run.c

   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 *
   4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
   5 *
   6 * TODO: try to use extents tree (instead of array)
   7 */
   8
   9#include <linux/blkdev.h>
  10#include <linux/fs.h>
  11#include <linux/log2.h>
  12#include <linux/overflow.h>
  13
  14#include "debug.h"
  15#include "ntfs.h"
  16#include "ntfs_fs.h"
  17
  18/* runs_tree is a continues memory. Try to avoid big size. */
  19#define NTFS3_RUN_MAX_BYTES 0x10000
  20
  21struct ntfs_run {
  22	CLST vcn; /* Virtual cluster number. */
  23	CLST len; /* Length in clusters. */
  24	CLST lcn; /* Logical cluster number. */
  25};
  26
  27/*
  28 * run_lookup - Lookup the index of a MCB entry that is first <= vcn.
  29 *
  30 * Case of success it will return non-zero value and set
  31 * @index parameter to index of entry been found.
  32 * Case of entry missing from list 'index' will be set to
  33 * point to insertion position for the entry question.
  34 */
  35static bool run_lookup(const struct runs_tree *run, CLST vcn, size_t *index)
  36{
  37	size_t min_idx, max_idx, mid_idx;
  38	struct ntfs_run *r;
  39
  40	if (!run->count) {
  41		*index = 0;
  42		return false;
  43	}
  44
  45	min_idx = 0;
  46	max_idx = run->count - 1;
  47
  48	/* Check boundary cases specially, 'cause they cover the often requests. */
  49	r = run->runs;
  50	if (vcn < r->vcn) {
  51		*index = 0;
  52		return false;
  53	}
  54
  55	if (vcn < r->vcn + r->len) {
  56		*index = 0;
  57		return true;
  58	}
  59
  60	r += max_idx;
  61	if (vcn >= r->vcn + r->len) {
  62		*index = run->count;
  63		return false;
  64	}
  65
  66	if (vcn >= r->vcn) {
  67		*index = max_idx;
  68		return true;
  69	}
  70
  71	do {
  72		mid_idx = min_idx + ((max_idx - min_idx) >> 1);
  73		r = run->runs + mid_idx;
  74
  75		if (vcn < r->vcn) {
  76			max_idx = mid_idx - 1;
  77			if (!mid_idx)
  78				break;
  79		} else if (vcn >= r->vcn + r->len) {
  80			min_idx = mid_idx + 1;
  81		} else {
  82			*index = mid_idx;
  83			return true;
  84		}
  85	} while (min_idx <= max_idx);
  86
  87	*index = max_idx + 1;
  88	return false;
  89}
  90
  91/*
  92 * run_consolidate - Consolidate runs starting from a given one.
  93 */
  94static void run_consolidate(struct runs_tree *run, size_t index)
  95{
  96	size_t i;
  97	struct ntfs_run *r = run->runs + index;
  98
  99	while (index + 1 < run->count) {
 100		/*
 101		 * I should merge current run with next
 102		 * if start of the next run lies inside one being tested.
 103		 */
 104		struct ntfs_run *n = r + 1;
 105		CLST end = r->vcn + r->len;
 106		CLST dl;
 107
 108		/* Stop if runs are not aligned one to another. */
 109		if (n->vcn > end)
 110			break;
 111
 112		dl = end - n->vcn;
 113
 114		/*
 115		 * If range at index overlaps with next one
 116		 * then I will either adjust it's start position
 117		 * or (if completely matches) dust remove one from the list.
 118		 */
 119		if (dl > 0) {
 120			if (n->len <= dl)
 121				goto remove_next_range;
 122
 123			n->len -= dl;
 124			n->vcn += dl;
 125			if (n->lcn != SPARSE_LCN)
 126				n->lcn += dl;
 127			dl = 0;
 128		}
 129
 130		/*
 131		 * Stop if sparse mode does not match
 132		 * both current and next runs.
 133		 */
 134		if ((n->lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) {
 135			index += 1;
 136			r = n;
 137			continue;
 138		}
 139
 140		/*
 141		 * Check if volume block
 142		 * of a next run lcn does not match
 143		 * last volume block of the current run.
 144		 */
 145		if (n->lcn != SPARSE_LCN && n->lcn != r->lcn + r->len)
 146			break;
 147
 148		/*
 149		 * Next and current are siblings.
 150		 * Eat/join.
 151		 */
 152		r->len += n->len - dl;
 153
 154remove_next_range:
 155		i = run->count - (index + 1);
 156		if (i > 1)
 157			memmove(n, n + 1, sizeof(*n) * (i - 1));
 158
 159		run->count -= 1;
 160	}
 161}
 162
 163/*
 164 * run_is_mapped_full
 165 *
 166 * Return: True if range [svcn - evcn] is mapped.
 167 */
 168bool run_is_mapped_full(const struct runs_tree *run, CLST svcn, CLST evcn)
 169{
 170	size_t i;
 171	const struct ntfs_run *r, *end;
 172	CLST next_vcn;
 173
 174	if (!run_lookup(run, svcn, &i))
 175		return false;
 176
 177	end = run->runs + run->count;
 178	r = run->runs + i;
 179
 180	for (;;) {
 181		next_vcn = r->vcn + r->len;
 182		if (next_vcn > evcn)
 183			return true;
 184
 185		if (++r >= end)
 186			return false;
 187
 188		if (r->vcn != next_vcn)
 189			return false;
 190	}
 191}
 192
 193bool run_lookup_entry(const struct runs_tree *run, CLST vcn, CLST *lcn,
 194		      CLST *len, size_t *index)
 195{
 196	size_t idx;
 197	CLST gap;
 198	struct ntfs_run *r;
 199
 200	/* Fail immediately if nrun was not touched yet. */
 201	if (!run->runs)
 202		return false;
 203
 204	if (!run_lookup(run, vcn, &idx))
 205		return false;
 206
 207	r = run->runs + idx;
 208
 209	if (vcn >= r->vcn + r->len)
 210		return false;
 211
 212	gap = vcn - r->vcn;
 213	if (r->len <= gap)
 214		return false;
 215
 216	*lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + gap);
 217
 218	if (len)
 219		*len = r->len - gap;
 220	if (index)
 221		*index = idx;
 222
 223	return true;
 224}
 225
 226/*
 227 * run_truncate_head - Decommit the range before vcn.
 228 */
 229void run_truncate_head(struct runs_tree *run, CLST vcn)
 230{
 231	size_t index;
 232	struct ntfs_run *r;
 233
 234	if (run_lookup(run, vcn, &index)) {
 235		r = run->runs + index;
 236
 237		if (vcn > r->vcn) {
 238			CLST dlen = vcn - r->vcn;
 239
 240			r->vcn = vcn;
 241			r->len -= dlen;
 242			if (r->lcn != SPARSE_LCN)
 243				r->lcn += dlen;
 244		}
 245
 246		if (!index)
 247			return;
 248	}
 249	r = run->runs;
 250	memmove(r, r + index, sizeof(*r) * (run->count - index));
 251
 252	run->count -= index;
 253
 254	if (!run->count) {
 255		kvfree(run->runs);
 256		run->runs = NULL;
 257		run->allocated = 0;
 258	}
 259}
 260
 261/*
 262 * run_truncate - Decommit the range after vcn.
 263 */
 264void run_truncate(struct runs_tree *run, CLST vcn)
 265{
 266	size_t index;
 267
 268	/*
 269	 * If I hit the range then
 270	 * I have to truncate one.
 271	 * If range to be truncated is becoming empty
 272	 * then it will entirely be removed.
 273	 */
 274	if (run_lookup(run, vcn, &index)) {
 275		struct ntfs_run *r = run->runs + index;
 276
 277		r->len = vcn - r->vcn;
 278
 279		if (r->len > 0)
 280			index += 1;
 281	}
 282
 283	/*
 284	 * At this point 'index' is set to position that
 285	 * should be thrown away (including index itself)
 286	 * Simple one - just set the limit.
 287	 */
 288	run->count = index;
 289
 290	/* Do not reallocate array 'runs'. Only free if possible. */
 291	if (!index) {
 292		kvfree(run->runs);
 293		run->runs = NULL;
 294		run->allocated = 0;
 295	}
 296}
 297
 298/*
 299 * run_truncate_around - Trim head and tail if necessary.
 300 */
 301void run_truncate_around(struct runs_tree *run, CLST vcn)
 302{
 303	run_truncate_head(run, vcn);
 304
 305	if (run->count >= NTFS3_RUN_MAX_BYTES / sizeof(struct ntfs_run) / 2)
 306		run_truncate(run, (run->runs + (run->count >> 1))->vcn);
 307}
 308
 309/*
 310 * run_add_entry
 311 *
 312 * Sets location to known state.
 313 * Run to be added may overlap with existing location.
 314 *
 315 * Return: false if of memory.
 316 */
 317bool run_add_entry(struct runs_tree *run, CLST vcn, CLST lcn, CLST len,
 318		   bool is_mft)
 319{
 320	size_t used, index;
 321	struct ntfs_run *r;
 322	bool inrange;
 323	CLST tail_vcn = 0, tail_len = 0, tail_lcn = 0;
 324	bool should_add_tail = false;
 325
 326	/*
 327	 * Lookup the insertion point.
 328	 *
 329	 * Execute bsearch for the entry containing
 330	 * start position question.
 331	 */
 332	inrange = run_lookup(run, vcn, &index);
 333
 334	/*
 335	 * Shortcut here would be case of
 336	 * range not been found but one been added
 337	 * continues previous run.
 338	 * This case I can directly make use of
 339	 * existing range as my start point.
 340	 */
 341	if (!inrange && index > 0) {
 342		struct ntfs_run *t = run->runs + index - 1;
 343
 344		if (t->vcn + t->len == vcn &&
 345		    (t->lcn == SPARSE_LCN) == (lcn == SPARSE_LCN) &&
 346		    (lcn == SPARSE_LCN || lcn == t->lcn + t->len)) {
 347			inrange = true;
 348			index -= 1;
 349		}
 350	}
 351
 352	/*
 353	 * At this point 'index' either points to the range
 354	 * containing start position or to the insertion position
 355	 * for a new range.
 356	 * So first let's check if range I'm probing is here already.
 357	 */
 358	if (!inrange) {
 359requires_new_range:
 360		/*
 361		 * Range was not found.
 362		 * Insert at position 'index'
 363		 */
 364		used = run->count * sizeof(struct ntfs_run);
 365
 366		/*
 367		 * Check allocated space.
 368		 * If one is not enough to get one more entry
 369		 * then it will be reallocated.
 370		 */
 371		if (run->allocated < used + sizeof(struct ntfs_run)) {
 372			size_t bytes;
 373			struct ntfs_run *new_ptr;
 374
 375			/* Use power of 2 for 'bytes'. */
 376			if (!used) {
 377				bytes = 64;
 378			} else if (used <= 16 * PAGE_SIZE) {
 379				if (is_power_of_2(run->allocated))
 380					bytes = run->allocated << 1;
 381				else
 382					bytes = (size_t)1
 383						<< (2 + blksize_bits(used));
 384			} else {
 385				bytes = run->allocated + (16 * PAGE_SIZE);
 386			}
 387
 388			WARN_ON(!is_mft && bytes > NTFS3_RUN_MAX_BYTES);
 389
 390			new_ptr = kvmalloc(bytes, GFP_KERNEL);
 391
 392			if (!new_ptr)
 393				return false;
 394
 395			r = new_ptr + index;
 396			memcpy(new_ptr, run->runs,
 397			       index * sizeof(struct ntfs_run));
 398			memcpy(r + 1, run->runs + index,
 399			       sizeof(struct ntfs_run) * (run->count - index));
 400
 401			kvfree(run->runs);
 402			run->runs = new_ptr;
 403			run->allocated = bytes;
 404
 405		} else {
 406			size_t i = run->count - index;
 407
 408			r = run->runs + index;
 409
 410			/* memmove appears to be a bottle neck here... */
 411			if (i > 0)
 412				memmove(r + 1, r, sizeof(struct ntfs_run) * i);
 413		}
 414
 415		r->vcn = vcn;
 416		r->lcn = lcn;
 417		r->len = len;
 418		run->count += 1;
 419	} else {
 420		r = run->runs + index;
 421
 422		/*
 423		 * If one of ranges was not allocated then we
 424		 * have to split location we just matched and
 425		 * insert current one.
 426		 * A common case this requires tail to be reinserted
 427		 * a recursive call.
 428		 */
 429		if (((lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) ||
 430		    (lcn != SPARSE_LCN && lcn != r->lcn + (vcn - r->vcn))) {
 431			CLST to_eat = vcn - r->vcn;
 432			CLST Tovcn = to_eat + len;
 433
 434			should_add_tail = Tovcn < r->len;
 435
 436			if (should_add_tail) {
 437				tail_lcn = r->lcn == SPARSE_LCN ?
 438						   SPARSE_LCN :
 439						   (r->lcn + Tovcn);
 440				tail_vcn = r->vcn + Tovcn;
 441				tail_len = r->len - Tovcn;
 442			}
 443
 444			if (to_eat > 0) {
 445				r->len = to_eat;
 446				inrange = false;
 447				index += 1;
 448				goto requires_new_range;
 449			}
 450
 451			/* lcn should match one were going to add. */
 452			r->lcn = lcn;
 453		}
 454
 455		/*
 456		 * If existing range fits then were done.
 457		 * Otherwise extend found one and fall back to range jocode.
 458		 */
 459		if (r->vcn + r->len < vcn + len)
 460			r->len += len - ((r->vcn + r->len) - vcn);
 461	}
 462
 463	/*
 464	 * And normalize it starting from insertion point.
 465	 * It's possible that no insertion needed case if
 466	 * start point lies within the range of an entry
 467	 * that 'index' points to.
 468	 */
 469	if (inrange && index > 0)
 470		index -= 1;
 471	run_consolidate(run, index);
 472	run_consolidate(run, index + 1);
 473
 474	/*
 475	 * A special case.
 476	 * We have to add extra range a tail.
 477	 */
 478	if (should_add_tail &&
 479	    !run_add_entry(run, tail_vcn, tail_lcn, tail_len, is_mft))
 480		return false;
 481
 482	return true;
 483}
 484
 485/* run_collapse_range
 486 *
 487 * Helper for attr_collapse_range(),
 488 * which is helper for fallocate(collapse_range).
 489 */
 490bool run_collapse_range(struct runs_tree *run, CLST vcn, CLST len, CLST sub)
 491{
 492	size_t index, eat;
 493	struct ntfs_run *r, *e, *eat_start, *eat_end;
 494	CLST end;
 495
 496	if (WARN_ON(!run_lookup(run, vcn, &index)))
 497		return true; /* Should never be here. */
 498
 499	e = run->runs + run->count;
 500	r = run->runs + index;
 501	end = vcn + len;
 502
 503	if (vcn > r->vcn) {
 504		if (r->vcn + r->len <= end) {
 505			/* Collapse tail of run .*/
 506			r->len = vcn - r->vcn;
 507		} else if (r->lcn == SPARSE_LCN) {
 508			/* Collapse a middle part of sparsed run. */
 509			r->len -= len;
 510		} else {
 511			/* Collapse a middle part of normal run, split. */
 512			if (!run_add_entry(run, vcn, SPARSE_LCN, len, false))
 513				return false;
 514			return run_collapse_range(run, vcn, len, sub);
 515		}
 516
 517		r += 1;
 518	}
 519
 520	eat_start = r;
 521	eat_end = r;
 522
 523	for (; r < e; r++) {
 524		CLST d;
 525
 526		if (r->vcn >= end) {
 527			r->vcn -= len;
 528			continue;
 529		}
 530
 531		if (r->vcn + r->len <= end) {
 532			/* Eat this run. */
 533			eat_end = r + 1;
 534			continue;
 535		}
 536
 537		d = end - r->vcn;
 538		if (r->lcn != SPARSE_LCN)
 539			r->lcn += d;
 540		r->len -= d;
 541		r->vcn -= len - d;
 542	}
 543
 544	eat = eat_end - eat_start;
 545	memmove(eat_start, eat_end, (e - eat_end) * sizeof(*r));
 546	run->count -= eat;
 547
 548	if (sub) {
 549		e -= eat;
 550		for (r = run->runs; r < e; r++) {
 551			r->vcn -= sub;
 552		}
 553	}
 554
 555	return true;
 556}
 557
 558/* run_insert_range
 559 *
 560 * Helper for attr_insert_range(),
 561 * which is helper for fallocate(insert_range).
 562 */
 563bool run_insert_range(struct runs_tree *run, CLST vcn, CLST len)
 564{
 565	size_t index;
 566	struct ntfs_run *r, *e;
 567
 568	if (WARN_ON(!run_lookup(run, vcn, &index)))
 569		return false; /* Should never be here. */
 570
 571	e = run->runs + run->count;
 572	r = run->runs + index;
 573
 574	if (vcn > r->vcn)
 575		r += 1;
 576
 577	for (; r < e; r++)
 578		r->vcn += len;
 579
 580	r = run->runs + index;
 581
 582	if (vcn > r->vcn) {
 583		/* split fragment. */
 584		CLST len1 = vcn - r->vcn;
 585		CLST len2 = r->len - len1;
 586		CLST lcn2 = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len1);
 587
 588		r->len = len1;
 589
 590		if (!run_add_entry(run, vcn + len, lcn2, len2, false))
 591			return false;
 592	}
 593
 594	if (!run_add_entry(run, vcn, SPARSE_LCN, len, false))
 595		return false;
 596
 597	return true;
 598}
 599
 600/*
 601 * run_get_entry - Return index-th mapped region.
 602 */
 603bool run_get_entry(const struct runs_tree *run, size_t index, CLST *vcn,
 604		   CLST *lcn, CLST *len)
 605{
 606	const struct ntfs_run *r;
 607
 608	if (index >= run->count)
 609		return false;
 610
 611	r = run->runs + index;
 612
 613	if (!r->len)
 614		return false;
 615
 616	if (vcn)
 617		*vcn = r->vcn;
 618	if (lcn)
 619		*lcn = r->lcn;
 620	if (len)
 621		*len = r->len;
 622	return true;
 623}
 624
 625/*
 626 * run_packed_size - Calculate the size of packed int64.
 627 */
 628#ifdef __BIG_ENDIAN
 629static inline int run_packed_size(const s64 n)
 630{
 631	const u8 *p = (const u8 *)&n + sizeof(n) - 1;
 632
 633	if (n >= 0) {
 634		if (p[-7] || p[-6] || p[-5] || p[-4])
 635			p -= 4;
 636		if (p[-3] || p[-2])
 637			p -= 2;
 638		if (p[-1])
 639			p -= 1;
 640		if (p[0] & 0x80)
 641			p -= 1;
 642	} else {
 643		if (p[-7] != 0xff || p[-6] != 0xff || p[-5] != 0xff ||
 644		    p[-4] != 0xff)
 645			p -= 4;
 646		if (p[-3] != 0xff || p[-2] != 0xff)
 647			p -= 2;
 648		if (p[-1] != 0xff)
 649			p -= 1;
 650		if (!(p[0] & 0x80))
 651			p -= 1;
 652	}
 653	return (const u8 *)&n + sizeof(n) - p;
 654}
 655
 656/* Full trusted function. It does not check 'size' for errors. */
 657static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v)
 658{
 659	const u8 *p = (u8 *)&v;
 660
 661	switch (size) {
 662	case 8:
 663		run_buf[7] = p[0];
 664		fallthrough;
 665	case 7:
 666		run_buf[6] = p[1];
 667		fallthrough;
 668	case 6:
 669		run_buf[5] = p[2];
 670		fallthrough;
 671	case 5:
 672		run_buf[4] = p[3];
 673		fallthrough;
 674	case 4:
 675		run_buf[3] = p[4];
 676		fallthrough;
 677	case 3:
 678		run_buf[2] = p[5];
 679		fallthrough;
 680	case 2:
 681		run_buf[1] = p[6];
 682		fallthrough;
 683	case 1:
 684		run_buf[0] = p[7];
 685	}
 686}
 687
 688/* Full trusted function. It does not check 'size' for errors. */
 689static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v)
 690{
 691	u8 *p = (u8 *)&v;
 692
 693	switch (size) {
 694	case 8:
 695		p[0] = run_buf[7];
 696		fallthrough;
 697	case 7:
 698		p[1] = run_buf[6];
 699		fallthrough;
 700	case 6:
 701		p[2] = run_buf[5];
 702		fallthrough;
 703	case 5:
 704		p[3] = run_buf[4];
 705		fallthrough;
 706	case 4:
 707		p[4] = run_buf[3];
 708		fallthrough;
 709	case 3:
 710		p[5] = run_buf[2];
 711		fallthrough;
 712	case 2:
 713		p[6] = run_buf[1];
 714		fallthrough;
 715	case 1:
 716		p[7] = run_buf[0];
 717	}
 718	return v;
 719}
 720
 721#else
 722
 723static inline int run_packed_size(const s64 n)
 724{
 725	const u8 *p = (const u8 *)&n;
 726
 727	if (n >= 0) {
 728		if (p[7] || p[6] || p[5] || p[4])
 729			p += 4;
 730		if (p[3] || p[2])
 731			p += 2;
 732		if (p[1])
 733			p += 1;
 734		if (p[0] & 0x80)
 735			p += 1;
 736	} else {
 737		if (p[7] != 0xff || p[6] != 0xff || p[5] != 0xff ||
 738		    p[4] != 0xff)
 739			p += 4;
 740		if (p[3] != 0xff || p[2] != 0xff)
 741			p += 2;
 742		if (p[1] != 0xff)
 743			p += 1;
 744		if (!(p[0] & 0x80))
 745			p += 1;
 746	}
 747
 748	return 1 + p - (const u8 *)&n;
 749}
 750
 751/* Full trusted function. It does not check 'size' for errors. */
 752static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v)
 753{
 754	const u8 *p = (u8 *)&v;
 755
 756	/* memcpy( run_buf, &v, size); Is it faster? */
 757	switch (size) {
 758	case 8:
 759		run_buf[7] = p[7];
 760		fallthrough;
 761	case 7:
 762		run_buf[6] = p[6];
 763		fallthrough;
 764	case 6:
 765		run_buf[5] = p[5];
 766		fallthrough;
 767	case 5:
 768		run_buf[4] = p[4];
 769		fallthrough;
 770	case 4:
 771		run_buf[3] = p[3];
 772		fallthrough;
 773	case 3:
 774		run_buf[2] = p[2];
 775		fallthrough;
 776	case 2:
 777		run_buf[1] = p[1];
 778		fallthrough;
 779	case 1:
 780		run_buf[0] = p[0];
 781	}
 782}
 783
 784/* full trusted function. It does not check 'size' for errors */
 785static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v)
 786{
 787	u8 *p = (u8 *)&v;
 788
 789	/* memcpy( &v, run_buf, size); Is it faster? */
 790	switch (size) {
 791	case 8:
 792		p[7] = run_buf[7];
 793		fallthrough;
 794	case 7:
 795		p[6] = run_buf[6];
 796		fallthrough;
 797	case 6:
 798		p[5] = run_buf[5];
 799		fallthrough;
 800	case 5:
 801		p[4] = run_buf[4];
 802		fallthrough;
 803	case 4:
 804		p[3] = run_buf[3];
 805		fallthrough;
 806	case 3:
 807		p[2] = run_buf[2];
 808		fallthrough;
 809	case 2:
 810		p[1] = run_buf[1];
 811		fallthrough;
 812	case 1:
 813		p[0] = run_buf[0];
 814	}
 815	return v;
 816}
 817#endif
 818
 819/*
 820 * run_pack - Pack runs into buffer.
 821 *
 822 * packed_vcns - How much runs we have packed.
 823 * packed_size - How much bytes we have used run_buf.
 824 */
 825int run_pack(const struct runs_tree *run, CLST svcn, CLST len, u8 *run_buf,
 826	     u32 run_buf_size, CLST *packed_vcns)
 827{
 828	CLST next_vcn, vcn, lcn;
 829	CLST prev_lcn = 0;
 830	CLST evcn1 = svcn + len;
 831	const struct ntfs_run *r, *r_end;
 832	int packed_size = 0;
 833	size_t i;
 834	s64 dlcn;
 835	int offset_size, size_size, tmp;
 836
 837	*packed_vcns = 0;
 838
 839	if (!len)
 840		goto out;
 841
 842	/* Check all required entries [svcn, encv1) available. */
 843	if (!run_lookup(run, svcn, &i))
 844		return -ENOENT;
 845
 846	r_end = run->runs + run->count;
 847	r = run->runs + i;
 848
 849	for (next_vcn = r->vcn + r->len; next_vcn < evcn1;
 850	     next_vcn = r->vcn + r->len) {
 851		if (++r >= r_end || r->vcn != next_vcn)
 852			return -ENOENT;
 853	}
 854
 855	/* Repeat cycle above and pack runs. Assume no errors. */
 856	r = run->runs + i;
 857	len = svcn - r->vcn;
 858	vcn = svcn;
 859	lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len);
 860	len = r->len - len;
 861
 862	for (;;) {
 863		next_vcn = vcn + len;
 864		if (next_vcn > evcn1)
 865			len = evcn1 - vcn;
 866
 867		/* How much bytes required to pack len. */
 868		size_size = run_packed_size(len);
 869
 870		/* offset_size - How much bytes is packed dlcn. */
 871		if (lcn == SPARSE_LCN) {
 872			offset_size = 0;
 873			dlcn = 0;
 874		} else {
 875			/* NOTE: lcn can be less than prev_lcn! */
 876			dlcn = (s64)lcn - prev_lcn;
 877			offset_size = run_packed_size(dlcn);
 878			prev_lcn = lcn;
 879		}
 880
 881		tmp = run_buf_size - packed_size - 2 - offset_size;
 882		if (tmp <= 0)
 883			goto out;
 884
 885		/* Can we store this entire run. */
 886		if (tmp < size_size)
 887			goto out;
 888
 889		if (run_buf) {
 890			/* Pack run header. */
 891			run_buf[0] = ((u8)(size_size | (offset_size << 4)));
 892			run_buf += 1;
 893
 894			/* Pack the length of run. */
 895			run_pack_s64(run_buf, size_size, len);
 896
 897			run_buf += size_size;
 898			/* Pack the offset from previous LCN. */
 899			run_pack_s64(run_buf, offset_size, dlcn);
 900			run_buf += offset_size;
 901		}
 902
 903		packed_size += 1 + offset_size + size_size;
 904		*packed_vcns += len;
 905
 906		if (packed_size + 1 >= run_buf_size || next_vcn >= evcn1)
 907			goto out;
 908
 909		r += 1;
 910		vcn = r->vcn;
 911		lcn = r->lcn;
 912		len = r->len;
 913	}
 914
 915out:
 916	/* Store last zero. */
 917	if (run_buf)
 918		run_buf[0] = 0;
 919
 920	return packed_size + 1;
 921}
 922
 923/*
 924 * run_unpack - Unpack packed runs from @run_buf.
 925 *
 926 * Return: Error if negative, or real used bytes.
 927 */
 928int run_unpack(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino,
 929	       CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf,
 930	       int run_buf_size)
 931{
 932	u64 prev_lcn, vcn64, lcn, next_vcn;
 933	const u8 *run_last, *run_0;
 934	bool is_mft = ino == MFT_REC_MFT;
 935
 936	if (run_buf_size < 0)
 937		return -EINVAL;
 938
 939	/* Check for empty. */
 940	if (evcn + 1 == svcn)
 941		return 0;
 942
 943	if (evcn < svcn)
 944		return -EINVAL;
 945
 946	run_0 = run_buf;
 947	run_last = run_buf + run_buf_size;
 948	prev_lcn = 0;
 949	vcn64 = svcn;
 950
 951	/* Read all runs the chain. */
 952	/* size_size - How much bytes is packed len. */
 953	while (run_buf < run_last) {
 954		/* size_size - How much bytes is packed len. */
 955		u8 size_size = *run_buf & 0xF;
 956		/* offset_size - How much bytes is packed dlcn. */
 957		u8 offset_size = *run_buf++ >> 4;
 958		u64 len;
 959
 960		if (!size_size)
 961			break;
 962
 963		/*
 964		 * Unpack runs.
 965		 * NOTE: Runs are stored little endian order
 966		 * "len" is unsigned value, "dlcn" is signed.
 967		 * Large positive number requires to store 5 bytes
 968		 * e.g.: 05 FF 7E FF FF 00 00 00
 969		 */
 970		if (size_size > sizeof(len))
 971			return -EINVAL;
 972
 973		len = run_unpack_s64(run_buf, size_size, 0);
 974		/* Skip size_size. */
 975		run_buf += size_size;
 976
 977		if (!len)
 978			return -EINVAL;
 979
 980		if (!offset_size)
 981			lcn = SPARSE_LCN64;
 982		else if (offset_size <= sizeof(s64)) {
 983			s64 dlcn;
 984
 985			/* Initial value of dlcn is -1 or 0. */
 986			dlcn = (run_buf[offset_size - 1] & 0x80) ? (s64)-1 : 0;
 987			dlcn = run_unpack_s64(run_buf, offset_size, dlcn);
 988			/* Skip offset_size. */
 989			run_buf += offset_size;
 990
 991			if (!dlcn)
 992				return -EINVAL;
 993
 994			/* Check special combination: 0 + SPARSE_LCN64. */
 995			if (!prev_lcn && dlcn == SPARSE_LCN64) {
 996				lcn = SPARSE_LCN64;
 997			} else if (check_add_overflow(prev_lcn, dlcn, &lcn)) {
 998				return -EINVAL;
 999			}
1000			prev_lcn = lcn;
1001		} else {
1002			/* The size of 'dlcn' can't be > 8. */
1003			return -EINVAL;
1004		}
1005
1006		if (check_add_overflow(vcn64, len, &next_vcn))
1007			return -EINVAL;
1008
1009		/* Check boundary. */
1010		if (next_vcn > evcn + 1)
1011			return -EINVAL;
1012
1013#ifndef CONFIG_NTFS3_64BIT_CLUSTER
1014		if (next_vcn > 0x100000000ull || (lcn + len) > 0x100000000ull) {
1015			ntfs_err(
1016				sbi->sb,
1017				"This driver is compiled without CONFIG_NTFS3_64BIT_CLUSTER (like windows driver).\n"
1018				"Volume contains 64 bits run: vcn %llx, lcn %llx, len %llx.\n"
1019				"Activate CONFIG_NTFS3_64BIT_CLUSTER to process this case",
1020				vcn64, lcn, len);
1021			return -EOPNOTSUPP;
1022		}
1023#endif
1024		if (lcn != SPARSE_LCN64 && lcn + len > sbi->used.bitmap.nbits) {
1025			/* LCN range is out of volume. */
1026			return -EINVAL;
1027		}
1028
1029		if (!run)
1030			; /* Called from check_attr(fslog.c) to check run. */
1031		else if (run == RUN_DEALLOCATE) {
1032			/*
1033			 * Called from ni_delete_all to free clusters
1034			 * without storing in run.
1035			 */
1036			if (lcn != SPARSE_LCN64)
1037				mark_as_free_ex(sbi, lcn, len, true);
1038		} else if (vcn64 >= vcn) {
1039			if (!run_add_entry(run, vcn64, lcn, len, is_mft))
1040				return -ENOMEM;
1041		} else if (next_vcn > vcn) {
1042			u64 dlen = vcn - vcn64;
1043
1044			if (!run_add_entry(run, vcn, lcn + dlen, len - dlen,
1045					   is_mft))
1046				return -ENOMEM;
1047		}
1048
1049		vcn64 = next_vcn;
1050	}
1051
1052	if (vcn64 != evcn + 1) {
1053		/* Not expected length of unpacked runs. */
1054		return -EINVAL;
1055	}
1056
1057	return run_buf - run_0;
1058}
1059
1060#ifdef NTFS3_CHECK_FREE_CLST
1061/*
1062 * run_unpack_ex - Unpack packed runs from "run_buf".
1063 *
1064 * Checks unpacked runs to be used in bitmap.
1065 *
1066 * Return: Error if negative, or real used bytes.
1067 */
1068int run_unpack_ex(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino,
1069		  CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf,
1070		  int run_buf_size)
1071{
1072	int ret, err;
1073	CLST next_vcn, lcn, len;
1074	size_t index, done;
1075	bool ok, zone;
1076	struct wnd_bitmap *wnd;
1077
1078	ret = run_unpack(run, sbi, ino, svcn, evcn, vcn, run_buf, run_buf_size);
1079	if (ret <= 0)
1080		return ret;
1081
1082	if (!sbi->used.bitmap.sb || !run || run == RUN_DEALLOCATE)
1083		return ret;
1084
1085	if (ino == MFT_REC_BADCLUST)
1086		return ret;
1087
1088	next_vcn = vcn = svcn;
1089	wnd = &sbi->used.bitmap;
1090
1091	for (ok = run_lookup_entry(run, vcn, &lcn, &len, &index);
1092	     next_vcn <= evcn;
1093	     ok = run_get_entry(run, ++index, &vcn, &lcn, &len)) {
1094		if (!ok || next_vcn != vcn)
1095			return -EINVAL;
1096
1097		next_vcn = vcn + len;
1098
1099		if (lcn == SPARSE_LCN)
1100			continue;
1101
1102		if (sbi->flags & NTFS_FLAGS_NEED_REPLAY)
1103			continue;
1104
1105		down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS);
1106		zone = max(wnd->zone_bit, lcn) < min(wnd->zone_end, lcn + len);
1107		/* Check for free blocks. */
1108		ok = !zone && wnd_is_used(wnd, lcn, len);
1109		up_read(&wnd->rw_lock);
1110		if (ok)
1111			continue;
1112
1113		/* Looks like volume is corrupted. */
1114		ntfs_set_state(sbi, NTFS_DIRTY_ERROR);
1115
1116		if (!down_write_trylock(&wnd->rw_lock))
1117			continue;
1118
1119		if (zone) {
1120			/*
1121			 * Range [lcn, lcn + len) intersects with zone.
1122			 * To avoid complex with zone just turn it off.
1123			 */
1124			wnd_zone_set(wnd, 0, 0);
1125		}
1126
1127		/* Mark all zero bits as used in range [lcn, lcn+len). */
1128		err = wnd_set_used_safe(wnd, lcn, len, &done);
1129		if (zone) {
1130			/* Restore zone. Lock mft run. */
1131			struct rw_semaphore *lock =
1132				is_mounted(sbi) ? &sbi->mft.ni->file.run_lock :
1133						  NULL;
1134			if (lock) {
1135				if (down_read_trylock(lock)) {
1136					ntfs_refresh_zone(sbi);
1137					up_read(lock);
1138				}
1139			} else {
1140				ntfs_refresh_zone(sbi);
1141			}
1142		}
1143		up_write(&wnd->rw_lock);
1144		if (err)
1145			return err;
1146	}
1147
1148	return ret;
1149}
1150#endif
1151
1152/*
1153 * run_get_highest_vcn
1154 *
1155 * Return the highest vcn from a mapping pairs array
1156 * it used while replaying log file.
1157 */
1158int run_get_highest_vcn(CLST vcn, const u8 *run_buf, u64 *highest_vcn)
1159{
1160	u64 vcn64 = vcn;
1161	u8 size_size;
1162
1163	while ((size_size = *run_buf & 0xF)) {
1164		u8 offset_size = *run_buf++ >> 4;
1165		u64 len;
1166
1167		if (size_size > 8 || offset_size > 8)
1168			return -EINVAL;
1169
1170		len = run_unpack_s64(run_buf, size_size, 0);
1171		if (!len)
1172			return -EINVAL;
1173
1174		run_buf += size_size + offset_size;
1175		if (check_add_overflow(vcn64, len, &vcn64))
1176			return -EINVAL;
1177
1178#ifndef CONFIG_NTFS3_64BIT_CLUSTER
1179		if (vcn64 > 0x100000000ull)
1180			return -EINVAL;
1181#endif
1182	}
1183
1184	*highest_vcn = vcn64 - 1;
1185	return 0;
1186}
1187
1188/*
1189 * run_clone
1190 *
1191 * Make a copy of run
1192 */
1193int run_clone(const struct runs_tree *run, struct runs_tree *new_run)
1194{
1195	size_t bytes = run->count * sizeof(struct ntfs_run);
1196
1197	if (bytes > new_run->allocated) {
1198		struct ntfs_run *new_ptr = kvmalloc(bytes, GFP_KERNEL);
1199
1200		if (!new_ptr)
1201			return -ENOMEM;
1202
1203		kvfree(new_run->runs);
1204		new_run->runs = new_ptr;
1205		new_run->allocated = bytes;
1206	}
1207
1208	memcpy(new_run->runs, run->runs, bytes);
1209	new_run->count = run->count;
1210	return 0;
1211}