]>
git.proxmox.com Git - mirror_ubuntu-jammy-kernel.git/blob - fs/ntfs3/run.c
1 // SPDX-License-Identifier: GPL-2.0
4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
6 * TODO: try to use extents tree (instead of array)
9 #include <linux/blkdev.h>
11 #include <linux/log2.h>
17 /* runs_tree is a continues memory. Try to avoid big size. */
18 #define NTFS3_RUN_MAX_BYTES 0x10000
21 CLST vcn
; /* Virtual cluster number. */
22 CLST len
; /* Length in clusters. */
23 CLST lcn
; /* Logical cluster number. */
27 * run_lookup - Lookup the index of a MCB entry that is first <= vcn.
29 * Case of success it will return non-zero value and set
30 * @index parameter to index of entry been found.
31 * Case of entry missing from list 'index' will be set to
32 * point to insertion position for the entry question.
34 bool run_lookup(const struct runs_tree
*run
, CLST vcn
, size_t *index
)
36 size_t min_idx
, max_idx
, mid_idx
;
45 max_idx
= run
->count
- 1;
47 /* Check boundary cases specially, 'cause they cover the often requests. */
54 if (vcn
< r
->vcn
+ r
->len
) {
60 if (vcn
>= r
->vcn
+ r
->len
) {
71 mid_idx
= min_idx
+ ((max_idx
- min_idx
) >> 1);
72 r
= run
->runs
+ mid_idx
;
75 max_idx
= mid_idx
- 1;
78 } else if (vcn
>= r
->vcn
+ r
->len
) {
79 min_idx
= mid_idx
+ 1;
84 } while (min_idx
<= max_idx
);
91 * run_consolidate - Consolidate runs starting from a given one.
93 static void run_consolidate(struct runs_tree
*run
, size_t index
)
96 struct ntfs_run
*r
= run
->runs
+ index
;
98 while (index
+ 1 < run
->count
) {
100 * I should merge current run with next
101 * if start of the next run lies inside one being tested.
103 struct ntfs_run
*n
= r
+ 1;
104 CLST end
= r
->vcn
+ r
->len
;
107 /* Stop if runs are not aligned one to another. */
114 * If range at index overlaps with next one
115 * then I will either adjust it's start position
116 * or (if completely matches) dust remove one from the list.
120 goto remove_next_range
;
124 if (n
->lcn
!= SPARSE_LCN
)
130 * Stop if sparse mode does not match
131 * both current and next runs.
133 if ((n
->lcn
== SPARSE_LCN
) != (r
->lcn
== SPARSE_LCN
)) {
140 * Check if volume block
141 * of a next run lcn does not match
142 * last volume block of the current run.
144 if (n
->lcn
!= SPARSE_LCN
&& n
->lcn
!= r
->lcn
+ r
->len
)
148 * Next and current are siblings.
151 r
->len
+= n
->len
- dl
;
154 i
= run
->count
- (index
+ 1);
156 memmove(n
, n
+ 1, sizeof(*n
) * (i
- 1));
165 * Return: True if range [svcn - evcn] is mapped.
167 bool run_is_mapped_full(const struct runs_tree
*run
, CLST svcn
, CLST evcn
)
170 const struct ntfs_run
*r
, *end
;
173 if (!run_lookup(run
, svcn
, &i
))
176 end
= run
->runs
+ run
->count
;
180 next_vcn
= r
->vcn
+ r
->len
;
187 if (r
->vcn
!= next_vcn
)
192 bool run_lookup_entry(const struct runs_tree
*run
, CLST vcn
, CLST
*lcn
,
193 CLST
*len
, size_t *index
)
199 /* Fail immediately if nrun was not touched yet. */
203 if (!run_lookup(run
, vcn
, &idx
))
208 if (vcn
>= r
->vcn
+ r
->len
)
215 *lcn
= r
->lcn
== SPARSE_LCN
? SPARSE_LCN
: (r
->lcn
+ gap
);
226 * run_truncate_head - Decommit the range before vcn.
228 void run_truncate_head(struct runs_tree
*run
, CLST vcn
)
233 if (run_lookup(run
, vcn
, &index
)) {
234 r
= run
->runs
+ index
;
237 CLST dlen
= vcn
- r
->vcn
;
241 if (r
->lcn
!= SPARSE_LCN
)
249 memmove(r
, r
+ index
, sizeof(*r
) * (run
->count
- index
));
261 * run_truncate - Decommit the range after vcn.
263 void run_truncate(struct runs_tree
*run
, CLST vcn
)
268 * If I hit the range then
269 * I have to truncate one.
270 * If range to be truncated is becoming empty
271 * then it will entirely be removed.
273 if (run_lookup(run
, vcn
, &index
)) {
274 struct ntfs_run
*r
= run
->runs
+ index
;
276 r
->len
= vcn
- r
->vcn
;
283 * At this point 'index' is set to position that
284 * should be thrown away (including index itself)
285 * Simple one - just set the limit.
289 /* Do not reallocate array 'runs'. Only free if possible. */
298 * run_truncate_around - Trim head and tail if necessary.
300 void run_truncate_around(struct runs_tree
*run
, CLST vcn
)
302 run_truncate_head(run
, vcn
);
304 if (run
->count
>= NTFS3_RUN_MAX_BYTES
/ sizeof(struct ntfs_run
) / 2)
305 run_truncate(run
, (run
->runs
+ (run
->count
>> 1))->vcn
);
311 * Sets location to known state.
312 * Run to be added may overlap with existing location.
314 * Return: false if of memory.
316 bool run_add_entry(struct runs_tree
*run
, CLST vcn
, CLST lcn
, CLST len
,
322 CLST tail_vcn
= 0, tail_len
= 0, tail_lcn
= 0;
323 bool should_add_tail
= false;
326 * Lookup the insertion point.
328 * Execute bsearch for the entry containing
329 * start position question.
331 inrange
= run_lookup(run
, vcn
, &index
);
334 * Shortcut here would be case of
335 * range not been found but one been added
336 * continues previous run.
337 * This case I can directly make use of
338 * existing range as my start point.
340 if (!inrange
&& index
> 0) {
341 struct ntfs_run
*t
= run
->runs
+ index
- 1;
343 if (t
->vcn
+ t
->len
== vcn
&&
344 (t
->lcn
== SPARSE_LCN
) == (lcn
== SPARSE_LCN
) &&
345 (lcn
== SPARSE_LCN
|| lcn
== t
->lcn
+ t
->len
)) {
352 * At this point 'index' either points to the range
353 * containing start position or to the insertion position
355 * So first let's check if range I'm probing is here already.
360 * Range was not found.
361 * Insert at position 'index'
363 used
= run
->count
* sizeof(struct ntfs_run
);
366 * Check allocated space.
367 * If one is not enough to get one more entry
368 * then it will be reallocated.
370 if (run
->allocated
< used
+ sizeof(struct ntfs_run
)) {
372 struct ntfs_run
*new_ptr
;
374 /* Use power of 2 for 'bytes'. */
377 } else if (used
<= 16 * PAGE_SIZE
) {
378 if (is_power_of_2(run
->allocated
))
379 bytes
= run
->allocated
<< 1;
382 << (2 + blksize_bits(used
));
384 bytes
= run
->allocated
+ (16 * PAGE_SIZE
);
387 WARN_ON(!is_mft
&& bytes
> NTFS3_RUN_MAX_BYTES
);
389 new_ptr
= kvmalloc(bytes
, GFP_KERNEL
);
395 memcpy(new_ptr
, run
->runs
,
396 index
* sizeof(struct ntfs_run
));
397 memcpy(r
+ 1, run
->runs
+ index
,
398 sizeof(struct ntfs_run
) * (run
->count
- index
));
402 run
->allocated
= bytes
;
405 size_t i
= run
->count
- index
;
407 r
= run
->runs
+ index
;
409 /* memmove appears to be a bottle neck here... */
411 memmove(r
+ 1, r
, sizeof(struct ntfs_run
) * i
);
419 r
= run
->runs
+ index
;
422 * If one of ranges was not allocated then we
423 * have to split location we just matched and
424 * insert current one.
425 * A common case this requires tail to be reinserted
428 if (((lcn
== SPARSE_LCN
) != (r
->lcn
== SPARSE_LCN
)) ||
429 (lcn
!= SPARSE_LCN
&& lcn
!= r
->lcn
+ (vcn
- r
->vcn
))) {
430 CLST to_eat
= vcn
- r
->vcn
;
431 CLST Tovcn
= to_eat
+ len
;
433 should_add_tail
= Tovcn
< r
->len
;
435 if (should_add_tail
) {
436 tail_lcn
= r
->lcn
== SPARSE_LCN
439 tail_vcn
= r
->vcn
+ Tovcn
;
440 tail_len
= r
->len
- Tovcn
;
447 goto requires_new_range
;
450 /* lcn should match one were going to add. */
455 * If existing range fits then were done.
456 * Otherwise extend found one and fall back to range jocode.
458 if (r
->vcn
+ r
->len
< vcn
+ len
)
459 r
->len
+= len
- ((r
->vcn
+ r
->len
) - vcn
);
463 * And normalize it starting from insertion point.
464 * It's possible that no insertion needed case if
465 * start point lies within the range of an entry
466 * that 'index' points to.
468 if (inrange
&& index
> 0)
470 run_consolidate(run
, index
);
471 run_consolidate(run
, index
+ 1);
475 * We have to add extra range a tail.
477 if (should_add_tail
&&
478 !run_add_entry(run
, tail_vcn
, tail_lcn
, tail_len
, is_mft
))
484 /* run_collapse_range
486 * Helper for attr_collapse_range(),
487 * which is helper for fallocate(collapse_range).
489 bool run_collapse_range(struct runs_tree
*run
, CLST vcn
, CLST len
)
492 struct ntfs_run
*r
, *e
, *eat_start
, *eat_end
;
495 if (WARN_ON(!run_lookup(run
, vcn
, &index
)))
496 return true; /* Should never be here. */
498 e
= run
->runs
+ run
->count
;
499 r
= run
->runs
+ index
;
503 if (r
->vcn
+ r
->len
<= end
) {
504 /* Collapse tail of run .*/
505 r
->len
= vcn
- r
->vcn
;
506 } else if (r
->lcn
== SPARSE_LCN
) {
507 /* Collapse a middle part of sparsed run. */
510 /* Collapse a middle part of normal run, split. */
511 if (!run_add_entry(run
, vcn
, SPARSE_LCN
, len
, false))
513 return run_collapse_range(run
, vcn
, len
);
530 if (r
->vcn
+ r
->len
<= end
) {
537 if (r
->lcn
!= SPARSE_LCN
)
543 eat
= eat_end
- eat_start
;
544 memmove(eat_start
, eat_end
, (e
- eat_end
) * sizeof(*r
));
551 * run_get_entry - Return index-th mapped region.
553 bool run_get_entry(const struct runs_tree
*run
, size_t index
, CLST
*vcn
,
554 CLST
*lcn
, CLST
*len
)
556 const struct ntfs_run
*r
;
558 if (index
>= run
->count
)
561 r
= run
->runs
+ index
;
576 * run_packed_size - Calculate the size of packed int64.
579 static inline int run_packed_size(const s64 n
)
581 const u8
*p
= (const u8
*)&n
+ sizeof(n
) - 1;
584 if (p
[-7] || p
[-6] || p
[-5] || p
[-4])
593 if (p
[-7] != 0xff || p
[-6] != 0xff || p
[-5] != 0xff ||
596 if (p
[-3] != 0xff || p
[-2] != 0xff)
603 return (const u8
*)&n
+ sizeof(n
) - p
;
606 /* Full trusted function. It does not check 'size' for errors. */
607 static inline void run_pack_s64(u8
*run_buf
, u8 size
, s64 v
)
609 const u8
*p
= (u8
*)&v
;
638 /* Full trusted function. It does not check 'size' for errors. */
639 static inline s64
run_unpack_s64(const u8
*run_buf
, u8 size
, s64 v
)
673 static inline int run_packed_size(const s64 n
)
675 const u8
*p
= (const u8
*)&n
;
678 if (p
[7] || p
[6] || p
[5] || p
[4])
687 if (p
[7] != 0xff || p
[6] != 0xff || p
[5] != 0xff ||
690 if (p
[3] != 0xff || p
[2] != 0xff)
698 return 1 + p
- (const u8
*)&n
;
701 /* Full trusted function. It does not check 'size' for errors. */
702 static inline void run_pack_s64(u8
*run_buf
, u8 size
, s64 v
)
704 const u8
*p
= (u8
*)&v
;
706 /* memcpy( run_buf, &v, size); Is it faster? */
734 /* full trusted function. It does not check 'size' for errors */
735 static inline s64
run_unpack_s64(const u8
*run_buf
, u8 size
, s64 v
)
739 /* memcpy( &v, run_buf, size); Is it faster? */
770 * run_pack - Pack runs into buffer.
772 * packed_vcns - How much runs we have packed.
773 * packed_size - How much bytes we have used run_buf.
775 int run_pack(const struct runs_tree
*run
, CLST svcn
, CLST len
, u8
*run_buf
,
776 u32 run_buf_size
, CLST
*packed_vcns
)
778 CLST next_vcn
, vcn
, lcn
;
780 CLST evcn1
= svcn
+ len
;
785 int offset_size
, size_size
, tmp
;
787 next_vcn
= vcn
= svcn
;
794 ok
= run_lookup_entry(run
, vcn
, &lcn
, &len
, &i
);
803 next_vcn
= vcn
+ len
;
804 if (next_vcn
> evcn1
)
807 /* How much bytes required to pack len. */
808 size_size
= run_packed_size(len
);
810 /* offset_size - How much bytes is packed dlcn. */
811 if (lcn
== SPARSE_LCN
) {
815 /* NOTE: lcn can be less than prev_lcn! */
816 dlcn
= (s64
)lcn
- prev_lcn
;
817 offset_size
= run_packed_size(dlcn
);
821 tmp
= run_buf_size
- packed_size
- 2 - offset_size
;
825 /* Can we store this entire run. */
830 /* Pack run header. */
831 run_buf
[0] = ((u8
)(size_size
| (offset_size
<< 4)));
834 /* Pack the length of run. */
835 run_pack_s64(run_buf
, size_size
, len
);
837 run_buf
+= size_size
;
838 /* Pack the offset from previous LCN. */
839 run_pack_s64(run_buf
, offset_size
, dlcn
);
840 run_buf
+= offset_size
;
843 packed_size
+= 1 + offset_size
+ size_size
;
846 if (packed_size
+ 1 >= run_buf_size
|| next_vcn
>= evcn1
)
849 ok
= run_get_entry(run
, ++i
, &vcn
, &lcn
, &len
);
858 /* Store last zero. */
862 return packed_size
+ 1;
869 * run_unpack - Unpack packed runs from @run_buf.
871 * Return: Error if negative, or real used bytes.
873 int run_unpack(struct runs_tree
*run
, struct ntfs_sb_info
*sbi
, CLST ino
,
874 CLST svcn
, CLST evcn
, CLST vcn
, const u8
*run_buf
,
877 u64 prev_lcn
, vcn64
, lcn
, next_vcn
;
878 const u8
*run_last
, *run_0
;
879 bool is_mft
= ino
== MFT_REC_MFT
;
881 /* Check for empty. */
882 if (evcn
+ 1 == svcn
)
889 run_last
= run_buf
+ run_buf_size
;
893 /* Read all runs the chain. */
894 /* size_size - How much bytes is packed len. */
895 while (run_buf
< run_last
) {
896 /* size_size - How much bytes is packed len. */
897 u8 size_size
= *run_buf
& 0xF;
898 /* offset_size - How much bytes is packed dlcn. */
899 u8 offset_size
= *run_buf
++ >> 4;
907 * NOTE: Runs are stored little endian order
908 * "len" is unsigned value, "dlcn" is signed.
909 * Large positive number requires to store 5 bytes
910 * e.g.: 05 FF 7E FF FF 00 00 00
915 len
= run_unpack_s64(run_buf
, size_size
, 0);
916 /* Skip size_size. */
917 run_buf
+= size_size
;
924 else if (offset_size
<= 8) {
927 /* Initial value of dlcn is -1 or 0. */
928 dlcn
= (run_buf
[offset_size
- 1] & 0x80) ? (s64
)-1 : 0;
929 dlcn
= run_unpack_s64(run_buf
, offset_size
, dlcn
);
930 /* Skip offset_size. */
931 run_buf
+= offset_size
;
935 lcn
= prev_lcn
+ dlcn
;
940 next_vcn
= vcn64
+ len
;
941 /* Check boundary. */
942 if (next_vcn
> evcn
+ 1)
945 #ifndef CONFIG_NTFS3_64BIT_CLUSTER
946 if (next_vcn
> 0x100000000ull
|| (lcn
+ len
) > 0x100000000ull
) {
949 "This driver is compiled without CONFIG_NTFS3_64BIT_CLUSTER (like windows driver).\n"
950 "Volume contains 64 bits run: vcn %llx, lcn %llx, len %llx.\n"
951 "Activate CONFIG_NTFS3_64BIT_CLUSTER to process this case",
956 if (lcn
!= SPARSE_LCN64
&& lcn
+ len
> sbi
->used
.bitmap
.nbits
) {
957 /* LCN range is out of volume. */
962 ; /* Called from check_attr(fslog.c) to check run. */
963 else if (run
== RUN_DEALLOCATE
) {
965 * Called from ni_delete_all to free clusters
966 * without storing in run.
968 if (lcn
!= SPARSE_LCN64
)
969 mark_as_free_ex(sbi
, lcn
, len
, true);
970 } else if (vcn64
>= vcn
) {
971 if (!run_add_entry(run
, vcn64
, lcn
, len
, is_mft
))
973 } else if (next_vcn
> vcn
) {
974 u64 dlen
= vcn
- vcn64
;
976 if (!run_add_entry(run
, vcn
, lcn
+ dlen
, len
- dlen
,
984 if (vcn64
!= evcn
+ 1) {
985 /* Not expected length of unpacked runs. */
989 return run_buf
- run_0
;
992 #ifdef NTFS3_CHECK_FREE_CLST
994 * run_unpack_ex - Unpack packed runs from "run_buf".
996 * Checks unpacked runs to be used in bitmap.
998 * Return: Error if negative, or real used bytes.
1000 int run_unpack_ex(struct runs_tree
*run
, struct ntfs_sb_info
*sbi
, CLST ino
,
1001 CLST svcn
, CLST evcn
, CLST vcn
, const u8
*run_buf
,
1005 CLST next_vcn
, lcn
, len
;
1008 struct wnd_bitmap
*wnd
;
1010 ret
= run_unpack(run
, sbi
, ino
, svcn
, evcn
, vcn
, run_buf
, run_buf_size
);
1014 if (!sbi
->used
.bitmap
.sb
|| !run
|| run
== RUN_DEALLOCATE
)
1017 if (ino
== MFT_REC_BADCLUST
)
1020 next_vcn
= vcn
= svcn
;
1021 wnd
= &sbi
->used
.bitmap
;
1023 for (ok
= run_lookup_entry(run
, vcn
, &lcn
, &len
, &index
);
1025 ok
= run_get_entry(run
, ++index
, &vcn
, &lcn
, &len
)) {
1026 if (!ok
|| next_vcn
!= vcn
)
1029 next_vcn
= vcn
+ len
;
1031 if (lcn
== SPARSE_LCN
)
1034 if (sbi
->flags
& NTFS_FLAGS_NEED_REPLAY
)
1037 down_read_nested(&wnd
->rw_lock
, BITMAP_MUTEX_CLUSTERS
);
1038 /* Check for free blocks. */
1039 ok
= wnd_is_used(wnd
, lcn
, len
);
1040 up_read(&wnd
->rw_lock
);
1044 /* Looks like volume is corrupted. */
1045 ntfs_set_state(sbi
, NTFS_DIRTY_ERROR
);
1047 if (down_write_trylock(&wnd
->rw_lock
)) {
1048 /* Mark all zero bits as used in range [lcn, lcn+len). */
1049 CLST i
, lcn_f
= 0, len_f
= 0;
1052 for (i
= 0; i
< len
; i
++) {
1053 if (wnd_is_free(wnd
, lcn
+ i
, 1)) {
1058 err
= wnd_set_used(wnd
, lcn_f
, len_f
);
1066 err
= wnd_set_used(wnd
, lcn_f
, len_f
);
1068 up_write(&wnd
->rw_lock
);
1079 * run_get_highest_vcn
1081 * Return the highest vcn from a mapping pairs array
1082 * it used while replaying log file.
1084 int run_get_highest_vcn(CLST vcn
, const u8
*run_buf
, u64
*highest_vcn
)
1089 while ((size_size
= *run_buf
& 0xF)) {
1090 u8 offset_size
= *run_buf
++ >> 4;
1093 if (size_size
> 8 || offset_size
> 8)
1096 len
= run_unpack_s64(run_buf
, size_size
, 0);
1100 run_buf
+= size_size
+ offset_size
;
1103 #ifndef CONFIG_NTFS3_64BIT_CLUSTER
1104 if (vcn64
> 0x100000000ull
)
1109 *highest_vcn
= vcn64
- 1;