diff options
Diffstat (limited to 'fs/ntfs3/run.c')
| -rw-r--r-- | fs/ntfs3/run.c | 1169 |
1 files changed, 1169 insertions, 0 deletions
diff --git a/fs/ntfs3/run.c b/fs/ntfs3/run.c new file mode 100644 index 0000000000..cb8cf01611 --- /dev/null +++ b/fs/ntfs3/run.c @@ -0,0 +1,1169 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * + * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved. + * + * TODO: try to use extents tree (instead of array) + */ + +#include <linux/blkdev.h> +#include <linux/fs.h> +#include <linux/log2.h> + +#include "debug.h" +#include "ntfs.h" +#include "ntfs_fs.h" + +/* runs_tree is a continues memory. Try to avoid big size. */ +#define NTFS3_RUN_MAX_BYTES 0x10000 + +struct ntfs_run { + CLST vcn; /* Virtual cluster number. */ + CLST len; /* Length in clusters. */ + CLST lcn; /* Logical cluster number. */ +}; + +/* + * run_lookup - Lookup the index of a MCB entry that is first <= vcn. + * + * Case of success it will return non-zero value and set + * @index parameter to index of entry been found. + * Case of entry missing from list 'index' will be set to + * point to insertion position for the entry question. + */ +static bool run_lookup(const struct runs_tree *run, CLST vcn, size_t *index) +{ + size_t min_idx, max_idx, mid_idx; + struct ntfs_run *r; + + if (!run->count) { + *index = 0; + return false; + } + + min_idx = 0; + max_idx = run->count - 1; + + /* Check boundary cases specially, 'cause they cover the often requests. */ + r = run->runs; + if (vcn < r->vcn) { + *index = 0; + return false; + } + + if (vcn < r->vcn + r->len) { + *index = 0; + return true; + } + + r += max_idx; + if (vcn >= r->vcn + r->len) { + *index = run->count; + return false; + } + + if (vcn >= r->vcn) { + *index = max_idx; + return true; + } + + do { + mid_idx = min_idx + ((max_idx - min_idx) >> 1); + r = run->runs + mid_idx; + + if (vcn < r->vcn) { + max_idx = mid_idx - 1; + if (!mid_idx) + break; + } else if (vcn >= r->vcn + r->len) { + min_idx = mid_idx + 1; + } else { + *index = mid_idx; + return true; + } + } while (min_idx <= max_idx); + + *index = max_idx + 1; + return false; +} + +/* + * run_consolidate - Consolidate runs starting from a given one. + */ +static void run_consolidate(struct runs_tree *run, size_t index) +{ + size_t i; + struct ntfs_run *r = run->runs + index; + + while (index + 1 < run->count) { + /* + * I should merge current run with next + * if start of the next run lies inside one being tested. + */ + struct ntfs_run *n = r + 1; + CLST end = r->vcn + r->len; + CLST dl; + + /* Stop if runs are not aligned one to another. */ + if (n->vcn > end) + break; + + dl = end - n->vcn; + + /* + * If range at index overlaps with next one + * then I will either adjust it's start position + * or (if completely matches) dust remove one from the list. + */ + if (dl > 0) { + if (n->len <= dl) + goto remove_next_range; + + n->len -= dl; + n->vcn += dl; + if (n->lcn != SPARSE_LCN) + n->lcn += dl; + dl = 0; + } + + /* + * Stop if sparse mode does not match + * both current and next runs. + */ + if ((n->lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) { + index += 1; + r = n; + continue; + } + + /* + * Check if volume block + * of a next run lcn does not match + * last volume block of the current run. + */ + if (n->lcn != SPARSE_LCN && n->lcn != r->lcn + r->len) + break; + + /* + * Next and current are siblings. + * Eat/join. + */ + r->len += n->len - dl; + +remove_next_range: + i = run->count - (index + 1); + if (i > 1) + memmove(n, n + 1, sizeof(*n) * (i - 1)); + + run->count -= 1; + } +} + +/* + * run_is_mapped_full + * + * Return: True if range [svcn - evcn] is mapped. + */ +bool run_is_mapped_full(const struct runs_tree *run, CLST svcn, CLST evcn) +{ + size_t i; + const struct ntfs_run *r, *end; + CLST next_vcn; + + if (!run_lookup(run, svcn, &i)) + return false; + + end = run->runs + run->count; + r = run->runs + i; + + for (;;) { + next_vcn = r->vcn + r->len; + if (next_vcn > evcn) + return true; + + if (++r >= end) + return false; + + if (r->vcn != next_vcn) + return false; + } +} + +bool run_lookup_entry(const struct runs_tree *run, CLST vcn, CLST *lcn, + CLST *len, size_t *index) +{ + size_t idx; + CLST gap; + struct ntfs_run *r; + + /* Fail immediately if nrun was not touched yet. */ + if (!run->runs) + return false; + + if (!run_lookup(run, vcn, &idx)) + return false; + + r = run->runs + idx; + + if (vcn >= r->vcn + r->len) + return false; + + gap = vcn - r->vcn; + if (r->len <= gap) + return false; + + *lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + gap); + + if (len) + *len = r->len - gap; + if (index) + *index = idx; + + return true; +} + +/* + * run_truncate_head - Decommit the range before vcn. + */ +void run_truncate_head(struct runs_tree *run, CLST vcn) +{ + size_t index; + struct ntfs_run *r; + + if (run_lookup(run, vcn, &index)) { + r = run->runs + index; + + if (vcn > r->vcn) { + CLST dlen = vcn - r->vcn; + + r->vcn = vcn; + r->len -= dlen; + if (r->lcn != SPARSE_LCN) + r->lcn += dlen; + } + + if (!index) + return; + } + r = run->runs; + memmove(r, r + index, sizeof(*r) * (run->count - index)); + + run->count -= index; + + if (!run->count) { + kvfree(run->runs); + run->runs = NULL; + run->allocated = 0; + } +} + +/* + * run_truncate - Decommit the range after vcn. + */ +void run_truncate(struct runs_tree *run, CLST vcn) +{ + size_t index; + + /* + * If I hit the range then + * I have to truncate one. + * If range to be truncated is becoming empty + * then it will entirely be removed. + */ + if (run_lookup(run, vcn, &index)) { + struct ntfs_run *r = run->runs + index; + + r->len = vcn - r->vcn; + + if (r->len > 0) + index += 1; + } + + /* + * At this point 'index' is set to position that + * should be thrown away (including index itself) + * Simple one - just set the limit. + */ + run->count = index; + + /* Do not reallocate array 'runs'. Only free if possible. */ + if (!index) { + kvfree(run->runs); + run->runs = NULL; + run->allocated = 0; + } +} + +/* + * run_truncate_around - Trim head and tail if necessary. + */ +void run_truncate_around(struct runs_tree *run, CLST vcn) +{ + run_truncate_head(run, vcn); + + if (run->count >= NTFS3_RUN_MAX_BYTES / sizeof(struct ntfs_run) / 2) + run_truncate(run, (run->runs + (run->count >> 1))->vcn); +} + +/* + * run_add_entry + * + * Sets location to known state. + * Run to be added may overlap with existing location. + * + * Return: false if of memory. + */ +bool run_add_entry(struct runs_tree *run, CLST vcn, CLST lcn, CLST len, + bool is_mft) +{ + size_t used, index; + struct ntfs_run *r; + bool inrange; + CLST tail_vcn = 0, tail_len = 0, tail_lcn = 0; + bool should_add_tail = false; + + /* + * Lookup the insertion point. + * + * Execute bsearch for the entry containing + * start position question. + */ + inrange = run_lookup(run, vcn, &index); + + /* + * Shortcut here would be case of + * range not been found but one been added + * continues previous run. + * This case I can directly make use of + * existing range as my start point. + */ + if (!inrange && index > 0) { + struct ntfs_run *t = run->runs + index - 1; + + if (t->vcn + t->len == vcn && + (t->lcn == SPARSE_LCN) == (lcn == SPARSE_LCN) && + (lcn == SPARSE_LCN || lcn == t->lcn + t->len)) { + inrange = true; + index -= 1; + } + } + + /* + * At this point 'index' either points to the range + * containing start position or to the insertion position + * for a new range. + * So first let's check if range I'm probing is here already. + */ + if (!inrange) { +requires_new_range: + /* + * Range was not found. + * Insert at position 'index' + */ + used = run->count * sizeof(struct ntfs_run); + + /* + * Check allocated space. + * If one is not enough to get one more entry + * then it will be reallocated. + */ + if (run->allocated < used + sizeof(struct ntfs_run)) { + size_t bytes; + struct ntfs_run *new_ptr; + + /* Use power of 2 for 'bytes'. */ + if (!used) { + bytes = 64; + } else if (used <= 16 * PAGE_SIZE) { + if (is_power_of_2(run->allocated)) + bytes = run->allocated << 1; + else + bytes = (size_t)1 + << (2 + blksize_bits(used)); + } else { + bytes = run->allocated + (16 * PAGE_SIZE); + } + + WARN_ON(!is_mft && bytes > NTFS3_RUN_MAX_BYTES); + + new_ptr = kvmalloc(bytes, GFP_KERNEL); + + if (!new_ptr) + return false; + + r = new_ptr + index; + memcpy(new_ptr, run->runs, + index * sizeof(struct ntfs_run)); + memcpy(r + 1, run->runs + index, + sizeof(struct ntfs_run) * (run->count - index)); + + kvfree(run->runs); + run->runs = new_ptr; + run->allocated = bytes; + + } else { + size_t i = run->count - index; + + r = run->runs + index; + + /* memmove appears to be a bottle neck here... */ + if (i > 0) + memmove(r + 1, r, sizeof(struct ntfs_run) * i); + } + + r->vcn = vcn; + r->lcn = lcn; + r->len = len; + run->count += 1; + } else { + r = run->runs + index; + + /* + * If one of ranges was not allocated then we + * have to split location we just matched and + * insert current one. + * A common case this requires tail to be reinserted + * a recursive call. + */ + if (((lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) || + (lcn != SPARSE_LCN && lcn != r->lcn + (vcn - r->vcn))) { + CLST to_eat = vcn - r->vcn; + CLST Tovcn = to_eat + len; + + should_add_tail = Tovcn < r->len; + + if (should_add_tail) { + tail_lcn = r->lcn == SPARSE_LCN ? + SPARSE_LCN : + (r->lcn + Tovcn); + tail_vcn = r->vcn + Tovcn; + tail_len = r->len - Tovcn; + } + + if (to_eat > 0) { + r->len = to_eat; + inrange = false; + index += 1; + goto requires_new_range; + } + + /* lcn should match one were going to add. */ + r->lcn = lcn; + } + + /* + * If existing range fits then were done. + * Otherwise extend found one and fall back to range jocode. + */ + if (r->vcn + r->len < vcn + len) + r->len += len - ((r->vcn + r->len) - vcn); + } + + /* + * And normalize it starting from insertion point. + * It's possible that no insertion needed case if + * start point lies within the range of an entry + * that 'index' points to. + */ + if (inrange && index > 0) + index -= 1; + run_consolidate(run, index); + run_consolidate(run, index + 1); + + /* + * A special case. + * We have to add extra range a tail. + */ + if (should_add_tail && + !run_add_entry(run, tail_vcn, tail_lcn, tail_len, is_mft)) + return false; + + return true; +} + +/* run_collapse_range + * + * Helper for attr_collapse_range(), + * which is helper for fallocate(collapse_range). + */ +bool run_collapse_range(struct runs_tree *run, CLST vcn, CLST len) +{ + size_t index, eat; + struct ntfs_run *r, *e, *eat_start, *eat_end; + CLST end; + + if (WARN_ON(!run_lookup(run, vcn, &index))) + return true; /* Should never be here. */ + + e = run->runs + run->count; + r = run->runs + index; + end = vcn + len; + + if (vcn > r->vcn) { + if (r->vcn + r->len <= end) { + /* Collapse tail of run .*/ + r->len = vcn - r->vcn; + } else if (r->lcn == SPARSE_LCN) { + /* Collapse a middle part of sparsed run. */ + r->len -= len; + } else { + /* Collapse a middle part of normal run, split. */ + if (!run_add_entry(run, vcn, SPARSE_LCN, len, false)) + return false; + return run_collapse_range(run, vcn, len); + } + + r += 1; + } + + eat_start = r; + eat_end = r; + + for (; r < e; r++) { + CLST d; + + if (r->vcn >= end) { + r->vcn -= len; + continue; + } + + if (r->vcn + r->len <= end) { + /* Eat this run. */ + eat_end = r + 1; + continue; + } + + d = end - r->vcn; + if (r->lcn != SPARSE_LCN) + r->lcn += d; + r->len -= d; + r->vcn -= len - d; + } + + eat = eat_end - eat_start; + memmove(eat_start, eat_end, (e - eat_end) * sizeof(*r)); + run->count -= eat; + + return true; +} + +/* run_insert_range + * + * Helper for attr_insert_range(), + * which is helper for fallocate(insert_range). + */ +bool run_insert_range(struct runs_tree *run, CLST vcn, CLST len) +{ + size_t index; + struct ntfs_run *r, *e; + + if (WARN_ON(!run_lookup(run, vcn, &index))) + return false; /* Should never be here. */ + + e = run->runs + run->count; + r = run->runs + index; + + if (vcn > r->vcn) + r += 1; + + for (; r < e; r++) + r->vcn += len; + + r = run->runs + index; + + if (vcn > r->vcn) { + /* split fragment. */ + CLST len1 = vcn - r->vcn; + CLST len2 = r->len - len1; + CLST lcn2 = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len1); + + r->len = len1; + + if (!run_add_entry(run, vcn + len, lcn2, len2, false)) + return false; + } + + if (!run_add_entry(run, vcn, SPARSE_LCN, len, false)) + return false; + + return true; +} + +/* + * run_get_entry - Return index-th mapped region. + */ +bool run_get_entry(const struct runs_tree *run, size_t index, CLST *vcn, + CLST *lcn, CLST *len) +{ + const struct ntfs_run *r; + + if (index >= run->count) + return false; + + r = run->runs + index; + + if (!r->len) + return false; + + if (vcn) + *vcn = r->vcn; + if (lcn) + *lcn = r->lcn; + if (len) + *len = r->len; + return true; +} + +/* + * run_packed_size - Calculate the size of packed int64. + */ +#ifdef __BIG_ENDIAN +static inline int run_packed_size(const s64 n) +{ + const u8 *p = (const u8 *)&n + sizeof(n) - 1; + + if (n >= 0) { + if (p[-7] || p[-6] || p[-5] || p[-4]) + p -= 4; + if (p[-3] || p[-2]) + p -= 2; + if (p[-1]) + p -= 1; + if (p[0] & 0x80) + p -= 1; + } else { + if (p[-7] != 0xff || p[-6] != 0xff || p[-5] != 0xff || + p[-4] != 0xff) + p -= 4; + if (p[-3] != 0xff || p[-2] != 0xff) + p -= 2; + if (p[-1] != 0xff) + p -= 1; + if (!(p[0] & 0x80)) + p -= 1; + } + return (const u8 *)&n + sizeof(n) - p; +} + +/* Full trusted function. It does not check 'size' for errors. */ +static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v) +{ + const u8 *p = (u8 *)&v; + + switch (size) { + case 8: + run_buf[7] = p[0]; + fallthrough; + case 7: + run_buf[6] = p[1]; + fallthrough; + case 6: + run_buf[5] = p[2]; + fallthrough; + case 5: + run_buf[4] = p[3]; + fallthrough; + case 4: + run_buf[3] = p[4]; + fallthrough; + case 3: + run_buf[2] = p[5]; + fallthrough; + case 2: + run_buf[1] = p[6]; + fallthrough; + case 1: + run_buf[0] = p[7]; + } +} + +/* Full trusted function. It does not check 'size' for errors. */ +static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v) +{ + u8 *p = (u8 *)&v; + + switch (size) { + case 8: + p[0] = run_buf[7]; + fallthrough; + case 7: + p[1] = run_buf[6]; + fallthrough; + case 6: + p[2] = run_buf[5]; + fallthrough; + case 5: + p[3] = run_buf[4]; + fallthrough; + case 4: + p[4] = run_buf[3]; + fallthrough; + case 3: + p[5] = run_buf[2]; + fallthrough; + case 2: + p[6] = run_buf[1]; + fallthrough; + case 1: + p[7] = run_buf[0]; + } + return v; +} + +#else + +static inline int run_packed_size(const s64 n) +{ + const u8 *p = (const u8 *)&n; + + if (n >= 0) { + if (p[7] || p[6] || p[5] || p[4]) + p += 4; + if (p[3] || p[2]) + p += 2; + if (p[1]) + p += 1; + if (p[0] & 0x80) + p += 1; + } else { + if (p[7] != 0xff || p[6] != 0xff || p[5] != 0xff || + p[4] != 0xff) + p += 4; + if (p[3] != 0xff || p[2] != 0xff) + p += 2; + if (p[1] != 0xff) + p += 1; + if (!(p[0] & 0x80)) + p += 1; + } + + return 1 + p - (const u8 *)&n; +} + +/* Full trusted function. It does not check 'size' for errors. */ +static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v) +{ + const u8 *p = (u8 *)&v; + + /* memcpy( run_buf, &v, size); Is it faster? */ + switch (size) { + case 8: + run_buf[7] = p[7]; + fallthrough; + case 7: + run_buf[6] = p[6]; + fallthrough; + case 6: + run_buf[5] = p[5]; + fallthrough; + case 5: + run_buf[4] = p[4]; + fallthrough; + case 4: + run_buf[3] = p[3]; + fallthrough; + case 3: + run_buf[2] = p[2]; + fallthrough; + case 2: + run_buf[1] = p[1]; + fallthrough; + case 1: + run_buf[0] = p[0]; + } +} + +/* full trusted function. It does not check 'size' for errors */ +static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v) +{ + u8 *p = (u8 *)&v; + + /* memcpy( &v, run_buf, size); Is it faster? */ + switch (size) { + case 8: + p[7] = run_buf[7]; + fallthrough; + case 7: + p[6] = run_buf[6]; + fallthrough; + case 6: + p[5] = run_buf[5]; + fallthrough; + case 5: + p[4] = run_buf[4]; + fallthrough; + case 4: + p[3] = run_buf[3]; + fallthrough; + case 3: + p[2] = run_buf[2]; + fallthrough; + case 2: + p[1] = run_buf[1]; + fallthrough; + case 1: + p[0] = run_buf[0]; + } + return v; +} +#endif + +/* + * run_pack - Pack runs into buffer. + * + * packed_vcns - How much runs we have packed. + * packed_size - How much bytes we have used run_buf. + */ +int run_pack(const struct runs_tree *run, CLST svcn, CLST len, u8 *run_buf, + u32 run_buf_size, CLST *packed_vcns) +{ + CLST next_vcn, vcn, lcn; + CLST prev_lcn = 0; + CLST evcn1 = svcn + len; + const struct ntfs_run *r, *r_end; + int packed_size = 0; + size_t i; + s64 dlcn; + int offset_size, size_size, tmp; + + *packed_vcns = 0; + + if (!len) + goto out; + + /* Check all required entries [svcn, encv1) available. */ + if (!run_lookup(run, svcn, &i)) + return -ENOENT; + + r_end = run->runs + run->count; + r = run->runs + i; + + for (next_vcn = r->vcn + r->len; next_vcn < evcn1; + next_vcn = r->vcn + r->len) { + if (++r >= r_end || r->vcn != next_vcn) + return -ENOENT; + } + + /* Repeat cycle above and pack runs. Assume no errors. */ + r = run->runs + i; + len = svcn - r->vcn; + vcn = svcn; + lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len); + len = r->len - len; + + for (;;) { + next_vcn = vcn + len; + if (next_vcn > evcn1) + len = evcn1 - vcn; + + /* How much bytes required to pack len. */ + size_size = run_packed_size(len); + + /* offset_size - How much bytes is packed dlcn. */ + if (lcn == SPARSE_LCN) { + offset_size = 0; + dlcn = 0; + } else { + /* NOTE: lcn can be less than prev_lcn! */ + dlcn = (s64)lcn - prev_lcn; + offset_size = run_packed_size(dlcn); + prev_lcn = lcn; + } + + tmp = run_buf_size - packed_size - 2 - offset_size; + if (tmp <= 0) + goto out; + + /* Can we store this entire run. */ + if (tmp < size_size) + goto out; + + if (run_buf) { + /* Pack run header. */ + run_buf[0] = ((u8)(size_size | (offset_size << 4))); + run_buf += 1; + + /* Pack the length of run. */ + run_pack_s64(run_buf, size_size, len); + + run_buf += size_size; + /* Pack the offset from previous LCN. */ + run_pack_s64(run_buf, offset_size, dlcn); + run_buf += offset_size; + } + + packed_size += 1 + offset_size + size_size; + *packed_vcns += len; + + if (packed_size + 1 >= run_buf_size || next_vcn >= evcn1) + goto out; + + r += 1; + vcn = r->vcn; + lcn = r->lcn; + len = r->len; + } + +out: + /* Store last zero. */ + if (run_buf) + run_buf[0] = 0; + + return packed_size + 1; +} + +/* + * run_unpack - Unpack packed runs from @run_buf. + * + * Return: Error if negative, or real used bytes. + */ +int run_unpack(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino, + CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf, + int run_buf_size) +{ + u64 prev_lcn, vcn64, lcn, next_vcn; + const u8 *run_last, *run_0; + bool is_mft = ino == MFT_REC_MFT; + + if (run_buf_size < 0) + return -EINVAL; + + /* Check for empty. */ + if (evcn + 1 == svcn) + return 0; + + if (evcn < svcn) + return -EINVAL; + + run_0 = run_buf; + run_last = run_buf + run_buf_size; + prev_lcn = 0; + vcn64 = svcn; + + /* Read all runs the chain. */ + /* size_size - How much bytes is packed len. */ + while (run_buf < run_last) { + /* size_size - How much bytes is packed len. */ + u8 size_size = *run_buf & 0xF; + /* offset_size - How much bytes is packed dlcn. */ + u8 offset_size = *run_buf++ >> 4; + u64 len; + + if (!size_size) + break; + + /* + * Unpack runs. + * NOTE: Runs are stored little endian order + * "len" is unsigned value, "dlcn" is signed. + * Large positive number requires to store 5 bytes + * e.g.: 05 FF 7E FF FF 00 00 00 + */ + if (size_size > 8) + return -EINVAL; + + len = run_unpack_s64(run_buf, size_size, 0); + /* Skip size_size. */ + run_buf += size_size; + + if (!len) + return -EINVAL; + + if (!offset_size) + lcn = SPARSE_LCN64; + else if (offset_size <= 8) { + s64 dlcn; + + /* Initial value of dlcn is -1 or 0. */ + dlcn = (run_buf[offset_size - 1] & 0x80) ? (s64)-1 : 0; + dlcn = run_unpack_s64(run_buf, offset_size, dlcn); + /* Skip offset_size. */ + run_buf += offset_size; + + if (!dlcn) + return -EINVAL; + lcn = prev_lcn + dlcn; + prev_lcn = lcn; + } else + return -EINVAL; + + next_vcn = vcn64 + len; + /* Check boundary. */ + if (next_vcn > evcn + 1) + return -EINVAL; + +#ifndef CONFIG_NTFS3_64BIT_CLUSTER + if (next_vcn > 0x100000000ull || (lcn + len) > 0x100000000ull) { + ntfs_err( + sbi->sb, + "This driver is compiled without CONFIG_NTFS3_64BIT_CLUSTER (like windows driver).\n" + "Volume contains 64 bits run: vcn %llx, lcn %llx, len %llx.\n" + "Activate CONFIG_NTFS3_64BIT_CLUSTER to process this case", + vcn64, lcn, len); + return -EOPNOTSUPP; + } +#endif + if (lcn != SPARSE_LCN64 && lcn + len > sbi->used.bitmap.nbits) { + /* LCN range is out of volume. */ + return -EINVAL; + } + + if (!run) + ; /* Called from check_attr(fslog.c) to check run. */ + else if (run == RUN_DEALLOCATE) { + /* + * Called from ni_delete_all to free clusters + * without storing in run. + */ + if (lcn != SPARSE_LCN64) + mark_as_free_ex(sbi, lcn, len, true); + } else if (vcn64 >= vcn) { + if (!run_add_entry(run, vcn64, lcn, len, is_mft)) + return -ENOMEM; + } else if (next_vcn > vcn) { + u64 dlen = vcn - vcn64; + + if (!run_add_entry(run, vcn, lcn + dlen, len - dlen, + is_mft)) + return -ENOMEM; + } + + vcn64 = next_vcn; + } + + if (vcn64 != evcn + 1) { + /* Not expected length of unpacked runs. */ + return -EINVAL; + } + + return run_buf - run_0; +} + +#ifdef NTFS3_CHECK_FREE_CLST +/* + * run_unpack_ex - Unpack packed runs from "run_buf". + * + * Checks unpacked runs to be used in bitmap. + * + * Return: Error if negative, or real used bytes. + */ +int run_unpack_ex(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino, + CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf, + int run_buf_size) +{ + int ret, err; + CLST next_vcn, lcn, len; + size_t index; + bool ok; + struct wnd_bitmap *wnd; + + ret = run_unpack(run, sbi, ino, svcn, evcn, vcn, run_buf, run_buf_size); + if (ret <= 0) + return ret; + + if (!sbi->used.bitmap.sb || !run || run == RUN_DEALLOCATE) + return ret; + + if (ino == MFT_REC_BADCLUST) + return ret; + + next_vcn = vcn = svcn; + wnd = &sbi->used.bitmap; + + for (ok = run_lookup_entry(run, vcn, &lcn, &len, &index); + next_vcn <= evcn; + ok = run_get_entry(run, ++index, &vcn, &lcn, &len)) { + if (!ok || next_vcn != vcn) + return -EINVAL; + + next_vcn = vcn + len; + + if (lcn == SPARSE_LCN) + continue; + + if (sbi->flags & NTFS_FLAGS_NEED_REPLAY) + continue; + + down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS); + /* Check for free blocks. */ + ok = wnd_is_used(wnd, lcn, len); + up_read(&wnd->rw_lock); + if (ok) + continue; + + /* Looks like volume is corrupted. */ + ntfs_set_state(sbi, NTFS_DIRTY_ERROR); + + if (down_write_trylock(&wnd->rw_lock)) { + /* Mark all zero bits as used in range [lcn, lcn+len). */ + size_t done; + err = wnd_set_used_safe(wnd, lcn, len, &done); + up_write(&wnd->rw_lock); + if (err) + return err; + } + } + + return ret; +} +#endif + +/* + * run_get_highest_vcn + * + * Return the highest vcn from a mapping pairs array + * it used while replaying log file. + */ +int run_get_highest_vcn(CLST vcn, const u8 *run_buf, u64 *highest_vcn) +{ + u64 vcn64 = vcn; + u8 size_size; + + while ((size_size = *run_buf & 0xF)) { + u8 offset_size = *run_buf++ >> 4; + u64 len; + + if (size_size > 8 || offset_size > 8) + return -EINVAL; + + len = run_unpack_s64(run_buf, size_size, 0); + if (!len) + return -EINVAL; + + run_buf += size_size + offset_size; + vcn64 += len; + +#ifndef CONFIG_NTFS3_64BIT_CLUSTER + if (vcn64 > 0x100000000ull) + return -EINVAL; +#endif + } + + *highest_vcn = vcn64 - 1; + return 0; +} + +/* + * run_clone + * + * Make a copy of run + */ +int run_clone(const struct runs_tree *run, struct runs_tree *new_run) +{ + size_t bytes = run->count * sizeof(struct ntfs_run); + + if (bytes > new_run->allocated) { + struct ntfs_run *new_ptr = kvmalloc(bytes, GFP_KERNEL); + + if (!new_ptr) + return -ENOMEM; + + kvfree(new_run->runs); + new_run->runs = new_ptr; + new_run->allocated = bytes; + } + + memcpy(new_run->runs, run->runs, bytes); + new_run->count = run->count; + return 0; +} |