]>
git.proxmox.com Git - mirror_ubuntu-kernels.git/blob - fs/ntfs3/bitmap.c
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 ulong
*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(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(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
;
508 size_t wpos
, wbit
, iw
, vbo
;
509 struct buffer_head
*bh
= NULL
;
514 wnd
->extent_min
= MINUS_ONE_T
;
515 wnd
->total_zeroes
= 0;
519 for (iw
= 0; iw
< wnd
->nwnd
; iw
++) {
520 if (iw
+ 1 == wnd
->nwnd
)
521 wbits
= wnd
->bits_last
;
524 if (!wnd
->free_bits
[iw
]) {
527 wnd_add_free_ext(wnd
,
534 if (wbits
== wnd
->free_bits
[iw
]) {
537 wnd
->total_zeroes
+= wbits
;
543 u32 off
= vbo
& sbi
->cluster_mask
;
545 if (!run_lookup_entry(&wnd
->run
, vbo
>> cluster_bits
,
546 &lcn
, &clen
, NULL
)) {
551 lbo
= ((u64
)lcn
<< cluster_bits
) + off
;
552 len
= ((u64
)clen
<< cluster_bits
) - off
;
555 bh
= ntfs_bread(sb
, lbo
>> sb
->s_blocksize_bits
);
561 buf
= (ulong
*)bh
->b_data
;
563 used
= __bitmap_weight(buf
, wbits
);
566 wnd
->free_bits
[iw
] = frb
;
567 wnd
->total_zeroes
+= frb
;
573 if (wbit
+ wbits
> wnd
->nbits
)
574 wbits
= wnd
->nbits
- wbit
;
577 used
= find_next_zero_bit(buf
, wbits
, wpos
);
579 if (used
> wpos
&& prev_tail
) {
580 wnd_add_free_ext(wnd
, wbit
+ wpos
- prev_tail
,
588 /* No free blocks. */
593 frb
= find_next_bit(buf
, wbits
, wpos
);
595 /* Keep last free block. */
596 prev_tail
+= frb
- wpos
;
600 wnd_add_free_ext(wnd
, wbit
+ wpos
- prev_tail
,
601 frb
+ prev_tail
- wpos
, true);
603 /* Skip free block and first '1'. */
605 /* Reset previous tail. */
607 } while (wpos
< wbits
);
622 /* Add last block. */
624 wnd_add_free_ext(wnd
, wnd
->nbits
- prev_tail
, prev_tail
, true);
627 * Before init cycle wnd->uptodated was 0.
628 * If any errors or limits occurs while initialization then
629 * wnd->uptodated will be -1.
630 * If 'uptodated' is still 0 then Tree is really updated.
635 if (wnd
->zone_bit
!= wnd
->zone_end
) {
636 size_t zlen
= wnd
->zone_end
- wnd
->zone_bit
;
638 wnd
->zone_end
= wnd
->zone_bit
;
639 wnd_zone_set(wnd
, wnd
->zone_bit
, zlen
);
646 int wnd_init(struct wnd_bitmap
*wnd
, struct super_block
*sb
, size_t nbits
)
649 u32 blocksize
= sb
->s_blocksize
;
650 u32 wbits
= blocksize
* 8;
652 init_rwsem(&wnd
->rw_lock
);
656 wnd
->total_zeroes
= nbits
;
657 wnd
->extent_max
= MINUS_ONE_T
;
658 wnd
->zone_bit
= wnd
->zone_end
= 0;
659 wnd
->nwnd
= bytes_to_block(sb
, bitmap_size(nbits
));
660 wnd
->bits_last
= nbits
& (wbits
- 1);
662 wnd
->bits_last
= wbits
;
664 wnd
->free_bits
= kcalloc(wnd
->nwnd
, sizeof(u16
), GFP_NOFS
| __GFP_NOWARN
);
668 err
= wnd_rescan(wnd
);
678 * wnd_map - Call sb_bread for requested window.
680 static struct buffer_head
*wnd_map(struct wnd_bitmap
*wnd
, size_t iw
)
684 struct super_block
*sb
= wnd
->sb
;
685 struct ntfs_sb_info
*sbi
;
686 struct buffer_head
*bh
;
690 vbo
= (u64
)iw
<< sb
->s_blocksize_bits
;
692 if (!run_lookup_entry(&wnd
->run
, vbo
>> sbi
->cluster_bits
, &lcn
, &clen
,
694 return ERR_PTR(-ENOENT
);
697 lbo
= ((u64
)lcn
<< sbi
->cluster_bits
) + (vbo
& sbi
->cluster_mask
);
699 bh
= ntfs_bread(wnd
->sb
, lbo
>> sb
->s_blocksize_bits
);
701 return ERR_PTR(-EIO
);
707 * wnd_set_free - Mark the bits range from bit to bit + bits as free.
709 int wnd_set_free(struct wnd_bitmap
*wnd
, size_t bit
, size_t bits
)
712 struct super_block
*sb
= wnd
->sb
;
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
;
719 while (iw
< wnd
->nwnd
&& bits
) {
723 if (iw
+ 1 == wnd
->nwnd
)
724 wbits
= wnd
->bits_last
;
727 op
= min_t(u32
, tail
, bits
);
729 bh
= wnd_map(wnd
, iw
);
735 buf
= (ulong
*)bh
->b_data
;
739 __bitmap_clear(buf
, wbit
, op
);
741 wnd
->free_bits
[iw
] += op
;
743 set_buffer_uptodate(bh
);
744 mark_buffer_dirty(bh
);
748 wnd
->total_zeroes
+= op
;
754 wnd_add_free_ext(wnd
, bit
, bits0
, false);
760 * wnd_set_used - Mark the bits range from bit to bit + bits as used.
762 int wnd_set_used(struct wnd_bitmap
*wnd
, size_t bit
, size_t bits
)
765 struct super_block
*sb
= wnd
->sb
;
767 size_t iw
= bit
>> (sb
->s_blocksize_bits
+ 3);
768 u32 wbits
= 8 * sb
->s_blocksize
;
769 u32 wbit
= bit
& (wbits
- 1);
770 struct buffer_head
*bh
;
772 while (iw
< wnd
->nwnd
&& bits
) {
776 if (unlikely(iw
+ 1 == wnd
->nwnd
))
777 wbits
= wnd
->bits_last
;
780 op
= min_t(u32
, tail
, bits
);
782 bh
= wnd_map(wnd
, iw
);
787 buf
= (ulong
*)bh
->b_data
;
791 __bitmap_set(buf
, wbit
, op
);
792 wnd
->free_bits
[iw
] -= op
;
794 set_buffer_uptodate(bh
);
795 mark_buffer_dirty(bh
);
799 wnd
->total_zeroes
-= op
;
805 if (!RB_EMPTY_ROOT(&wnd
->start_tree
))
806 wnd_remove_free_ext(wnd
, bit
, bits0
);
814 * Return: True if all clusters [bit, bit+bits) are free (bitmap only).
816 static bool wnd_is_free_hlp(struct wnd_bitmap
*wnd
, size_t bit
, size_t bits
)
818 struct super_block
*sb
= wnd
->sb
;
819 size_t iw
= bit
>> (sb
->s_blocksize_bits
+ 3);
820 u32 wbits
= 8 * sb
->s_blocksize
;
821 u32 wbit
= bit
& (wbits
- 1);
823 while (iw
< wnd
->nwnd
&& bits
) {
826 if (unlikely(iw
+ 1 == wnd
->nwnd
))
827 wbits
= wnd
->bits_last
;
830 op
= min_t(u32
, tail
, bits
);
832 if (wbits
!= wnd
->free_bits
[iw
]) {
834 struct buffer_head
*bh
= wnd_map(wnd
, iw
);
839 ret
= are_bits_clear((ulong
*)bh
->b_data
, wbit
, op
);
857 * Return: True if all clusters [bit, bit+bits) are free.
859 bool wnd_is_free(struct wnd_bitmap
*wnd
, size_t bit
, size_t bits
)
866 if (RB_EMPTY_ROOT(&wnd
->start_tree
))
869 n
= rb_lookup(&wnd
->start_tree
, bit
);
873 e
= rb_entry(n
, struct e_node
, start
.node
);
875 end
= e
->start
.key
+ e
->count
.key
;
877 if (bit
< end
&& bit
+ bits
<= end
)
881 ret
= wnd_is_free_hlp(wnd
, bit
, bits
);
889 * Return: True if all clusters [bit, bit+bits) are used.
891 bool wnd_is_used(struct wnd_bitmap
*wnd
, size_t bit
, size_t bits
)
894 struct super_block
*sb
= wnd
->sb
;
895 size_t iw
= bit
>> (sb
->s_blocksize_bits
+ 3);
896 u32 wbits
= 8 * sb
->s_blocksize
;
897 u32 wbit
= bit
& (wbits
- 1);
902 if (RB_EMPTY_ROOT(&wnd
->start_tree
))
906 n
= rb_lookup(&wnd
->start_tree
, end
- 1);
910 e
= rb_entry(n
, struct e_node
, start
.node
);
911 if (e
->start
.key
+ e
->count
.key
> bit
)
915 while (iw
< wnd
->nwnd
&& bits
) {
918 if (unlikely(iw
+ 1 == wnd
->nwnd
))
919 wbits
= wnd
->bits_last
;
922 op
= min_t(u32
, tail
, bits
);
924 if (wnd
->free_bits
[iw
]) {
926 struct buffer_head
*bh
= wnd_map(wnd
, iw
);
931 ret
= are_bits_set((ulong
*)bh
->b_data
, wbit
, op
);
948 * wnd_find - Look for free space.
950 * - flags - BITMAP_FIND_XXX flags
952 * Return: 0 if not found.
954 size_t wnd_find(struct wnd_bitmap
*wnd
, size_t to_alloc
, size_t hint
,
955 size_t flags
, size_t *allocated
)
957 struct super_block
*sb
;
958 u32 wbits
, wpos
, wzbit
, wzend
;
959 size_t fnd
, max_alloc
, b_len
, b_pos
;
960 size_t iw
, prev_tail
, nwnd
, wbit
, ebit
, zbit
, zend
;
961 size_t to_alloc0
= to_alloc
;
963 const struct e_node
*e
;
964 const struct rb_node
*pr
, *cr
;
967 struct buffer_head
*bh
;
969 /* Fast checking for available free space. */
970 if (flags
& BITMAP_FIND_FULL
) {
971 size_t zeroes
= wnd_zeroes(wnd
);
973 zeroes
-= wnd
->zone_end
- wnd
->zone_bit
;
974 if (zeroes
< to_alloc0
)
977 if (to_alloc0
> wnd
->extent_max
)
980 if (to_alloc
> wnd
->extent_max
)
981 to_alloc
= wnd
->extent_max
;
984 if (wnd
->zone_bit
<= hint
&& hint
< wnd
->zone_end
)
985 hint
= wnd
->zone_end
;
987 max_alloc
= wnd
->nbits
;
990 if (hint
>= max_alloc
)
993 if (RB_EMPTY_ROOT(&wnd
->start_tree
)) {
994 if (wnd
->uptodated
== 1) {
995 /* Extents tree is updated -> No free space. */
1003 goto allocate_biggest
;
1005 /* Use hint: Enumerate extents by start >= hint. */
1007 cr
= wnd
->start_tree
.rb_node
;
1010 e
= rb_entry(cr
, struct e_node
, start
.node
);
1012 if (e
->start
.key
== hint
)
1015 if (e
->start
.key
< hint
) {
1025 e
= pr
? rb_entry(pr
, struct e_node
, start
.node
) : NULL
;
1031 goto allocate_biggest
;
1033 if (e
->start
.key
+ e
->count
.key
> hint
) {
1034 /* We have found extension with 'hint' inside. */
1035 size_t len
= e
->start
.key
+ e
->count
.key
- hint
;
1037 if (len
>= to_alloc
&& hint
+ to_alloc
<= max_alloc
) {
1042 if (!(flags
& BITMAP_FIND_FULL
)) {
1046 if (hint
+ len
<= max_alloc
) {
1055 /* Allocate from biggest free extent. */
1056 e
= rb_entry(rb_first(&wnd
->count_tree
), struct e_node
, count
.node
);
1057 if (e
->count
.key
!= wnd
->extent_max
)
1058 wnd
->extent_max
= e
->count
.key
;
1060 if (e
->count
.key
< max_alloc
) {
1061 if (e
->count
.key
>= to_alloc
) {
1063 } else if (flags
& BITMAP_FIND_FULL
) {
1064 if (e
->count
.key
< to_alloc0
) {
1065 /* Biggest free block is less then requested. */
1068 to_alloc
= e
->count
.key
;
1069 } else if (-1 != wnd
->uptodated
) {
1070 to_alloc
= e
->count
.key
;
1072 /* Check if we can use more bits. */
1073 size_t op
, max_check
;
1074 struct rb_root start_tree
;
1076 memcpy(&start_tree
, &wnd
->start_tree
,
1077 sizeof(struct rb_root
));
1078 memset(&wnd
->start_tree
, 0, sizeof(struct rb_root
));
1080 max_check
= e
->start
.key
+ to_alloc
;
1081 if (max_check
> max_alloc
)
1082 max_check
= max_alloc
;
1083 for (op
= e
->start
.key
+ e
->count
.key
; op
< max_check
;
1085 if (!wnd_is_free(wnd
, op
, 1))
1088 memcpy(&wnd
->start_tree
, &start_tree
,
1089 sizeof(struct rb_root
));
1090 to_alloc
= op
- e
->start
.key
;
1093 /* Prepare to return. */
1095 if (e
->start
.key
+ to_alloc
> max_alloc
)
1096 to_alloc
= max_alloc
- e
->start
.key
;
1100 if (wnd
->uptodated
== 1) {
1101 /* Extents tree is updated -> no free space. */
1105 b_len
= e
->count
.key
;
1106 b_pos
= e
->start
.key
;
1110 log2_bits
= sb
->s_blocksize_bits
+ 3;
1112 /* At most two ranges [hint, max_alloc) + [0, hint). */
1115 /* TODO: Optimize request for case nbits > wbits. */
1116 iw
= hint
>> log2_bits
;
1117 wbits
= sb
->s_blocksize
* 8;
1118 wpos
= hint
& (wbits
- 1);
1122 if (max_alloc
== wnd
->nbits
) {
1125 size_t t
= max_alloc
+ wbits
- 1;
1127 nwnd
= likely(t
> max_alloc
) ? (t
>> log2_bits
) : wnd
->nwnd
;
1130 /* Enumerate all windows. */
1131 for (; iw
< nwnd
; iw
++) {
1132 wbit
= iw
<< log2_bits
;
1134 if (!wnd
->free_bits
[iw
]) {
1135 if (prev_tail
> b_len
) {
1136 b_pos
= wbit
- prev_tail
;
1140 /* Skip full used window. */
1146 if (unlikely(iw
+ 1 == nwnd
)) {
1147 if (max_alloc
== wnd
->nbits
) {
1148 wbits
= wnd
->bits_last
;
1150 size_t t
= max_alloc
& (wbits
- 1);
1154 fbits_valid
= false;
1159 if (wnd
->zone_end
> wnd
->zone_bit
) {
1160 ebit
= wbit
+ wbits
;
1161 zbit
= max(wnd
->zone_bit
, wbit
);
1162 zend
= min(wnd
->zone_end
, ebit
);
1164 /* Here we have a window [wbit, ebit) and zone [zbit, zend). */
1166 /* Zone does not overlap window. */
1168 wzbit
= zbit
- wbit
;
1169 wzend
= zend
- wbit
;
1171 /* Zone overlaps window. */
1172 if (wnd
->free_bits
[iw
] == wzend
- wzbit
) {
1178 /* Scan two ranges window: [wbit, zbit) and [zend, ebit). */
1179 bh
= wnd_map(wnd
, iw
);
1188 buf
= (ulong
*)bh
->b_data
;
1190 /* Scan range [wbit, zbit). */
1192 /* Scan range [wpos, zbit). */
1193 fnd
= wnd_scan(buf
, wbit
, wpos
, wzbit
,
1194 to_alloc
, &prev_tail
,
1196 if (fnd
!= MINUS_ONE_T
) {
1204 /* Scan range [zend, ebit). */
1205 if (wzend
< wbits
) {
1206 fnd
= wnd_scan(buf
, wbit
,
1207 max(wzend
, wpos
), wbits
,
1208 to_alloc
, &prev_tail
,
1210 if (fnd
!= MINUS_ONE_T
) {
1222 /* Current window does not overlap zone. */
1223 if (!wpos
&& fbits_valid
&& wnd
->free_bits
[iw
] == wbits
) {
1224 /* Window is empty. */
1225 if (prev_tail
+ wbits
>= to_alloc
) {
1226 fnd
= wbit
+ wpos
- prev_tail
;
1230 /* Increase 'prev_tail' and process next window. */
1237 bh
= wnd_map(wnd
, iw
);
1245 buf
= (ulong
*)bh
->b_data
;
1247 /* Scan range [wpos, eBits). */
1248 fnd
= wnd_scan(buf
, wbit
, wpos
, wbits
, to_alloc
, &prev_tail
,
1251 if (fnd
!= MINUS_ONE_T
)
1255 if (b_len
< prev_tail
) {
1256 /* The last fragment. */
1258 b_pos
= max_alloc
- prev_tail
;
1263 * We have scanned range [hint max_alloc).
1264 * Prepare to scan range [0 hint + to_alloc).
1266 size_t nextmax
= hint
+ to_alloc
;
1268 if (likely(nextmax
>= hint
) && nextmax
< max_alloc
)
1269 max_alloc
= nextmax
;
1277 wnd
->extent_max
= b_len
;
1279 if (flags
& BITMAP_FIND_FULL
)
1286 if (flags
& BITMAP_FIND_MARK_AS_USED
) {
1287 /* TODO: Optimize remove extent (pass 'e'?). */
1288 if (wnd_set_used(wnd
, fnd
, to_alloc
))
1290 } else if (wnd
->extent_max
!= MINUS_ONE_T
&&
1291 to_alloc
> wnd
->extent_max
) {
1292 wnd
->extent_max
= to_alloc
;
1303 * wnd_extend - Extend bitmap ($MFT bitmap).
1305 int wnd_extend(struct wnd_bitmap
*wnd
, size_t new_bits
)
1308 struct super_block
*sb
= wnd
->sb
;
1309 struct ntfs_sb_info
*sbi
= sb
->s_fs_info
;
1310 u32 blocksize
= sb
->s_blocksize
;
1311 u32 wbits
= blocksize
* 8;
1313 size_t bits
, iw
, new_wnd
;
1314 size_t old_bits
= wnd
->nbits
;
1317 if (new_bits
<= old_bits
)
1320 /* Align to 8 byte boundary. */
1321 new_wnd
= bytes_to_block(sb
, bitmap_size(new_bits
));
1322 new_last
= new_bits
& (wbits
- 1);
1326 if (new_wnd
!= wnd
->nwnd
) {
1327 new_free
= kmalloc_array(new_wnd
, sizeof(u16
), GFP_NOFS
);
1331 memcpy(new_free
, wnd
->free_bits
, wnd
->nwnd
* sizeof(short));
1332 memset(new_free
+ wnd
->nwnd
, 0,
1333 (new_wnd
- wnd
->nwnd
) * sizeof(short));
1334 kfree(wnd
->free_bits
);
1335 wnd
->free_bits
= new_free
;
1338 /* Zero bits [old_bits,new_bits). */
1339 bits
= new_bits
- old_bits
;
1340 b0
= old_bits
& (wbits
- 1);
1342 for (iw
= old_bits
>> (sb
->s_blocksize_bits
+ 3); bits
; iw
+= 1) {
1345 u64 vbo
, lbo
, bytes
;
1346 struct buffer_head
*bh
;
1349 if (iw
+ 1 == new_wnd
)
1352 op
= b0
+ bits
> wbits
? wbits
- b0
: bits
;
1353 vbo
= (u64
)iw
* blocksize
;
1355 err
= ntfs_vbo_to_lbo(sbi
, &wnd
->run
, vbo
, &lbo
, &bytes
);
1359 bh
= ntfs_bread(sb
, lbo
>> sb
->s_blocksize_bits
);
1364 buf
= (ulong
*)bh
->b_data
;
1366 __bitmap_clear(buf
, b0
, blocksize
* 8 - b0
);
1367 frb
= wbits
- __bitmap_weight(buf
, wbits
);
1368 wnd
->total_zeroes
+= frb
- wnd
->free_bits
[iw
];
1369 wnd
->free_bits
[iw
] = frb
;
1371 set_buffer_uptodate(bh
);
1372 mark_buffer_dirty(bh
);
1374 /* err = sync_dirty_buffer(bh); */
1380 wnd
->nbits
= new_bits
;
1381 wnd
->nwnd
= new_wnd
;
1382 wnd
->bits_last
= new_last
;
1384 wnd_add_free_ext(wnd
, old_bits
, new_bits
- old_bits
, false);
1389 void wnd_zone_set(struct wnd_bitmap
*wnd
, size_t lcn
, size_t len
)
1391 size_t zlen
= wnd
->zone_end
- wnd
->zone_bit
;
1394 wnd_add_free_ext(wnd
, wnd
->zone_bit
, zlen
, false);
1396 if (!RB_EMPTY_ROOT(&wnd
->start_tree
) && len
)
1397 wnd_remove_free_ext(wnd
, lcn
, len
);
1399 wnd
->zone_bit
= lcn
;
1400 wnd
->zone_end
= lcn
+ len
;
1403 int ntfs_trim_fs(struct ntfs_sb_info
*sbi
, struct fstrim_range
*range
)
1406 struct super_block
*sb
= sbi
->sb
;
1407 struct wnd_bitmap
*wnd
= &sbi
->used
.bitmap
;
1408 u32 wbits
= 8 * sb
->s_blocksize
;
1409 CLST len
= 0, lcn
= 0, done
= 0;
1410 CLST minlen
= bytes_to_cluster(sbi
, range
->minlen
);
1411 CLST lcn_from
= bytes_to_cluster(sbi
, range
->start
);
1412 size_t iw
= lcn_from
>> (sb
->s_blocksize_bits
+ 3);
1413 u32 wbit
= lcn_from
& (wbits
- 1);
1420 if (range
->len
== (u64
)-1)
1421 lcn_to
= wnd
->nbits
;
1423 lcn_to
= bytes_to_cluster(sbi
, range
->start
+ range
->len
);
1425 down_read_nested(&wnd
->rw_lock
, BITMAP_MUTEX_CLUSTERS
);
1427 for (; iw
< wnd
->nwnd
; iw
++, wbit
= 0) {
1428 CLST lcn_wnd
= iw
* wbits
;
1429 struct buffer_head
*bh
;
1431 if (lcn_wnd
> lcn_to
)
1434 if (!wnd
->free_bits
[iw
])
1437 if (iw
+ 1 == wnd
->nwnd
)
1438 wbits
= wnd
->bits_last
;
1440 if (lcn_wnd
+ wbits
> lcn_to
)
1441 wbits
= lcn_to
- lcn_wnd
;
1443 bh
= wnd_map(wnd
, iw
);
1449 buf
= (ulong
*)bh
->b_data
;
1451 for (; wbit
< wbits
; wbit
++) {
1452 if (!test_bit(wbit
, buf
)) {
1454 lcn
= lcn_wnd
+ wbit
;
1458 if (len
>= minlen
) {
1459 err
= ntfs_discard(sbi
, lcn
, len
);
1469 /* Process the last fragment. */
1470 if (len
>= minlen
) {
1471 err
= ntfs_discard(sbi
, lcn
, len
);
1478 range
->len
= (u64
)done
<< sbi
->cluster_bits
;
1480 up_read(&wnd
->rw_lock
);