1 // SPDX-License-Identifier: GPL-2.0
4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
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.
13 #include <linux/buffer_head.h>
15 #include <linux/kernel.h>
21 * Maximum number of extents in tree.
23 #define NTFS_MAX_WND_EXTENTS (32u * 1024u)
31 struct rb_node_key start
; /* Tree sorted by start. */
32 struct rb_node_key count
; /* Tree sorted by len. */
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
);
39 static struct kmem_cache
*ntfs_enode_cachep
;
41 int __init
ntfs3_init_bitmap(void)
44 kmem_cache_create("ntfs3_enode_cache", sizeof(struct e_node
), 0,
45 SLAB_RECLAIM_ACCOUNT
, NULL
);
46 return ntfs_enode_cachep
? 0 : -ENOMEM
;
49 void ntfs3_exit_bitmap(void)
51 kmem_cache_destroy(ntfs_enode_cachep
);
57 * b_pos + b_len - biggest fragment.
58 * Scan range [wpos wbits) window @buf.
60 * Return: -1 if not found.
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
,
69 u32 used
= find_next_zero_bit_le(buf
, wend
, wpos
);
72 if (*b_len
< *prev_tail
) {
73 *b_pos
= wbit
- *prev_tail
;
83 if (*b_len
< *prev_tail
) {
84 *b_pos
= wbit
- *prev_tail
;
92 * Now we have a fragment [wpos, wend) staring with 0.
94 end
= wpos
+ to_alloc
- *prev_tail
;
95 free_bits
= find_next_bit_le(buf
, min(end
, wend
), wpos
);
97 free_len
= *prev_tail
+ free_bits
- wpos
;
99 if (*b_len
< free_len
) {
100 *b_pos
= wbit
+ wpos
- *prev_tail
;
104 if (free_len
>= to_alloc
)
105 return wbit
+ wpos
- *prev_tail
;
107 if (free_bits
>= wend
) {
108 *prev_tail
+= free_bits
- wpos
;
112 wpos
= free_bits
+ 1;
121 * wnd_close - Frees all resources.
123 void wnd_close(struct wnd_bitmap
*wnd
)
125 struct rb_node
*node
, *next
;
127 kfree(wnd
->free_bits
);
128 run_close(&wnd
->run
);
130 node
= rb_first(&wnd
->start_tree
);
133 next
= rb_next(node
);
134 rb_erase(node
, &wnd
->start_tree
);
135 kmem_cache_free(ntfs_enode_cachep
,
136 rb_entry(node
, struct e_node
, start
.node
));
141 static struct rb_node
*rb_lookup(struct rb_root
*root
, size_t v
)
143 struct rb_node
**p
= &root
->rb_node
;
144 struct rb_node
*r
= NULL
;
147 struct rb_node_key
*k
;
149 k
= rb_entry(*p
, struct rb_node_key
, node
);
152 } else if (v
> k
->key
) {
164 * rb_insert_count - Helper function to insert special kind of 'count' tree.
166 static inline bool rb_insert_count(struct rb_root
*root
, struct e_node
*e
)
168 struct rb_node
**p
= &root
->rb_node
;
169 struct rb_node
*parent
= NULL
;
170 size_t e_ckey
= e
->count
.key
;
171 size_t e_skey
= e
->start
.key
;
175 rb_entry(parent
= *p
, struct e_node
, count
.node
);
177 if (e_ckey
> k
->count
.key
) {
179 } else if (e_ckey
< k
->count
.key
) {
181 } else if (e_skey
< k
->start
.key
) {
183 } else if (e_skey
> k
->start
.key
) {
191 rb_link_node(&e
->count
.node
, parent
, p
);
192 rb_insert_color(&e
->count
.node
, root
);
197 * rb_insert_start - Helper function to insert special kind of 'count' tree.
199 static inline bool rb_insert_start(struct rb_root
*root
, struct e_node
*e
)
201 struct rb_node
**p
= &root
->rb_node
;
202 struct rb_node
*parent
= NULL
;
203 size_t e_skey
= e
->start
.key
;
210 k
= rb_entry(parent
, struct e_node
, start
.node
);
211 if (e_skey
< k
->start
.key
) {
213 } else if (e_skey
> k
->start
.key
) {
221 rb_link_node(&e
->start
.node
, parent
, p
);
222 rb_insert_color(&e
->start
.node
, root
);
227 * wnd_add_free_ext - Adds a new extent of free space.
228 * @build: 1 when building tree.
230 static void wnd_add_free_ext(struct wnd_bitmap
*wnd
, size_t bit
, size_t len
,
233 struct e_node
*e
, *e0
= NULL
;
234 size_t ib
, end_in
= bit
+ len
;
238 /* Use extent_min to filter too short extents. */
239 if (wnd
->count
>= NTFS_MAX_WND_EXTENTS
&&
240 len
<= wnd
->extent_min
) {
245 /* Try to find extent before 'bit'. */
246 n
= rb_lookup(&wnd
->start_tree
, bit
);
249 n
= rb_first(&wnd
->start_tree
);
251 e
= rb_entry(n
, struct e_node
, start
.node
);
253 if (e
->start
.key
+ e
->count
.key
== bit
) {
257 rb_erase(&e
->start
.node
, &wnd
->start_tree
);
258 rb_erase(&e
->count
.node
, &wnd
->count_tree
);
267 e
= rb_entry(n
, struct e_node
, start
.node
);
268 next_end
= e
->start
.key
+ e
->count
.key
;
269 if (e
->start
.key
> end_in
)
274 len
+= next_end
- end_in
;
276 rb_erase(&e
->start
.node
, &wnd
->start_tree
);
277 rb_erase(&e
->count
.node
, &wnd
->count_tree
);
283 kmem_cache_free(ntfs_enode_cachep
, e
);
286 if (wnd
->uptodated
!= 1) {
287 /* Check bits before 'bit'. */
288 ib
= wnd
->zone_bit
== wnd
->zone_end
||
293 while (bit
> ib
&& wnd_is_free_hlp(wnd
, bit
- 1, 1)) {
298 /* Check bits after 'end_in'. */
299 ib
= wnd
->zone_bit
== wnd
->zone_end
||
300 end_in
> wnd
->zone_bit
304 while (end_in
< ib
&& wnd_is_free_hlp(wnd
, end_in
, 1)) {
310 /* Insert new fragment. */
311 if (wnd
->count
>= NTFS_MAX_WND_EXTENTS
) {
313 kmem_cache_free(ntfs_enode_cachep
, e0
);
317 /* Compare with smallest fragment. */
318 n
= rb_last(&wnd
->count_tree
);
319 e
= rb_entry(n
, struct e_node
, count
.node
);
320 if (len
<= e
->count
.key
)
321 goto out
; /* Do not insert small fragments. */
327 e2
= rb_entry(n
, struct e_node
, count
.node
);
328 /* Smallest fragment will be 'e2->count.key'. */
329 wnd
->extent_min
= e2
->count
.key
;
332 /* Replace smallest fragment by new one. */
333 rb_erase(&e
->start
.node
, &wnd
->start_tree
);
334 rb_erase(&e
->count
.node
, &wnd
->count_tree
);
337 e
= e0
? e0
: kmem_cache_alloc(ntfs_enode_cachep
, GFP_ATOMIC
);
343 if (build
&& len
<= wnd
->extent_min
)
344 wnd
->extent_min
= len
;
348 if (len
> wnd
->extent_max
)
349 wnd
->extent_max
= len
;
351 rb_insert_start(&wnd
->start_tree
, e
);
352 rb_insert_count(&wnd
->count_tree
, e
);
359 * wnd_remove_free_ext - Remove a run from the cached free space.
361 static void wnd_remove_free_ext(struct wnd_bitmap
*wnd
, size_t bit
, size_t len
)
363 struct rb_node
*n
, *n3
;
364 struct e_node
*e
, *e3
;
365 size_t end_in
= bit
+ len
;
366 size_t end3
, end
, new_key
, new_len
, max_new_len
;
368 /* Try to find extent before 'bit'. */
369 n
= rb_lookup(&wnd
->start_tree
, bit
);
374 e
= rb_entry(n
, struct e_node
, start
.node
);
375 end
= e
->start
.key
+ e
->count
.key
;
377 new_key
= new_len
= 0;
380 /* Range [bit,end_in) must be inside 'e' or outside 'e' and 'n'. */
381 if (e
->start
.key
> bit
)
383 else if (end_in
<= end
) {
384 /* Range [bit,end_in) inside 'e'. */
386 new_len
= end
- end_in
;
387 len
= bit
- e
->start
.key
;
388 } else if (bit
> end
) {
394 e3
= rb_entry(n3
, struct e_node
, start
.node
);
395 if (e3
->start
.key
>= end_in
)
398 if (e3
->count
.key
== wnd
->extent_max
)
401 end3
= e3
->start
.key
+ e3
->count
.key
;
403 e3
->start
.key
= end_in
;
404 rb_erase(&e3
->count
.node
, &wnd
->count_tree
);
405 e3
->count
.key
= end3
- end_in
;
406 rb_insert_count(&wnd
->count_tree
, e3
);
411 rb_erase(&e3
->start
.node
, &wnd
->start_tree
);
412 rb_erase(&e3
->count
.node
, &wnd
->count_tree
);
414 kmem_cache_free(ntfs_enode_cachep
, e3
);
418 n3
= rb_first(&wnd
->count_tree
);
420 n3
? rb_entry(n3
, struct e_node
, count
.node
)->count
.key
425 if (e
->count
.key
!= wnd
->extent_max
) {
427 } else if (rb_prev(&e
->count
.node
)) {
430 n3
= rb_next(&e
->count
.node
);
431 max_new_len
= max(len
, new_len
);
433 wnd
->extent_max
= max_new_len
;
435 e3
= rb_entry(n3
, struct e_node
, count
.node
);
436 wnd
->extent_max
= max(e3
->count
.key
, max_new_len
);
442 e
->start
.key
= new_key
;
443 rb_erase(&e
->count
.node
, &wnd
->count_tree
);
444 e
->count
.key
= new_len
;
445 rb_insert_count(&wnd
->count_tree
, e
);
447 rb_erase(&e
->start
.node
, &wnd
->start_tree
);
448 rb_erase(&e
->count
.node
, &wnd
->count_tree
);
450 kmem_cache_free(ntfs_enode_cachep
, e
);
454 rb_erase(&e
->count
.node
, &wnd
->count_tree
);
456 rb_insert_count(&wnd
->count_tree
, e
);
461 if (wnd
->count
>= NTFS_MAX_WND_EXTENTS
) {
464 /* Get minimal extent. */
465 e
= rb_entry(rb_last(&wnd
->count_tree
), struct e_node
,
467 if (e
->count
.key
> new_len
)
470 /* Replace minimum. */
471 rb_erase(&e
->start
.node
, &wnd
->start_tree
);
472 rb_erase(&e
->count
.node
, &wnd
->count_tree
);
475 e
= kmem_cache_alloc(ntfs_enode_cachep
, GFP_ATOMIC
);
481 e
->start
.key
= new_key
;
482 e
->count
.key
= new_len
;
483 rb_insert_start(&wnd
->start_tree
, e
);
484 rb_insert_count(&wnd
->count_tree
, e
);
489 if (!wnd
->count
&& 1 != wnd
->uptodated
)
494 * wnd_rescan - Scan all bitmap. Used while initialization.
496 static int wnd_rescan(struct wnd_bitmap
*wnd
)
499 size_t prev_tail
= 0;
500 struct super_block
*sb
= wnd
->sb
;
501 struct ntfs_sb_info
*sbi
= sb
->s_fs_info
;
503 u32 blocksize
= sb
->s_blocksize
;
504 u8 cluster_bits
= sbi
->cluster_bits
;
505 u32 wbits
= 8 * sb
->s_blocksize
;
507 size_t wpos
, wbit
, iw
, vbo
;
508 struct buffer_head
*bh
= NULL
;
513 wnd
->extent_min
= MINUS_ONE_T
;
514 wnd
->total_zeroes
= 0;
518 for (iw
= 0; iw
< wnd
->nwnd
; iw
++) {
519 if (iw
+ 1 == wnd
->nwnd
)
520 wbits
= wnd
->bits_last
;
523 if (!wnd
->free_bits
[iw
]) {
526 wnd_add_free_ext(wnd
,
533 if (wbits
== wnd
->free_bits
[iw
]) {
536 wnd
->total_zeroes
+= wbits
;
542 u32 off
= vbo
& sbi
->cluster_mask
;
544 if (!run_lookup_entry(&wnd
->run
, vbo
>> cluster_bits
,
545 &lcn
, &clen
, NULL
)) {
550 lbo
= ((u64
)lcn
<< cluster_bits
) + off
;
551 len
= ((u64
)clen
<< cluster_bits
) - off
;
554 bh
= ntfs_bread(sb
, lbo
>> sb
->s_blocksize_bits
);
560 used
= ntfs_bitmap_weight_le(bh
->b_data
, wbits
);
563 wnd
->free_bits
[iw
] = frb
;
564 wnd
->total_zeroes
+= frb
;
570 if (wbit
+ wbits
> wnd
->nbits
)
571 wbits
= wnd
->nbits
- wbit
;
574 used
= find_next_zero_bit_le(bh
->b_data
, wbits
, wpos
);
576 if (used
> wpos
&& prev_tail
) {
577 wnd_add_free_ext(wnd
, wbit
+ wpos
- prev_tail
,
585 /* No free blocks. */
590 frb
= find_next_bit_le(bh
->b_data
, wbits
, wpos
);
592 /* Keep last free block. */
593 prev_tail
+= frb
- wpos
;
597 wnd_add_free_ext(wnd
, wbit
+ wpos
- prev_tail
,
598 frb
+ prev_tail
- wpos
, true);
600 /* Skip free block and first '1'. */
602 /* Reset previous tail. */
604 } while (wpos
< wbits
);
619 /* Add last block. */
621 wnd_add_free_ext(wnd
, wnd
->nbits
- prev_tail
, prev_tail
, true);
624 * Before init cycle wnd->uptodated was 0.
625 * If any errors or limits occurs while initialization then
626 * wnd->uptodated will be -1.
627 * If 'uptodated' is still 0 then Tree is really updated.
632 if (wnd
->zone_bit
!= wnd
->zone_end
) {
633 size_t zlen
= wnd
->zone_end
- wnd
->zone_bit
;
635 wnd
->zone_end
= wnd
->zone_bit
;
636 wnd_zone_set(wnd
, wnd
->zone_bit
, zlen
);
643 int wnd_init(struct wnd_bitmap
*wnd
, struct super_block
*sb
, size_t nbits
)
646 u32 blocksize
= sb
->s_blocksize
;
647 u32 wbits
= blocksize
* 8;
649 init_rwsem(&wnd
->rw_lock
);
653 wnd
->total_zeroes
= nbits
;
654 wnd
->extent_max
= MINUS_ONE_T
;
655 wnd
->zone_bit
= wnd
->zone_end
= 0;
656 wnd
->nwnd
= bytes_to_block(sb
, bitmap_size(nbits
));
657 wnd
->bits_last
= nbits
& (wbits
- 1);
659 wnd
->bits_last
= wbits
;
661 wnd
->free_bits
= kcalloc(wnd
->nwnd
, sizeof(u16
), GFP_NOFS
| __GFP_NOWARN
);
665 err
= wnd_rescan(wnd
);
675 * wnd_map - Call sb_bread for requested window.
677 static struct buffer_head
*wnd_map(struct wnd_bitmap
*wnd
, size_t iw
)
681 struct super_block
*sb
= wnd
->sb
;
682 struct ntfs_sb_info
*sbi
;
683 struct buffer_head
*bh
;
687 vbo
= (u64
)iw
<< sb
->s_blocksize_bits
;
689 if (!run_lookup_entry(&wnd
->run
, vbo
>> sbi
->cluster_bits
, &lcn
, &clen
,
691 return ERR_PTR(-ENOENT
);
694 lbo
= ((u64
)lcn
<< sbi
->cluster_bits
) + (vbo
& sbi
->cluster_mask
);
696 bh
= ntfs_bread(wnd
->sb
, lbo
>> sb
->s_blocksize_bits
);
698 return ERR_PTR(-EIO
);
704 * wnd_set_free - Mark the bits range from bit to bit + bits as free.
706 int wnd_set_free(struct wnd_bitmap
*wnd
, size_t bit
, size_t bits
)
709 struct super_block
*sb
= wnd
->sb
;
711 u32 wbits
= 8 * sb
->s_blocksize
;
712 size_t iw
= bit
>> (sb
->s_blocksize_bits
+ 3);
713 u32 wbit
= bit
& (wbits
- 1);
714 struct buffer_head
*bh
;
716 while (iw
< wnd
->nwnd
&& bits
) {
719 if (iw
+ 1 == wnd
->nwnd
)
720 wbits
= wnd
->bits_last
;
723 op
= min_t(u32
, tail
, bits
);
725 bh
= wnd_map(wnd
, iw
);
733 ntfs_bitmap_clear_le(bh
->b_data
, wbit
, op
);
735 wnd
->free_bits
[iw
] += op
;
737 set_buffer_uptodate(bh
);
738 mark_buffer_dirty(bh
);
742 wnd
->total_zeroes
+= op
;
748 wnd_add_free_ext(wnd
, bit
, bits0
, false);
754 * wnd_set_used - Mark the bits range from bit to bit + bits as used.
756 int wnd_set_used(struct wnd_bitmap
*wnd
, size_t bit
, size_t bits
)
759 struct super_block
*sb
= wnd
->sb
;
761 size_t iw
= bit
>> (sb
->s_blocksize_bits
+ 3);
762 u32 wbits
= 8 * sb
->s_blocksize
;
763 u32 wbit
= bit
& (wbits
- 1);
764 struct buffer_head
*bh
;
766 while (iw
< wnd
->nwnd
&& bits
) {
769 if (unlikely(iw
+ 1 == wnd
->nwnd
))
770 wbits
= wnd
->bits_last
;
773 op
= min_t(u32
, tail
, bits
);
775 bh
= wnd_map(wnd
, iw
);
783 ntfs_bitmap_set_le(bh
->b_data
, wbit
, op
);
784 wnd
->free_bits
[iw
] -= op
;
786 set_buffer_uptodate(bh
);
787 mark_buffer_dirty(bh
);
791 wnd
->total_zeroes
-= op
;
797 if (!RB_EMPTY_ROOT(&wnd
->start_tree
))
798 wnd_remove_free_ext(wnd
, bit
, bits0
);
804 * wnd_set_used_safe - Mark the bits range from bit to bit + bits as used.
806 * Unlikely wnd_set_used/wnd_set_free this function is not full trusted.
807 * It scans every bit in bitmap and marks free bit as used.
808 * @done - how many bits were marked as used.
810 * NOTE: normally *done should be 0.
812 int wnd_set_used_safe(struct wnd_bitmap
*wnd
, size_t bit
, size_t bits
,
815 size_t i
, from
= 0, len
= 0;
819 for (i
= 0; i
< bits
; i
++) {
820 if (wnd_is_free(wnd
, bit
+ i
, 1)) {
825 err
= wnd_set_used(wnd
, from
, len
);
835 err
= wnd_set_used(wnd
, from
, len
);
844 * Return: True if all clusters [bit, bit+bits) are free (bitmap only).
846 static bool wnd_is_free_hlp(struct wnd_bitmap
*wnd
, size_t bit
, size_t bits
)
848 struct super_block
*sb
= wnd
->sb
;
849 size_t iw
= bit
>> (sb
->s_blocksize_bits
+ 3);
850 u32 wbits
= 8 * sb
->s_blocksize
;
851 u32 wbit
= bit
& (wbits
- 1);
853 while (iw
< wnd
->nwnd
&& bits
) {
856 if (unlikely(iw
+ 1 == wnd
->nwnd
))
857 wbits
= wnd
->bits_last
;
860 op
= min_t(u32
, tail
, bits
);
862 if (wbits
!= wnd
->free_bits
[iw
]) {
864 struct buffer_head
*bh
= wnd_map(wnd
, iw
);
869 ret
= are_bits_clear(bh
->b_data
, wbit
, op
);
887 * Return: True if all clusters [bit, bit+bits) are free.
889 bool wnd_is_free(struct wnd_bitmap
*wnd
, size_t bit
, size_t bits
)
896 if (RB_EMPTY_ROOT(&wnd
->start_tree
))
899 n
= rb_lookup(&wnd
->start_tree
, bit
);
903 e
= rb_entry(n
, struct e_node
, start
.node
);
905 end
= e
->start
.key
+ e
->count
.key
;
907 if (bit
< end
&& bit
+ bits
<= end
)
911 ret
= wnd_is_free_hlp(wnd
, bit
, bits
);
919 * Return: True if all clusters [bit, bit+bits) are used.
921 bool wnd_is_used(struct wnd_bitmap
*wnd
, size_t bit
, size_t bits
)
924 struct super_block
*sb
= wnd
->sb
;
925 size_t iw
= bit
>> (sb
->s_blocksize_bits
+ 3);
926 u32 wbits
= 8 * sb
->s_blocksize
;
927 u32 wbit
= bit
& (wbits
- 1);
932 if (RB_EMPTY_ROOT(&wnd
->start_tree
))
936 n
= rb_lookup(&wnd
->start_tree
, end
- 1);
940 e
= rb_entry(n
, struct e_node
, start
.node
);
941 if (e
->start
.key
+ e
->count
.key
> bit
)
945 while (iw
< wnd
->nwnd
&& bits
) {
948 if (unlikely(iw
+ 1 == wnd
->nwnd
))
949 wbits
= wnd
->bits_last
;
952 op
= min_t(u32
, tail
, bits
);
954 if (wnd
->free_bits
[iw
]) {
956 struct buffer_head
*bh
= wnd_map(wnd
, iw
);
961 ret
= are_bits_set(bh
->b_data
, wbit
, op
);
978 * wnd_find - Look for free space.
980 * - flags - BITMAP_FIND_XXX flags
982 * Return: 0 if not found.
984 size_t wnd_find(struct wnd_bitmap
*wnd
, size_t to_alloc
, size_t hint
,
985 size_t flags
, size_t *allocated
)
987 struct super_block
*sb
;
988 u32 wbits
, wpos
, wzbit
, wzend
;
989 size_t fnd
, max_alloc
, b_len
, b_pos
;
990 size_t iw
, prev_tail
, nwnd
, wbit
, ebit
, zbit
, zend
;
991 size_t to_alloc0
= to_alloc
;
992 const struct e_node
*e
;
993 const struct rb_node
*pr
, *cr
;
996 struct buffer_head
*bh
;
998 /* Fast checking for available free space. */
999 if (flags
& BITMAP_FIND_FULL
) {
1000 size_t zeroes
= wnd_zeroes(wnd
);
1002 zeroes
-= wnd
->zone_end
- wnd
->zone_bit
;
1003 if (zeroes
< to_alloc0
)
1006 if (to_alloc0
> wnd
->extent_max
)
1009 if (to_alloc
> wnd
->extent_max
)
1010 to_alloc
= wnd
->extent_max
;
1013 if (wnd
->zone_bit
<= hint
&& hint
< wnd
->zone_end
)
1014 hint
= wnd
->zone_end
;
1016 max_alloc
= wnd
->nbits
;
1019 if (hint
>= max_alloc
)
1022 if (RB_EMPTY_ROOT(&wnd
->start_tree
)) {
1023 if (wnd
->uptodated
== 1) {
1024 /* Extents tree is updated -> No free space. */
1032 goto allocate_biggest
;
1034 /* Use hint: Enumerate extents by start >= hint. */
1036 cr
= wnd
->start_tree
.rb_node
;
1039 e
= rb_entry(cr
, struct e_node
, start
.node
);
1041 if (e
->start
.key
== hint
)
1044 if (e
->start
.key
< hint
) {
1054 e
= pr
? rb_entry(pr
, struct e_node
, start
.node
) : NULL
;
1060 goto allocate_biggest
;
1062 if (e
->start
.key
+ e
->count
.key
> hint
) {
1063 /* We have found extension with 'hint' inside. */
1064 size_t len
= e
->start
.key
+ e
->count
.key
- hint
;
1066 if (len
>= to_alloc
&& hint
+ to_alloc
<= max_alloc
) {
1071 if (!(flags
& BITMAP_FIND_FULL
)) {
1075 if (hint
+ len
<= max_alloc
) {
1084 /* Allocate from biggest free extent. */
1085 e
= rb_entry(rb_first(&wnd
->count_tree
), struct e_node
, count
.node
);
1086 if (e
->count
.key
!= wnd
->extent_max
)
1087 wnd
->extent_max
= e
->count
.key
;
1089 if (e
->count
.key
< max_alloc
) {
1090 if (e
->count
.key
>= to_alloc
) {
1092 } else if (flags
& BITMAP_FIND_FULL
) {
1093 if (e
->count
.key
< to_alloc0
) {
1094 /* Biggest free block is less then requested. */
1097 to_alloc
= e
->count
.key
;
1098 } else if (-1 != wnd
->uptodated
) {
1099 to_alloc
= e
->count
.key
;
1101 /* Check if we can use more bits. */
1102 size_t op
, max_check
;
1103 struct rb_root start_tree
;
1105 memcpy(&start_tree
, &wnd
->start_tree
,
1106 sizeof(struct rb_root
));
1107 memset(&wnd
->start_tree
, 0, sizeof(struct rb_root
));
1109 max_check
= e
->start
.key
+ to_alloc
;
1110 if (max_check
> max_alloc
)
1111 max_check
= max_alloc
;
1112 for (op
= e
->start
.key
+ e
->count
.key
; op
< max_check
;
1114 if (!wnd_is_free(wnd
, op
, 1))
1117 memcpy(&wnd
->start_tree
, &start_tree
,
1118 sizeof(struct rb_root
));
1119 to_alloc
= op
- e
->start
.key
;
1122 /* Prepare to return. */
1124 if (e
->start
.key
+ to_alloc
> max_alloc
)
1125 to_alloc
= max_alloc
- e
->start
.key
;
1129 if (wnd
->uptodated
== 1) {
1130 /* Extents tree is updated -> no free space. */
1134 b_len
= e
->count
.key
;
1135 b_pos
= e
->start
.key
;
1139 log2_bits
= sb
->s_blocksize_bits
+ 3;
1141 /* At most two ranges [hint, max_alloc) + [0, hint). */
1144 /* TODO: Optimize request for case nbits > wbits. */
1145 iw
= hint
>> log2_bits
;
1146 wbits
= sb
->s_blocksize
* 8;
1147 wpos
= hint
& (wbits
- 1);
1151 if (max_alloc
== wnd
->nbits
) {
1154 size_t t
= max_alloc
+ wbits
- 1;
1156 nwnd
= likely(t
> max_alloc
) ? (t
>> log2_bits
) : wnd
->nwnd
;
1159 /* Enumerate all windows. */
1160 for (; iw
< nwnd
; iw
++) {
1161 wbit
= iw
<< log2_bits
;
1163 if (!wnd
->free_bits
[iw
]) {
1164 if (prev_tail
> b_len
) {
1165 b_pos
= wbit
- prev_tail
;
1169 /* Skip full used window. */
1175 if (unlikely(iw
+ 1 == nwnd
)) {
1176 if (max_alloc
== wnd
->nbits
) {
1177 wbits
= wnd
->bits_last
;
1179 size_t t
= max_alloc
& (wbits
- 1);
1183 fbits_valid
= false;
1188 if (wnd
->zone_end
> wnd
->zone_bit
) {
1189 ebit
= wbit
+ wbits
;
1190 zbit
= max(wnd
->zone_bit
, wbit
);
1191 zend
= min(wnd
->zone_end
, ebit
);
1193 /* Here we have a window [wbit, ebit) and zone [zbit, zend). */
1195 /* Zone does not overlap window. */
1197 wzbit
= zbit
- wbit
;
1198 wzend
= zend
- wbit
;
1200 /* Zone overlaps window. */
1201 if (wnd
->free_bits
[iw
] == wzend
- wzbit
) {
1207 /* Scan two ranges window: [wbit, zbit) and [zend, ebit). */
1208 bh
= wnd_map(wnd
, iw
);
1217 /* Scan range [wbit, zbit). */
1219 /* Scan range [wpos, zbit). */
1220 fnd
= wnd_scan(bh
->b_data
, wbit
, wpos
,
1224 if (fnd
!= MINUS_ONE_T
) {
1232 /* Scan range [zend, ebit). */
1233 if (wzend
< wbits
) {
1234 fnd
= wnd_scan(bh
->b_data
, wbit
,
1235 max(wzend
, wpos
), wbits
,
1236 to_alloc
, &prev_tail
,
1238 if (fnd
!= MINUS_ONE_T
) {
1250 /* Current window does not overlap zone. */
1251 if (!wpos
&& fbits_valid
&& wnd
->free_bits
[iw
] == wbits
) {
1252 /* Window is empty. */
1253 if (prev_tail
+ wbits
>= to_alloc
) {
1254 fnd
= wbit
+ wpos
- prev_tail
;
1258 /* Increase 'prev_tail' and process next window. */
1265 bh
= wnd_map(wnd
, iw
);
1273 /* Scan range [wpos, eBits). */
1274 fnd
= wnd_scan(bh
->b_data
, wbit
, wpos
, wbits
, to_alloc
,
1275 &prev_tail
, &b_pos
, &b_len
);
1277 if (fnd
!= MINUS_ONE_T
)
1281 if (b_len
< prev_tail
) {
1282 /* The last fragment. */
1284 b_pos
= max_alloc
- prev_tail
;
1289 * We have scanned range [hint max_alloc).
1290 * Prepare to scan range [0 hint + to_alloc).
1292 size_t nextmax
= hint
+ to_alloc
;
1294 if (likely(nextmax
>= hint
) && nextmax
< max_alloc
)
1295 max_alloc
= nextmax
;
1303 wnd
->extent_max
= b_len
;
1305 if (flags
& BITMAP_FIND_FULL
)
1312 if (flags
& BITMAP_FIND_MARK_AS_USED
) {
1313 /* TODO: Optimize remove extent (pass 'e'?). */
1314 if (wnd_set_used(wnd
, fnd
, to_alloc
))
1316 } else if (wnd
->extent_max
!= MINUS_ONE_T
&&
1317 to_alloc
> wnd
->extent_max
) {
1318 wnd
->extent_max
= to_alloc
;
1329 * wnd_extend - Extend bitmap ($MFT bitmap).
1331 int wnd_extend(struct wnd_bitmap
*wnd
, size_t new_bits
)
1334 struct super_block
*sb
= wnd
->sb
;
1335 struct ntfs_sb_info
*sbi
= sb
->s_fs_info
;
1336 u32 blocksize
= sb
->s_blocksize
;
1337 u32 wbits
= blocksize
* 8;
1339 size_t bits
, iw
, new_wnd
;
1340 size_t old_bits
= wnd
->nbits
;
1343 if (new_bits
<= old_bits
)
1346 /* Align to 8 byte boundary. */
1347 new_wnd
= bytes_to_block(sb
, bitmap_size(new_bits
));
1348 new_last
= new_bits
& (wbits
- 1);
1352 if (new_wnd
!= wnd
->nwnd
) {
1353 new_free
= kmalloc_array(new_wnd
, sizeof(u16
), GFP_NOFS
);
1357 memcpy(new_free
, wnd
->free_bits
, wnd
->nwnd
* sizeof(short));
1358 memset(new_free
+ wnd
->nwnd
, 0,
1359 (new_wnd
- wnd
->nwnd
) * sizeof(short));
1360 kfree(wnd
->free_bits
);
1361 wnd
->free_bits
= new_free
;
1364 /* Zero bits [old_bits,new_bits). */
1365 bits
= new_bits
- old_bits
;
1366 b0
= old_bits
& (wbits
- 1);
1368 for (iw
= old_bits
>> (sb
->s_blocksize_bits
+ 3); bits
; iw
+= 1) {
1371 u64 vbo
, lbo
, bytes
;
1372 struct buffer_head
*bh
;
1374 if (iw
+ 1 == new_wnd
)
1377 op
= b0
+ bits
> wbits
? wbits
- b0
: bits
;
1378 vbo
= (u64
)iw
* blocksize
;
1380 err
= ntfs_vbo_to_lbo(sbi
, &wnd
->run
, vbo
, &lbo
, &bytes
);
1384 bh
= ntfs_bread(sb
, lbo
>> sb
->s_blocksize_bits
);
1390 ntfs_bitmap_clear_le(bh
->b_data
, b0
, blocksize
* 8 - b0
);
1391 frb
= wbits
- ntfs_bitmap_weight_le(bh
->b_data
, wbits
);
1392 wnd
->total_zeroes
+= frb
- wnd
->free_bits
[iw
];
1393 wnd
->free_bits
[iw
] = frb
;
1395 set_buffer_uptodate(bh
);
1396 mark_buffer_dirty(bh
);
1398 /* err = sync_dirty_buffer(bh); */
1404 wnd
->nbits
= new_bits
;
1405 wnd
->nwnd
= new_wnd
;
1406 wnd
->bits_last
= new_last
;
1408 wnd_add_free_ext(wnd
, old_bits
, new_bits
- old_bits
, false);
1413 void wnd_zone_set(struct wnd_bitmap
*wnd
, size_t lcn
, size_t len
)
1415 size_t zlen
= wnd
->zone_end
- wnd
->zone_bit
;
1418 wnd_add_free_ext(wnd
, wnd
->zone_bit
, zlen
, false);
1420 if (!RB_EMPTY_ROOT(&wnd
->start_tree
) && len
)
1421 wnd_remove_free_ext(wnd
, lcn
, len
);
1423 wnd
->zone_bit
= lcn
;
1424 wnd
->zone_end
= lcn
+ len
;
1427 int ntfs_trim_fs(struct ntfs_sb_info
*sbi
, struct fstrim_range
*range
)
1430 struct super_block
*sb
= sbi
->sb
;
1431 struct wnd_bitmap
*wnd
= &sbi
->used
.bitmap
;
1432 u32 wbits
= 8 * sb
->s_blocksize
;
1433 CLST len
= 0, lcn
= 0, done
= 0;
1434 CLST minlen
= bytes_to_cluster(sbi
, range
->minlen
);
1435 CLST lcn_from
= bytes_to_cluster(sbi
, range
->start
);
1436 size_t iw
= lcn_from
>> (sb
->s_blocksize_bits
+ 3);
1437 u32 wbit
= lcn_from
& (wbits
- 1);
1443 if (range
->len
== (u64
)-1)
1444 lcn_to
= wnd
->nbits
;
1446 lcn_to
= bytes_to_cluster(sbi
, range
->start
+ range
->len
);
1448 down_read_nested(&wnd
->rw_lock
, BITMAP_MUTEX_CLUSTERS
);
1450 for (; iw
< wnd
->nwnd
; iw
++, wbit
= 0) {
1451 CLST lcn_wnd
= iw
* wbits
;
1452 struct buffer_head
*bh
;
1454 if (lcn_wnd
> lcn_to
)
1457 if (!wnd
->free_bits
[iw
])
1460 if (iw
+ 1 == wnd
->nwnd
)
1461 wbits
= wnd
->bits_last
;
1463 if (lcn_wnd
+ wbits
> lcn_to
)
1464 wbits
= lcn_to
- lcn_wnd
;
1466 bh
= wnd_map(wnd
, iw
);
1472 for (; wbit
< wbits
; wbit
++) {
1473 if (!test_bit_le(wbit
, bh
->b_data
)) {
1475 lcn
= lcn_wnd
+ wbit
;
1479 if (len
>= minlen
) {
1480 err
= ntfs_discard(sbi
, lcn
, len
);
1490 /* Process the last fragment. */
1491 if (len
>= minlen
) {
1492 err
= ntfs_discard(sbi
, lcn
, len
);
1499 range
->len
= (u64
)done
<< sbi
->cluster_bits
;
1501 up_read(&wnd
->rw_lock
);
1506 #if BITS_PER_LONG == 64
1507 typedef __le64 bitmap_ulong
;
1508 #define cpu_to_ul(x) cpu_to_le64(x)
1509 #define ul_to_cpu(x) le64_to_cpu(x)
1511 typedef __le32 bitmap_ulong
;
1512 #define cpu_to_ul(x) cpu_to_le32(x)
1513 #define ul_to_cpu(x) le32_to_cpu(x)
1516 void ntfs_bitmap_set_le(void *map
, unsigned int start
, int len
)
1518 bitmap_ulong
*p
= (bitmap_ulong
*)map
+ BIT_WORD(start
);
1519 const unsigned int size
= start
+ len
;
1520 int bits_to_set
= BITS_PER_LONG
- (start
% BITS_PER_LONG
);
1521 bitmap_ulong mask_to_set
= cpu_to_ul(BITMAP_FIRST_WORD_MASK(start
));
1523 while (len
- bits_to_set
>= 0) {
1526 bits_to_set
= BITS_PER_LONG
;
1527 mask_to_set
= cpu_to_ul(~0UL);
1531 mask_to_set
&= cpu_to_ul(BITMAP_LAST_WORD_MASK(size
));
1536 void ntfs_bitmap_clear_le(void *map
, unsigned int start
, int len
)
1538 bitmap_ulong
*p
= (bitmap_ulong
*)map
+ BIT_WORD(start
);
1539 const unsigned int size
= start
+ len
;
1540 int bits_to_clear
= BITS_PER_LONG
- (start
% BITS_PER_LONG
);
1541 bitmap_ulong mask_to_clear
= cpu_to_ul(BITMAP_FIRST_WORD_MASK(start
));
1543 while (len
- bits_to_clear
>= 0) {
1544 *p
&= ~mask_to_clear
;
1545 len
-= bits_to_clear
;
1546 bits_to_clear
= BITS_PER_LONG
;
1547 mask_to_clear
= cpu_to_ul(~0UL);
1551 mask_to_clear
&= cpu_to_ul(BITMAP_LAST_WORD_MASK(size
));
1552 *p
&= ~mask_to_clear
;
1556 unsigned int ntfs_bitmap_weight_le(const void *bitmap
, int bits
)
1558 const ulong
*bmp
= bitmap
;
1559 unsigned int k
, lim
= bits
/ BITS_PER_LONG
;
1562 for (k
= 0; k
< lim
; k
++)
1563 w
+= hweight_long(bmp
[k
]);
1565 if (bits
% BITS_PER_LONG
) {
1566 w
+= hweight_long(ul_to_cpu(((bitmap_ulong
*)bitmap
)[k
]) &
1567 BITMAP_LAST_WORD_MASK(bits
));