index.c

   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 *
   4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
   5 *
   6 */
   7
   8#include <linux/blkdev.h>
   9#include <linux/buffer_head.h>
  10#include <linux/fs.h>
  11#include <linux/kernel.h>
  12
  13#include "debug.h"
  14#include "ntfs.h"
  15#include "ntfs_fs.h"
  16
  17static const struct INDEX_NAMES {
  18	const __le16 *name;
  19	u8 name_len;
  20} s_index_names[INDEX_MUTEX_TOTAL] = {
  21	{ I30_NAME, ARRAY_SIZE(I30_NAME) }, { SII_NAME, ARRAY_SIZE(SII_NAME) },
  22	{ SDH_NAME, ARRAY_SIZE(SDH_NAME) }, { SO_NAME, ARRAY_SIZE(SO_NAME) },
  23	{ SQ_NAME, ARRAY_SIZE(SQ_NAME) },   { SR_NAME, ARRAY_SIZE(SR_NAME) },
  24};
  25
  26/*
  27 * cmp_fnames - Compare two names in index.
  28 *
  29 * if l1 != 0
  30 *   Both names are little endian on-disk ATTR_FILE_NAME structs.
  31 * else
  32 *   key1 - cpu_str, key2 - ATTR_FILE_NAME
  33 */
  34static int cmp_fnames(const void *key1, size_t l1, const void *key2, size_t l2,
  35		      const void *data)
  36{
  37	const struct ATTR_FILE_NAME *f2 = key2;
  38	const struct ntfs_sb_info *sbi = data;
  39	const struct ATTR_FILE_NAME *f1;
  40	u16 fsize2;
  41	bool both_case;
  42
  43	if (l2 <= offsetof(struct ATTR_FILE_NAME, name))
  44		return -1;
  45
  46	fsize2 = fname_full_size(f2);
  47	if (l2 < fsize2)
  48		return -1;
  49
  50	both_case = f2->type != FILE_NAME_DOS && !sbi->options->nocase;
  51	if (!l1) {
  52		const struct le_str *s2 = (struct le_str *)&f2->name_len;
  53
  54		/*
  55		 * If names are equal (case insensitive)
  56		 * try to compare it case sensitive.
  57		 */
  58		return ntfs_cmp_names_cpu(key1, s2, sbi->upcase, both_case);
  59	}
  60
  61	f1 = key1;
  62	return ntfs_cmp_names(f1->name, f1->name_len, f2->name, f2->name_len,
  63			      sbi->upcase, both_case);
  64}
  65
  66/*
  67 * cmp_uint - $SII of $Secure and $Q of Quota
  68 */
  69static int cmp_uint(const void *key1, size_t l1, const void *key2, size_t l2,
  70		    const void *data)
  71{
  72	const u32 *k1 = key1;
  73	const u32 *k2 = key2;
  74
  75	if (l2 < sizeof(u32))
  76		return -1;
  77
  78	if (*k1 < *k2)
  79		return -1;
  80	if (*k1 > *k2)
  81		return 1;
  82	return 0;
  83}
  84
  85/*
  86 * cmp_sdh - $SDH of $Secure
  87 */
  88static int cmp_sdh(const void *key1, size_t l1, const void *key2, size_t l2,
  89		   const void *data)
  90{
  91	const struct SECURITY_KEY *k1 = key1;
  92	const struct SECURITY_KEY *k2 = key2;
  93	u32 t1, t2;
  94
  95	if (l2 < sizeof(struct SECURITY_KEY))
  96		return -1;
  97
  98	t1 = le32_to_cpu(k1->hash);
  99	t2 = le32_to_cpu(k2->hash);
 100
 101	/* First value is a hash value itself. */
 102	if (t1 < t2)
 103		return -1;
 104	if (t1 > t2)
 105		return 1;
 106
 107	/* Second value is security Id. */
 108	if (data) {
 109		t1 = le32_to_cpu(k1->sec_id);
 110		t2 = le32_to_cpu(k2->sec_id);
 111		if (t1 < t2)
 112			return -1;
 113		if (t1 > t2)
 114			return 1;
 115	}
 116
 117	return 0;
 118}
 119
 120/*
 121 * cmp_uints - $O of ObjId and "$R" for Reparse.
 122 */
 123static int cmp_uints(const void *key1, size_t l1, const void *key2, size_t l2,
 124		     const void *data)
 125{
 126	const __le32 *k1 = key1;
 127	const __le32 *k2 = key2;
 128	size_t count;
 129
 130	if ((size_t)data == 1) {
 131		/*
 132		 * ni_delete_all -> ntfs_remove_reparse ->
 133		 * delete all with this reference.
 134		 * k1, k2 - pointers to REPARSE_KEY
 135		 */
 136
 137		k1 += 1; // Skip REPARSE_KEY.ReparseTag
 138		k2 += 1; // Skip REPARSE_KEY.ReparseTag
 139		if (l2 <= sizeof(int))
 140			return -1;
 141		l2 -= sizeof(int);
 142		if (l1 <= sizeof(int))
 143			return 1;
 144		l1 -= sizeof(int);
 145	}
 146
 147	if (l2 < sizeof(int))
 148		return -1;
 149
 150	for (count = min(l1, l2) >> 2; count > 0; --count, ++k1, ++k2) {
 151		u32 t1 = le32_to_cpu(*k1);
 152		u32 t2 = le32_to_cpu(*k2);
 153
 154		if (t1 > t2)
 155			return 1;
 156		if (t1 < t2)
 157			return -1;
 158	}
 159
 160	if (l1 > l2)
 161		return 1;
 162	if (l1 < l2)
 163		return -1;
 164
 165	return 0;
 166}
 167
 168static inline NTFS_CMP_FUNC get_cmp_func(const struct INDEX_ROOT *root)
 169{
 170	switch (root->type) {
 171	case ATTR_NAME:
 172		if (root->rule == NTFS_COLLATION_TYPE_FILENAME)
 173			return &cmp_fnames;
 174		break;
 175	case ATTR_ZERO:
 176		switch (root->rule) {
 177		case NTFS_COLLATION_TYPE_UINT:
 178			return &cmp_uint;
 179		case NTFS_COLLATION_TYPE_SECURITY_HASH:
 180			return &cmp_sdh;
 181		case NTFS_COLLATION_TYPE_UINTS:
 182			return &cmp_uints;
 183		default:
 184			break;
 185		}
 186		break;
 187	default:
 188		break;
 189	}
 190
 191	return NULL;
 192}
 193
 194struct bmp_buf {
 195	struct ATTRIB *b;
 196	struct mft_inode *mi;
 197	struct buffer_head *bh;
 198	ulong *buf;
 199	size_t bit;
 200	u32 nbits;
 201	u64 new_valid;
 202};
 203
 204static int bmp_buf_get(struct ntfs_index *indx, struct ntfs_inode *ni,
 205		       size_t bit, struct bmp_buf *bbuf)
 206{
 207	struct ATTRIB *b;
 208	size_t data_size, valid_size, vbo, off = bit >> 3;
 209	struct ntfs_sb_info *sbi = ni->mi.sbi;
 210	CLST vcn = off >> sbi->cluster_bits;
 211	struct ATTR_LIST_ENTRY *le = NULL;
 212	struct buffer_head *bh;
 213	struct super_block *sb;
 214	u32 blocksize;
 215	const struct INDEX_NAMES *in = &s_index_names[indx->type];
 216
 217	bbuf->bh = NULL;
 218
 219	b = ni_find_attr(ni, NULL, &le, ATTR_BITMAP, in->name, in->name_len,
 220			 &vcn, &bbuf->mi);
 221	bbuf->b = b;
 222	if (!b)
 223		return -EINVAL;
 224
 225	if (!b->non_res) {
 226		data_size = le32_to_cpu(b->res.data_size);
 227
 228		if (off >= data_size)
 229			return -EINVAL;
 230
 231		bbuf->buf = (ulong *)resident_data(b);
 232		bbuf->bit = 0;
 233		bbuf->nbits = data_size * 8;
 234
 235		return 0;
 236	}
 237
 238	data_size = le64_to_cpu(b->nres.data_size);
 239	if (WARN_ON(off >= data_size)) {
 240		/* Looks like filesystem error. */
 241		return -EINVAL;
 242	}
 243
 244	valid_size = le64_to_cpu(b->nres.valid_size);
 245
 246	bh = ntfs_bread_run(sbi, &indx->bitmap_run, off);
 247	if (!bh)
 248		return -EIO;
 249
 250	if (IS_ERR(bh))
 251		return PTR_ERR(bh);
 252
 253	bbuf->bh = bh;
 254
 255	if (buffer_locked(bh))
 256		__wait_on_buffer(bh);
 257
 258	lock_buffer(bh);
 259
 260	sb = sbi->sb;
 261	blocksize = sb->s_blocksize;
 262
 263	vbo = off & ~(size_t)sbi->block_mask;
 264
 265	bbuf->new_valid = vbo + blocksize;
 266	if (bbuf->new_valid <= valid_size)
 267		bbuf->new_valid = 0;
 268	else if (bbuf->new_valid > data_size)
 269		bbuf->new_valid = data_size;
 270
 271	if (vbo >= valid_size) {
 272		memset(bh->b_data, 0, blocksize);
 273	} else if (vbo + blocksize > valid_size) {
 274		u32 voff = valid_size & sbi->block_mask;
 275
 276		memset(bh->b_data + voff, 0, blocksize - voff);
 277	}
 278
 279	bbuf->buf = (ulong *)bh->b_data;
 280	bbuf->bit = 8 * (off & ~(size_t)sbi->block_mask);
 281	bbuf->nbits = 8 * blocksize;
 282
 283	return 0;
 284}
 285
 286static void bmp_buf_put(struct bmp_buf *bbuf, bool dirty)
 287{
 288	struct buffer_head *bh = bbuf->bh;
 289	struct ATTRIB *b = bbuf->b;
 290
 291	if (!bh) {
 292		if (b && !b->non_res && dirty)
 293			bbuf->mi->dirty = true;
 294		return;
 295	}
 296
 297	if (!dirty)
 298		goto out;
 299
 300	if (bbuf->new_valid) {
 301		b->nres.valid_size = cpu_to_le64(bbuf->new_valid);
 302		bbuf->mi->dirty = true;
 303	}
 304
 305	set_buffer_uptodate(bh);
 306	mark_buffer_dirty(bh);
 307
 308out:
 309	unlock_buffer(bh);
 310	put_bh(bh);
 311}
 312
 313/*
 314 * indx_mark_used - Mark the bit @bit as used.
 315 */
 316static int indx_mark_used(struct ntfs_index *indx, struct ntfs_inode *ni,
 317			  size_t bit)
 318{
 319	int err;
 320	struct bmp_buf bbuf;
 321
 322	err = bmp_buf_get(indx, ni, bit, &bbuf);
 323	if (err)
 324		return err;
 325
 326	__set_bit_le(bit - bbuf.bit, bbuf.buf);
 327
 328	bmp_buf_put(&bbuf, true);
 329
 330	return 0;
 331}
 332
 333/*
 334 * indx_mark_free - Mark the bit @bit as free.
 335 */
 336static int indx_mark_free(struct ntfs_index *indx, struct ntfs_inode *ni,
 337			  size_t bit)
 338{
 339	int err;
 340	struct bmp_buf bbuf;
 341
 342	err = bmp_buf_get(indx, ni, bit, &bbuf);
 343	if (err)
 344		return err;
 345
 346	__clear_bit_le(bit - bbuf.bit, bbuf.buf);
 347
 348	bmp_buf_put(&bbuf, true);
 349
 350	return 0;
 351}
 352
 353/*
 354 * scan_nres_bitmap
 355 *
 356 * If ntfs_readdir calls this function (indx_used_bit -> scan_nres_bitmap),
 357 * inode is shared locked and no ni_lock.
 358 * Use rw_semaphore for read/write access to bitmap_run.
 359 */
 360static int scan_nres_bitmap(struct ntfs_inode *ni, struct ATTRIB *bitmap,
 361			    struct ntfs_index *indx, size_t from,
 362			    bool (*fn)(const ulong *buf, u32 bit, u32 bits,
 363				       size_t *ret),
 364			    size_t *ret)
 365{
 366	struct ntfs_sb_info *sbi = ni->mi.sbi;
 367	struct super_block *sb = sbi->sb;
 368	struct runs_tree *run = &indx->bitmap_run;
 369	struct rw_semaphore *lock = &indx->run_lock;
 370	u32 nbits = sb->s_blocksize * 8;
 371	u32 blocksize = sb->s_blocksize;
 372	u64 valid_size = le64_to_cpu(bitmap->nres.valid_size);
 373	u64 data_size = le64_to_cpu(bitmap->nres.data_size);
 374	sector_t eblock = bytes_to_block(sb, data_size);
 375	size_t vbo = from >> 3;
 376	sector_t blk = (vbo & sbi->cluster_mask) >> sb->s_blocksize_bits;
 377	sector_t vblock = vbo >> sb->s_blocksize_bits;
 378	sector_t blen, block;
 379	CLST lcn, clen, vcn, vcn_next;
 380	size_t idx;
 381	struct buffer_head *bh;
 382	bool ok;
 383
 384	*ret = MINUS_ONE_T;
 385
 386	if (vblock >= eblock)
 387		return 0;
 388
 389	from &= nbits - 1;
 390	vcn = vbo >> sbi->cluster_bits;
 391
 392	down_read(lock);
 393	ok = run_lookup_entry(run, vcn, &lcn, &clen, &idx);
 394	up_read(lock);
 395
 396next_run:
 397	if (!ok) {
 398		int err;
 399		const struct INDEX_NAMES *name = &s_index_names[indx->type];
 400
 401		down_write(lock);
 402		err = attr_load_runs_vcn(ni, ATTR_BITMAP, name->name,
 403					 name->name_len, run, vcn);
 404		up_write(lock);
 405		if (err)
 406			return err;
 407		down_read(lock);
 408		ok = run_lookup_entry(run, vcn, &lcn, &clen, &idx);
 409		up_read(lock);
 410		if (!ok)
 411			return -EINVAL;
 412	}
 413
 414	blen = (sector_t)clen * sbi->blocks_per_cluster;
 415	block = (sector_t)lcn * sbi->blocks_per_cluster;
 416
 417	for (; blk < blen; blk++, from = 0) {
 418		bh = ntfs_bread(sb, block + blk);
 419		if (!bh)
 420			return -EIO;
 421
 422		vbo = (u64)vblock << sb->s_blocksize_bits;
 423		if (vbo >= valid_size) {
 424			memset(bh->b_data, 0, blocksize);
 425		} else if (vbo + blocksize > valid_size) {
 426			u32 voff = valid_size & sbi->block_mask;
 427
 428			memset(bh->b_data + voff, 0, blocksize - voff);
 429		}
 430
 431		if (vbo + blocksize > data_size)
 432			nbits = 8 * (data_size - vbo);
 433
 434		ok = nbits > from ?
 435			     (*fn)((ulong *)bh->b_data, from, nbits, ret) :
 436			     false;
 437		put_bh(bh);
 438
 439		if (ok) {
 440			*ret += 8 * vbo;
 441			return 0;
 442		}
 443
 444		if (++vblock >= eblock) {
 445			*ret = MINUS_ONE_T;
 446			return 0;
 447		}
 448	}
 449	blk = 0;
 450	vcn_next = vcn + clen;
 451	down_read(lock);
 452	ok = run_get_entry(run, ++idx, &vcn, &lcn, &clen) && vcn == vcn_next;
 453	if (!ok)
 454		vcn = vcn_next;
 455	up_read(lock);
 456	goto next_run;
 457}
 458
 459static bool scan_for_free(const ulong *buf, u32 bit, u32 bits, size_t *ret)
 460{
 461	size_t pos = find_next_zero_bit_le(buf, bits, bit);
 462
 463	if (pos >= bits)
 464		return false;
 465	*ret = pos;
 466	return true;
 467}
 468
 469/*
 470 * indx_find_free - Look for free bit.
 471 *
 472 * Return: -1 if no free bits.
 473 */
 474static int indx_find_free(struct ntfs_index *indx, struct ntfs_inode *ni,
 475			  size_t *bit, struct ATTRIB **bitmap)
 476{
 477	struct ATTRIB *b;
 478	struct ATTR_LIST_ENTRY *le = NULL;
 479	const struct INDEX_NAMES *in = &s_index_names[indx->type];
 480	int err;
 481
 482	b = ni_find_attr(ni, NULL, &le, ATTR_BITMAP, in->name, in->name_len,
 483			 NULL, NULL);
 484
 485	if (!b)
 486		return -ENOENT;
 487
 488	*bitmap = b;
 489	*bit = MINUS_ONE_T;
 490
 491	if (!b->non_res) {
 492		u32 nbits = 8 * le32_to_cpu(b->res.data_size);
 493		size_t pos = find_next_zero_bit_le(resident_data(b), nbits, 0);
 494
 495		if (pos < nbits)
 496			*bit = pos;
 497	} else {
 498		err = scan_nres_bitmap(ni, b, indx, 0, &scan_for_free, bit);
 499
 500		if (err)
 501			return err;
 502	}
 503
 504	return 0;
 505}
 506
 507static bool scan_for_used(const ulong *buf, u32 bit, u32 bits, size_t *ret)
 508{
 509	size_t pos = find_next_bit_le(buf, bits, bit);
 510
 511	if (pos >= bits)
 512		return false;
 513	*ret = pos;
 514	return true;
 515}
 516
 517/*
 518 * indx_used_bit - Look for used bit.
 519 *
 520 * Return: MINUS_ONE_T if no used bits.
 521 */
 522int indx_used_bit(struct ntfs_index *indx, struct ntfs_inode *ni, size_t *bit)
 523{
 524	struct ATTRIB *b;
 525	struct ATTR_LIST_ENTRY *le = NULL;
 526	size_t from = *bit;
 527	const struct INDEX_NAMES *in = &s_index_names[indx->type];
 528	int err;
 529
 530	b = ni_find_attr(ni, NULL, &le, ATTR_BITMAP, in->name, in->name_len,
 531			 NULL, NULL);
 532
 533	if (!b)
 534		return -ENOENT;
 535
 536	*bit = MINUS_ONE_T;
 537
 538	if (!b->non_res) {
 539		u32 nbits = le32_to_cpu(b->res.data_size) * 8;
 540		size_t pos = find_next_bit_le(resident_data(b), nbits, from);
 541
 542		if (pos < nbits)
 543			*bit = pos;
 544	} else {
 545		err = scan_nres_bitmap(ni, b, indx, from, &scan_for_used, bit);
 546		if (err)
 547			return err;
 548	}
 549
 550	return 0;
 551}
 552
 553/*
 554 * hdr_find_split
 555 *
 556 * Find a point at which the index allocation buffer would like to be split.
 557 * NOTE: This function should never return 'END' entry NULL returns on error.
 558 */
 559static const struct NTFS_DE *hdr_find_split(const struct INDEX_HDR *hdr)
 560{
 561	size_t o;
 562	const struct NTFS_DE *e = hdr_first_de(hdr);
 563	u32 used_2 = le32_to_cpu(hdr->used) >> 1;
 564	u16 esize;
 565
 566	if (!e || de_is_last(e))
 567		return NULL;
 568
 569	esize = le16_to_cpu(e->size);
 570	for (o = le32_to_cpu(hdr->de_off) + esize; o < used_2; o += esize) {
 571		const struct NTFS_DE *p = e;
 572
 573		e = Add2Ptr(hdr, o);
 574
 575		/* We must not return END entry. */
 576		if (de_is_last(e))
 577			return p;
 578
 579		esize = le16_to_cpu(e->size);
 580	}
 581
 582	return e;
 583}
 584
 585/*
 586 * hdr_insert_head - Insert some entries at the beginning of the buffer.
 587 *
 588 * It is used to insert entries into a newly-created buffer.
 589 */
 590static const struct NTFS_DE *hdr_insert_head(struct INDEX_HDR *hdr,
 591					     const void *ins, u32 ins_bytes)
 592{
 593	u32 to_move;
 594	struct NTFS_DE *e = hdr_first_de(hdr);
 595	u32 used = le32_to_cpu(hdr->used);
 596
 597	if (!e)
 598		return NULL;
 599
 600	/* Now we just make room for the inserted entries and jam it in. */
 601	to_move = used - le32_to_cpu(hdr->de_off);
 602	memmove(Add2Ptr(e, ins_bytes), e, to_move);
 603	memcpy(e, ins, ins_bytes);
 604	hdr->used = cpu_to_le32(used + ins_bytes);
 605
 606	return e;
 607}
 608
 609/*
 610 * index_hdr_check
 611 *
 612 * return true if INDEX_HDR is valid
 613 */
 614static bool index_hdr_check(const struct INDEX_HDR *hdr, u32 bytes)
 615{
 616	u32 end = le32_to_cpu(hdr->used);
 617	u32 tot = le32_to_cpu(hdr->total);
 618	u32 off = le32_to_cpu(hdr->de_off);
 619
 620	if (!IS_ALIGNED(off, 8) || tot > bytes || end > tot ||
 621	    size_add(off, sizeof(struct NTFS_DE)) > end) {
 622		/* incorrect index buffer. */
 623		return false;
 624	}
 625
 626	return true;
 627}
 628
 629/*
 630 * index_buf_check
 631 *
 632 * return true if INDEX_BUFFER seems is valid
 633 */
 634static bool index_buf_check(const struct INDEX_BUFFER *ib, u32 bytes,
 635			    const CLST *vbn)
 636{
 637	const struct NTFS_RECORD_HEADER *rhdr = &ib->rhdr;
 638	u16 fo = le16_to_cpu(rhdr->fix_off);
 639	u16 fn = le16_to_cpu(rhdr->fix_num);
 640
 641	if (bytes <= offsetof(struct INDEX_BUFFER, ihdr) ||
 642	    rhdr->sign != NTFS_INDX_SIGNATURE ||
 643	    fo < sizeof(struct INDEX_BUFFER)
 644	    /* Check index buffer vbn. */
 645	    || (vbn && *vbn != le64_to_cpu(ib->vbn)) || (fo % sizeof(short)) ||
 646	    fo + fn * sizeof(short) >= bytes ||
 647	    fn != ((bytes >> SECTOR_SHIFT) + 1)) {
 648		/* incorrect index buffer. */
 649		return false;
 650	}
 651
 652	return index_hdr_check(&ib->ihdr,
 653			       bytes - offsetof(struct INDEX_BUFFER, ihdr));
 654}
 655
 656void fnd_clear(struct ntfs_fnd *fnd)
 657{
 658	int i;
 659
 660	for (i = fnd->level - 1; i >= 0; i--) {
 661		struct indx_node *n = fnd->nodes[i];
 662
 663		if (!n)
 664			continue;
 665
 666		put_indx_node(n);
 667		fnd->nodes[i] = NULL;
 668	}
 669	fnd->level = 0;
 670	fnd->root_de = NULL;
 671}
 672
 673static int fnd_push(struct ntfs_fnd *fnd, struct indx_node *n,
 674		    struct NTFS_DE *e)
 675{
 676	int i = fnd->level;
 677
 678	if (i < 0 || i >= ARRAY_SIZE(fnd->nodes))
 679		return -EINVAL;
 680	fnd->nodes[i] = n;
 681	fnd->de[i] = e;
 682	fnd->level += 1;
 683	return 0;
 684}
 685
 686static struct indx_node *fnd_pop(struct ntfs_fnd *fnd)
 687{
 688	struct indx_node *n;
 689	int i = fnd->level;
 690
 691	i -= 1;
 692	n = fnd->nodes[i];
 693	fnd->nodes[i] = NULL;
 694	fnd->level = i;
 695
 696	return n;
 697}
 698
 699static bool fnd_is_empty(struct ntfs_fnd *fnd)
 700{
 701	if (!fnd->level)
 702		return !fnd->root_de;
 703
 704	return !fnd->de[fnd->level - 1];
 705}
 706
 707/*
 708 * hdr_find_e - Locate an entry the index buffer.
 709 *
 710 * If no matching entry is found, it returns the first entry which is greater
 711 * than the desired entry If the search key is greater than all the entries the
 712 * buffer, it returns the 'end' entry. This function does a binary search of the
 713 * current index buffer, for the first entry that is <= to the search value.
 714 *
 715 * Return: NULL if error.
 716 */
 717static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
 718				  const struct INDEX_HDR *hdr, const void *key,
 719				  size_t key_len, const void *ctx, int *diff)
 720{
 721	struct NTFS_DE *e, *found = NULL;
 722	NTFS_CMP_FUNC cmp = indx->cmp;
 723	int min_idx = 0, mid_idx, max_idx = 0;
 724	int diff2;
 725	int table_size = 8;
 726	u32 e_size, e_key_len;
 727	u32 end = le32_to_cpu(hdr->used);
 728	u32 off = le32_to_cpu(hdr->de_off);
 729	u32 total = le32_to_cpu(hdr->total);
 730	u16 offs[128];
 731
 732	if (unlikely(!cmp))
 733		return NULL;
 734
 735fill_table:
 736	if (end > total)
 737		return NULL;
 738
 739	if (size_add(off, sizeof(struct NTFS_DE)) > end)
 740		return NULL;
 741
 742	e = Add2Ptr(hdr, off);
 743	e_size = le16_to_cpu(e->size);
 744
 745	if (e_size < sizeof(struct NTFS_DE) || off + e_size > end)
 746		return NULL;
 747
 748	if (!de_is_last(e)) {
 749		offs[max_idx] = off;
 750		off += e_size;
 751
 752		max_idx++;
 753		if (max_idx < table_size)
 754			goto fill_table;
 755
 756		max_idx--;
 757	}
 758
 759binary_search:
 760	e_key_len = le16_to_cpu(e->key_size);
 761
 762	diff2 = (*cmp)(key, key_len, e + 1, e_key_len, ctx);
 763	if (diff2 > 0) {
 764		if (found) {
 765			min_idx = mid_idx + 1;
 766		} else {
 767			if (de_is_last(e))
 768				return NULL;
 769
 770			max_idx = 0;
 771			table_size = min(table_size * 2, (int)ARRAY_SIZE(offs));
 772			goto fill_table;
 773		}
 774	} else if (diff2 < 0) {
 775		if (found)
 776			max_idx = mid_idx - 1;
 777		else
 778			max_idx--;
 779
 780		found = e;
 781	} else {
 782		*diff = 0;
 783		return e;
 784	}
 785
 786	if (min_idx > max_idx) {
 787		*diff = -1;
 788		return found;
 789	}
 790
 791	mid_idx = (min_idx + max_idx) >> 1;
 792	e = Add2Ptr(hdr, offs[mid_idx]);
 793
 794	goto binary_search;
 795}
 796
 797/*
 798 * hdr_insert_de - Insert an index entry into the buffer.
 799 *
 800 * 'before' should be a pointer previously returned from hdr_find_e.
 801 */
 802static struct NTFS_DE *hdr_insert_de(const struct ntfs_index *indx,
 803				     struct INDEX_HDR *hdr,
 804				     const struct NTFS_DE *de,
 805				     struct NTFS_DE *before, const void *ctx)
 806{
 807	int diff;
 808	size_t off = PtrOffset(hdr, before);
 809	u32 used = le32_to_cpu(hdr->used);
 810	u32 total = le32_to_cpu(hdr->total);
 811	u16 de_size = le16_to_cpu(de->size);
 812
 813	/* First, check to see if there's enough room. */
 814	if (used + de_size > total)
 815		return NULL;
 816
 817	/* We know there's enough space, so we know we'll succeed. */
 818	if (before) {
 819		/* Check that before is inside Index. */
 820		if (off >= used || off < le32_to_cpu(hdr->de_off) ||
 821		    off + le16_to_cpu(before->size) > total) {
 822			return NULL;
 823		}
 824		goto ok;
 825	}
 826	/* No insert point is applied. Get it manually. */
 827	before = hdr_find_e(indx, hdr, de + 1, le16_to_cpu(de->key_size), ctx,
 828			    &diff);
 829	if (!before)
 830		return NULL;
 831	off = PtrOffset(hdr, before);
 832
 833ok:
 834	/* Now we just make room for the entry and jam it in. */
 835	memmove(Add2Ptr(before, de_size), before, used - off);
 836
 837	hdr->used = cpu_to_le32(used + de_size);
 838	memcpy(before, de, de_size);
 839
 840	return before;
 841}
 842
 843/*
 844 * hdr_delete_de - Remove an entry from the index buffer.
 845 */
 846static inline struct NTFS_DE *hdr_delete_de(struct INDEX_HDR *hdr,
 847					    struct NTFS_DE *re)
 848{
 849	u32 used = le32_to_cpu(hdr->used);
 850	u16 esize = le16_to_cpu(re->size);
 851	u32 off = PtrOffset(hdr, re);
 852	int bytes = used - (off + esize);
 853
 854	/* check INDEX_HDR valid before using INDEX_HDR */
 855	if (!check_index_header(hdr, le32_to_cpu(hdr->total)))
 856		return NULL;
 857
 858	if (off >= used || esize < sizeof(struct NTFS_DE) ||
 859	    bytes < sizeof(struct NTFS_DE))
 860		return NULL;
 861
 862	hdr->used = cpu_to_le32(used - esize);
 863	memmove(re, Add2Ptr(re, esize), bytes);
 864
 865	return re;
 866}
 867
 868void indx_clear(struct ntfs_index *indx)
 869{
 870	run_close(&indx->alloc_run);
 871	run_close(&indx->bitmap_run);
 872}
 873
 874int indx_init(struct ntfs_index *indx, struct ntfs_sb_info *sbi,
 875	      const struct ATTRIB *attr, enum index_mutex_classed type)
 876{
 877	u32 t32;
 878	const struct INDEX_ROOT *root = resident_data(attr);
 879
 880	t32 = le32_to_cpu(attr->res.data_size);
 881	if (t32 <= offsetof(struct INDEX_ROOT, ihdr) ||
 882	    !index_hdr_check(&root->ihdr,
 883			     t32 - offsetof(struct INDEX_ROOT, ihdr))) {
 884		goto out;
 885	}
 886
 887	/* Check root fields. */
 888	if (!root->index_block_clst)
 889		goto out;
 890
 891	indx->type = type;
 892	indx->idx2vbn_bits = __ffs(root->index_block_clst);
 893
 894	t32 = le32_to_cpu(root->index_block_size);
 895	indx->index_bits = blksize_bits(t32);
 896
 897	/* Check index record size. */
 898	if (t32 < sbi->cluster_size) {
 899		/* Index record is smaller than a cluster, use 512 blocks. */
 900		if (t32 != root->index_block_clst * SECTOR_SIZE)
 901			goto out;
 902
 903		/* Check alignment to a cluster. */
 904		if ((sbi->cluster_size >> SECTOR_SHIFT) &
 905		    (root->index_block_clst - 1)) {
 906			goto out;
 907		}
 908
 909		indx->vbn2vbo_bits = SECTOR_SHIFT;
 910	} else {
 911		/* Index record must be a multiple of cluster size. */
 912		if (t32 != root->index_block_clst << sbi->cluster_bits)
 913			goto out;
 914
 915		indx->vbn2vbo_bits = sbi->cluster_bits;
 916	}
 917
 918	init_rwsem(&indx->run_lock);
 919
 920	indx->cmp = get_cmp_func(root);
 921	if (!indx->cmp)
 922		goto out;
 923
 924	return 0;
 925
 926out:
 927	ntfs_set_state(sbi, NTFS_DIRTY_DIRTY);
 928	return -EINVAL;
 929}
 930
 931static struct indx_node *indx_new(struct ntfs_index *indx,
 932				  struct ntfs_inode *ni, CLST vbn,
 933				  const __le64 *sub_vbn)
 934{
 935	int err;
 936	struct NTFS_DE *e;
 937	struct indx_node *r;
 938	struct INDEX_HDR *hdr;
 939	struct INDEX_BUFFER *index;
 940	u64 vbo = (u64)vbn << indx->vbn2vbo_bits;
 941	u32 bytes = 1u << indx->index_bits;
 942	u16 fn;
 943	u32 eo;
 944
 945	r = kzalloc(sizeof(struct indx_node), GFP_NOFS);
 946	if (!r)
 947		return ERR_PTR(-ENOMEM);
 948
 949	index = kzalloc(bytes, GFP_NOFS);
 950	if (!index) {
 951		kfree(r);
 952		return ERR_PTR(-ENOMEM);
 953	}
 954
 955	err = ntfs_get_bh(ni->mi.sbi, &indx->alloc_run, vbo, bytes, &r->nb);
 956
 957	if (err) {
 958		kfree(index);
 959		kfree(r);
 960		return ERR_PTR(err);
 961	}
 962
 963	/* Create header. */
 964	index->rhdr.sign = NTFS_INDX_SIGNATURE;
 965	index->rhdr.fix_off = cpu_to_le16(sizeof(struct INDEX_BUFFER)); // 0x28
 966	fn = (bytes >> SECTOR_SHIFT) + 1; // 9
 967	index->rhdr.fix_num = cpu_to_le16(fn);
 968	index->vbn = cpu_to_le64(vbn);
 969	hdr = &index->ihdr;
 970	eo = ALIGN(sizeof(struct INDEX_BUFFER) + fn * sizeof(short), 8);
 971	hdr->de_off = cpu_to_le32(eo);
 972
 973	e = Add2Ptr(hdr, eo);
 974
 975	if (sub_vbn) {
 976		e->flags = NTFS_IE_LAST | NTFS_IE_HAS_SUBNODES;
 977		e->size = cpu_to_le16(sizeof(struct NTFS_DE) + sizeof(u64));
 978		hdr->used =
 979			cpu_to_le32(eo + sizeof(struct NTFS_DE) + sizeof(u64));
 980		de_set_vbn_le(e, *sub_vbn);
 981		hdr->flags = NTFS_INDEX_HDR_HAS_SUBNODES;
 982	} else {
 983		e->size = cpu_to_le16(sizeof(struct NTFS_DE));
 984		hdr->used = cpu_to_le32(eo + sizeof(struct NTFS_DE));
 985		e->flags = NTFS_IE_LAST;
 986	}
 987
 988	hdr->total = cpu_to_le32(bytes - offsetof(struct INDEX_BUFFER, ihdr));
 989
 990	r->index = index;
 991	return r;
 992}
 993
 994struct INDEX_ROOT *indx_get_root(struct ntfs_index *indx, struct ntfs_inode *ni,
 995				 struct ATTRIB **attr, struct mft_inode **mi)
 996{
 997	struct ATTR_LIST_ENTRY *le = NULL;
 998	struct ATTRIB *a;
 999	const struct INDEX_NAMES *in = &s_index_names[indx->type];
1000	struct INDEX_ROOT *root;
1001
1002	a = ni_find_attr(ni, NULL, &le, ATTR_ROOT, in->name, in->name_len, NULL,
1003			 mi);
1004	if (!a)
1005		return NULL;
1006
1007	if (attr)
1008		*attr = a;
1009
1010	root = resident_data_ex(a, sizeof(struct INDEX_ROOT));
1011
1012	/* length check */
1013	if (root &&
1014	    offsetof(struct INDEX_ROOT, ihdr) + le32_to_cpu(root->ihdr.used) >
1015		    le32_to_cpu(a->res.data_size)) {
1016		return NULL;
1017	}
1018
1019	return root;
1020}
1021
1022static int indx_write(struct ntfs_index *indx, struct ntfs_inode *ni,
1023		      struct indx_node *node, int sync)
1024{
1025	struct INDEX_BUFFER *ib = node->index;
1026
1027	return ntfs_write_bh(ni->mi.sbi, &ib->rhdr, &node->nb, sync);
1028}
1029
1030/*
1031 * indx_read
1032 *
1033 * If ntfs_readdir calls this function
1034 * inode is shared locked and no ni_lock.
1035 * Use rw_semaphore for read/write access to alloc_run.
1036 */
1037int indx_read(struct ntfs_index *indx, struct ntfs_inode *ni, CLST vbn,
1038	      struct indx_node **node)
1039{
1040	int err;
1041	struct INDEX_BUFFER *ib;
1042	struct runs_tree *run = &indx->alloc_run;
1043	struct rw_semaphore *lock = &indx->run_lock;
1044	u64 vbo = (u64)vbn << indx->vbn2vbo_bits;
1045	u32 bytes = 1u << indx->index_bits;
1046	struct indx_node *in = *node;
1047	const struct INDEX_NAMES *name;
1048
1049	if (!in) {
1050		in = kzalloc(sizeof(struct indx_node), GFP_NOFS);
1051		if (!in)
1052			return -ENOMEM;
1053	} else {
1054		nb_put(&in->nb);
1055	}
1056
1057	ib = in->index;
1058	if (!ib) {
1059		ib = kmalloc(bytes, GFP_NOFS);
1060		if (!ib) {
1061			err = -ENOMEM;
1062			goto out;
1063		}
1064	}
1065
1066	down_read(lock);
1067	err = ntfs_read_bh(ni->mi.sbi, run, vbo, &ib->rhdr, bytes, &in->nb);
1068	up_read(lock);
1069	if (!err)
1070		goto ok;
1071
1072	if (err == -E_NTFS_FIXUP)
1073		goto ok;
1074
1075	if (err != -ENOENT)
1076		goto out;
1077
1078	name = &s_index_names[indx->type];
1079	down_write(lock);
1080	err = attr_load_runs_range(ni, ATTR_ALLOC, name->name, name->name_len,
1081				   run, vbo, vbo + bytes);
1082	up_write(lock);
1083	if (err)
1084		goto out;
1085
1086	down_read(lock);
1087	err = ntfs_read_bh(ni->mi.sbi, run, vbo, &ib->rhdr, bytes, &in->nb);
1088	up_read(lock);
1089	if (err == -E_NTFS_FIXUP)
1090		goto ok;
1091
1092	if (err)
1093		goto out;
1094
1095ok:
1096	if (!index_buf_check(ib, bytes, &vbn)) {
1097		_ntfs_bad_inode(&ni->vfs_inode);
1098		err = -EINVAL;
1099		goto out;
1100	}
1101
1102	if (err == -E_NTFS_FIXUP) {
1103		ntfs_write_bh(ni->mi.sbi, &ib->rhdr, &in->nb, 0);
1104		err = 0;
1105	}
1106
1107	/* check for index header length */
1108	if (offsetof(struct INDEX_BUFFER, ihdr) + le32_to_cpu(ib->ihdr.used) >
1109	    bytes) {
1110		err = -EINVAL;
1111		goto out;
1112	}
1113
1114	in->index = ib;
1115	*node = in;
1116
1117out:
1118	if (err == -E_NTFS_CORRUPT) {
1119		_ntfs_bad_inode(&ni->vfs_inode);
1120		err = -EINVAL;
1121	}
1122
1123	if (ib != in->index)
1124		kfree(ib);
1125
1126	if (*node != in) {
1127		nb_put(&in->nb);
1128		kfree(in);
1129	}
1130
1131	return err;
1132}
1133
1134/*
1135 * indx_find - Scan NTFS directory for given entry.
1136 */
1137int indx_find(struct ntfs_index *indx, struct ntfs_inode *ni,
1138	      const struct INDEX_ROOT *root, const void *key, size_t key_len,
1139	      const void *ctx, int *diff, struct NTFS_DE **entry,
1140	      struct ntfs_fnd *fnd)
1141{
1142	int err;
1143	struct NTFS_DE *e;
1144	struct indx_node *node;
1145
1146	if (!root)
1147		root = indx_get_root(&ni->dir, ni, NULL, NULL);
1148
1149	if (!root) {
1150		/* Should not happen. */
1151		return -EINVAL;
1152	}
1153
1154	/* Check cache. */
1155	e = fnd->level ? fnd->de[fnd->level - 1] : fnd->root_de;
1156	if (e && !de_is_last(e) &&
1157	    !(*indx->cmp)(key, key_len, e + 1, le16_to_cpu(e->key_size), ctx)) {
1158		*entry = e;
1159		*diff = 0;
1160		return 0;
1161	}
1162
1163	/* Soft finder reset. */
1164	fnd_clear(fnd);
1165
1166	/* Lookup entry that is <= to the search value. */
1167	e = hdr_find_e(indx, &root->ihdr, key, key_len, ctx, diff);
1168	if (!e)
1169		return -EINVAL;
1170
1171	fnd->root_de = e;
1172
1173	for (;;) {
1174		node = NULL;
1175		if (*diff >= 0 || !de_has_vcn_ex(e))
1176			break;
1177
1178		/* Read next level. */
1179		err = indx_read(indx, ni, de_get_vbn(e), &node);
1180		if (err) {
1181			/* io error? */
1182			return err;
1183		}
1184
1185		/* Lookup entry that is <= to the search value. */
1186		e = hdr_find_e(indx, &node->index->ihdr, key, key_len, ctx,
1187			       diff);
1188		if (!e) {
1189			put_indx_node(node);
1190			return -EINVAL;
1191		}
1192
1193		err = fnd_push(fnd, node, e);
1194
1195		if (err) {
1196			put_indx_node(node);
1197			return err;
1198		}
1199	}
1200
1201	*entry = e;
1202	return 0;
1203}
1204
1205int indx_find_sort(struct ntfs_index *indx, struct ntfs_inode *ni,
1206		   const struct INDEX_ROOT *root, struct NTFS_DE **entry,
1207		   struct ntfs_fnd *fnd)
1208{
1209	int err;
1210	struct indx_node *n = NULL;
1211	struct NTFS_DE *e;
1212	size_t iter = 0;
1213	int level = fnd->level;
1214
1215	if (!*entry) {
1216		/* Start find. */
1217		e = hdr_first_de(&root->ihdr);
1218		if (!e)
1219			return 0;
1220		fnd_clear(fnd);
1221		fnd->root_de = e;
1222	} else if (!level) {
1223		if (de_is_last(fnd->root_de)) {
1224			*entry = NULL;
1225			return 0;
1226		}
1227
1228		e = hdr_next_de(&root->ihdr, fnd->root_de);
1229		if (!e)
1230			return -EINVAL;
1231		fnd->root_de = e;
1232	} else {
1233		n = fnd->nodes[level - 1];
1234		e = fnd->de[level - 1];
1235
1236		if (de_is_last(e))
1237			goto pop_level;
1238
1239		e = hdr_next_de(&n->index->ihdr, e);
1240		if (!e)
1241			return -EINVAL;
1242
1243		fnd->de[level - 1] = e;
1244	}
1245
1246	/* Just to avoid tree cycle. */
1247next_iter:
1248	if (iter++ >= 1000)
1249		return -EINVAL;
1250
1251	while (de_has_vcn_ex(e)) {
1252		if (le16_to_cpu(e->size) <
1253		    sizeof(struct NTFS_DE) + sizeof(u64)) {
1254			if (n) {
1255				fnd_pop(fnd);
1256				kfree(n);
1257			}
1258			return -EINVAL;
1259		}
1260
1261		/* Read next level. */
1262		err = indx_read(indx, ni, de_get_vbn(e), &n);
1263		if (err)
1264			return err;
1265
1266		/* Try next level. */
1267		e = hdr_first_de(&n->index->ihdr);
1268		if (!e) {
1269			kfree(n);
1270			return -EINVAL;
1271		}
1272
1273		fnd_push(fnd, n, e);
1274	}
1275
1276	if (le16_to_cpu(e->size) > sizeof(struct NTFS_DE)) {
1277		*entry = e;
1278		return 0;
1279	}
1280
1281pop_level:
1282	for (;;) {
1283		if (!de_is_last(e))
1284			goto next_iter;
1285
1286		/* Pop one level. */
1287		if (n) {
1288			fnd_pop(fnd);
1289			kfree(n);
1290		}
1291
1292		level = fnd->level;
1293
1294		if (level) {
1295			n = fnd->nodes[level - 1];
1296			e = fnd->de[level - 1];
1297		} else if (fnd->root_de) {
1298			n = NULL;
1299			e = fnd->root_de;
1300			fnd->root_de = NULL;
1301		} else {
1302			*entry = NULL;
1303			return 0;
1304		}
1305
1306		if (le16_to_cpu(e->size) > sizeof(struct NTFS_DE)) {
1307			*entry = e;
1308			if (!fnd->root_de)
1309				fnd->root_de = e;
1310			return 0;
1311		}
1312	}
1313}
1314
1315int indx_find_raw(struct ntfs_index *indx, struct ntfs_inode *ni,
1316		  const struct INDEX_ROOT *root, struct NTFS_DE **entry,
1317		  size_t *off, struct ntfs_fnd *fnd)
1318{
1319	int err;
1320	struct indx_node *n = NULL;
1321	struct NTFS_DE *e = NULL;
1322	struct NTFS_DE *e2;
1323	size_t bit;
1324	CLST next_used_vbn;
1325	CLST next_vbn;
1326	u32 record_size = ni->mi.sbi->record_size;
1327
1328	/* Use non sorted algorithm. */
1329	if (!*entry) {
1330		/* This is the first call. */
1331		e = hdr_first_de(&root->ihdr);
1332		if (!e)
1333			return 0;
1334		fnd_clear(fnd);
1335		fnd->root_de = e;
1336
1337		/* The first call with setup of initial element. */
1338		if (*off >= record_size) {
1339			next_vbn = (((*off - record_size) >> indx->index_bits))
1340				   << indx->idx2vbn_bits;
1341			/* Jump inside cycle 'for'. */
1342			goto next;
1343		}
1344
1345		/* Start enumeration from root. */
1346		*off = 0;
1347	} else if (!fnd->root_de)
1348		return -EINVAL;
1349
1350	for (;;) {
1351		/* Check if current entry can be used. */
1352		if (e && le16_to_cpu(e->size) > sizeof(struct NTFS_DE))
1353			goto ok;
1354
1355		if (!fnd->level) {
1356			/* Continue to enumerate root. */
1357			if (!de_is_last(fnd->root_de)) {
1358				e = hdr_next_de(&root->ihdr, fnd->root_de);
1359				if (!e)
1360					return -EINVAL;
1361				fnd->root_de = e;
1362				continue;
1363			}
1364
1365			/* Start to enumerate indexes from 0. */
1366			next_vbn = 0;
1367		} else {
1368			/* Continue to enumerate indexes. */
1369			e2 = fnd->de[fnd->level - 1];
1370
1371			n = fnd->nodes[fnd->level - 1];
1372
1373			if (!de_is_last(e2)) {
1374				e = hdr_next_de(&n->index->ihdr, e2);
1375				if (!e)
1376					return -EINVAL;
1377				fnd->de[fnd->level - 1] = e;
1378				continue;
1379			}
1380
1381			/* Continue with next index. */
1382			next_vbn = le64_to_cpu(n->index->vbn) +
1383				   root->index_block_clst;
1384		}
1385
1386next:
1387		/* Release current index. */
1388		if (n) {
1389			fnd_pop(fnd);
1390			put_indx_node(n);
1391			n = NULL;
1392		}
1393
1394		/* Skip all free indexes. */
1395		bit = next_vbn >> indx->idx2vbn_bits;
1396		err = indx_used_bit(indx, ni, &bit);
1397		if (err == -ENOENT || bit == MINUS_ONE_T) {
1398			/* No used indexes. */
1399			*entry = NULL;
1400			return 0;
1401		}
1402
1403		next_used_vbn = bit << indx->idx2vbn_bits;
1404
1405		/* Read buffer into memory. */
1406		err = indx_read(indx, ni, next_used_vbn, &n);
1407		if (err)
1408			return err;
1409
1410		e = hdr_first_de(&n->index->ihdr);
1411		fnd_push(fnd, n, e);
1412		if (!e)
1413			return -EINVAL;
1414	}
1415
1416ok:
1417	/* Return offset to restore enumerator if necessary. */
1418	if (!n) {
1419		/* 'e' points in root, */
1420		*off = PtrOffset(&root->ihdr, e);
1421	} else {
1422		/* 'e' points in index, */
1423		*off = (le64_to_cpu(n->index->vbn) << indx->vbn2vbo_bits) +
1424		       record_size + PtrOffset(&n->index->ihdr, e);
1425	}
1426
1427	*entry = e;
1428	return 0;
1429}
1430
1431/*
1432 * indx_create_allocate - Create "Allocation + Bitmap" attributes.
1433 */
1434static int indx_create_allocate(struct ntfs_index *indx, struct ntfs_inode *ni,
1435				CLST *vbn)
1436{
1437	int err;
1438	struct ntfs_sb_info *sbi = ni->mi.sbi;
1439	struct ATTRIB *bitmap;
1440	struct ATTRIB *alloc;
1441	u32 data_size = 1u << indx->index_bits;
1442	u32 alloc_size = ntfs_up_cluster(sbi, data_size);
1443	CLST len = alloc_size >> sbi->cluster_bits;
1444	const struct INDEX_NAMES *in = &s_index_names[indx->type];
1445	CLST alen;
1446	struct runs_tree run;
1447
1448	run_init(&run);
1449
1450	err = attr_allocate_clusters(sbi, &run, 0, 0, len, NULL, ALLOCATE_DEF,
1451				     &alen, 0, NULL, NULL);
1452	if (err)
1453		goto out;
1454
1455	err = ni_insert_nonresident(ni, ATTR_ALLOC, in->name, in->name_len,
1456				    &run, 0, len, 0, &alloc, NULL, NULL);
1457	if (err)
1458		goto out1;
1459
1460	alloc->nres.valid_size = alloc->nres.data_size = cpu_to_le64(data_size);
1461
1462	err = ni_insert_resident(ni, ntfs3_bitmap_size(1), ATTR_BITMAP,
1463				 in->name, in->name_len, &bitmap, NULL, NULL);
1464	if (err)
1465		goto out2;
1466
1467	if (in->name == I30_NAME) {
1468		i_size_write(&ni->vfs_inode, data_size);
1469		inode_set_bytes(&ni->vfs_inode, alloc_size);
1470	}
1471
1472	memcpy(&indx->alloc_run, &run, sizeof(run));
1473
1474	*vbn = 0;
1475
1476	return 0;
1477
1478out2:
1479	mi_remove_attr(NULL, &ni->mi, alloc);
1480
1481out1:
1482	run_deallocate(sbi, &run, false);
1483
1484out:
1485	return err;
1486}
1487
1488/*
1489 * indx_add_allocate - Add clusters to index.
1490 */
1491static int indx_add_allocate(struct ntfs_index *indx, struct ntfs_inode *ni,
1492			     CLST *vbn)
1493{
1494	int err;
1495	size_t bit;
1496	u64 data_size;
1497	u64 bmp_size, bmp_size_v;
1498	struct ATTRIB *bmp, *alloc;
1499	struct mft_inode *mi;
1500	const struct INDEX_NAMES *in = &s_index_names[indx->type];
1501
1502	err = indx_find_free(indx, ni, &bit, &bmp);
1503	if (err)
1504		goto out1;
1505
1506	if (bit != MINUS_ONE_T) {
1507		bmp = NULL;
1508	} else {
1509		if (bmp->non_res) {
1510			bmp_size = le64_to_cpu(bmp->nres.data_size);
1511			bmp_size_v = le64_to_cpu(bmp->nres.valid_size);
1512		} else {
1513			bmp_size = bmp_size_v = le32_to_cpu(bmp->res.data_size);
1514		}
1515
1516		/*
1517		 * Index blocks exist, but $BITMAP has zero valid bits.
1518		 * This implies an on-disk corruption and must be rejected.
1519		 */
1520		if (in->name == I30_NAME &&
1521		    unlikely(bmp_size_v == 0 && indx->alloc_run.count)) {
1522			err = -EINVAL;
1523			goto out1;
1524		}
1525
1526		bit = bmp_size << 3;
1527	}
1528
1529	data_size = (u64)(bit + 1) << indx->index_bits;
1530
1531	if (bmp) {
1532		/* Increase bitmap. */
1533		err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
1534				    &indx->bitmap_run,
1535				    ntfs3_bitmap_size(bit + 1), NULL, true,
1536				    NULL);
1537		if (err)
1538			goto out1;
1539	}
1540
1541	alloc = ni_find_attr(ni, NULL, NULL, ATTR_ALLOC, in->name, in->name_len,
1542			     NULL, &mi);
1543	if (!alloc) {
1544		err = -EINVAL;
1545		if (bmp)
1546			goto out2;
1547		goto out1;
1548	}
1549
1550	if (data_size <= le64_to_cpu(alloc->nres.data_size)) {
1551		/* Reuse index. */
1552		goto out;
1553	}
1554
1555	/* Increase allocation. */
1556	err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
1557			    &indx->alloc_run, data_size, &data_size, true,
1558			    NULL);
1559	if (err) {
1560		if (bmp)
1561			goto out2;
1562		goto out1;
1563	}
1564
1565	if (in->name == I30_NAME)
1566		i_size_write(&ni->vfs_inode, data_size);
1567
1568out:
1569	*vbn = bit << indx->idx2vbn_bits;
1570
1571	return 0;
1572
1573out2:
1574	/* Ops. No space? */
1575	attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
1576		      &indx->bitmap_run, bmp_size, &bmp_size_v, false, NULL);
1577
1578out1:
1579	return err;
1580}
1581
1582/*
1583 * indx_insert_into_root - Attempt to insert an entry into the index root.
1584 *
1585 * @undo - True if we undoing previous remove.
1586 * If necessary, it will twiddle the index b-tree.
1587 */
1588static int indx_insert_into_root(struct ntfs_index *indx, struct ntfs_inode *ni,
1589				 const struct NTFS_DE *new_de,
1590				 struct NTFS_DE *root_de, const void *ctx,
1591				 struct ntfs_fnd *fnd, bool undo)
1592{
1593	int err = 0;
1594	struct NTFS_DE *e, *e0, *re;
1595	struct mft_inode *mi;
1596	struct ATTRIB *attr;
1597	struct INDEX_HDR *hdr;
1598	struct indx_node *n;
1599	CLST new_vbn;
1600	__le64 *sub_vbn, t_vbn;
1601	u16 new_de_size;
1602	u32 hdr_used, hdr_total, asize, to_move;
1603	u32 root_size, new_root_size;
1604	struct ntfs_sb_info *sbi;
1605	int ds_root;
1606	struct INDEX_ROOT *root, *a_root;
1607
1608	/* Get the record this root placed in. */
1609	root = indx_get_root(indx, ni, &attr, &mi);
1610	if (!root)
1611		return -EINVAL;
1612
1613	/*
1614	 * Try easy case:
1615	 * hdr_insert_de will succeed if there's
1616	 * room the root for the new entry.
1617	 */
1618	hdr = &root->ihdr;
1619	sbi = ni->mi.sbi;
1620	new_de_size = le16_to_cpu(new_de->size);
1621	hdr_used = le32_to_cpu(hdr->used);
1622	hdr_total = le32_to_cpu(hdr->total);
1623	asize = le32_to_cpu(attr->size);
1624	root_size = le32_to_cpu(attr->res.data_size);
1625
1626	ds_root = new_de_size + hdr_used - hdr_total;
1627
1628	/* If 'undo' is set then reduce requirements. */
1629	if ((undo || asize + ds_root < sbi->max_bytes_per_attr) &&
1630	    mi_resize_attr(mi, attr, ds_root)) {
1631		hdr->total = cpu_to_le32(hdr_total + ds_root);
1632		e = hdr_insert_de(indx, hdr, new_de, root_de, ctx);
1633		WARN_ON(!e);
1634		fnd_clear(fnd);
1635		fnd->root_de = e;
1636
1637		return 0;
1638	}
1639
1640	/* Make a copy of root attribute to restore if error. */
1641	a_root = kmemdup(attr, asize, GFP_NOFS);
1642	if (!a_root)
1643		return -ENOMEM;
1644
1645	/*
1646	 * Copy all the non-end entries from
1647	 * the index root to the new buffer.
1648	 */
1649	to_move = 0;
1650	e0 = hdr_first_de(hdr);
1651
1652	/* Calculate the size to copy. */
1653	for (e = e0;; e = hdr_next_de(hdr, e)) {
1654		if (!e) {
1655			err = -EINVAL;
1656			goto out_free_root;
1657		}
1658
1659		if (de_is_last(e))
1660			break;
1661		to_move += le16_to_cpu(e->size);
1662	}
1663
1664	if (!to_move) {
1665		re = NULL;
1666	} else {
1667		re = kmemdup(e0, to_move, GFP_NOFS);
1668		if (!re) {
1669			err = -ENOMEM;
1670			goto out_free_root;
1671		}
1672	}
1673
1674	sub_vbn = NULL;
1675	if (de_has_vcn(e)) {
1676		t_vbn = de_get_vbn_le(e);
1677		sub_vbn = &t_vbn;
1678	}
1679
1680	new_root_size = sizeof(struct INDEX_ROOT) + sizeof(struct NTFS_DE) +
1681			sizeof(u64);
1682	ds_root = new_root_size - root_size;
1683
1684	if (ds_root > 0 && asize + ds_root > sbi->max_bytes_per_attr) {
1685		/* Make root external. */
1686		err = -EOPNOTSUPP;
1687		goto out_free_re;
1688	}
1689
1690	if (ds_root)
1691		mi_resize_attr(mi, attr, ds_root);
1692
1693	/* Fill first entry (vcn will be set later). */
1694	e = (struct NTFS_DE *)(root + 1);
1695	memset(e, 0, sizeof(struct NTFS_DE));
1696	e->size = cpu_to_le16(sizeof(struct NTFS_DE) + sizeof(u64));
1697	e->flags = NTFS_IE_HAS_SUBNODES | NTFS_IE_LAST;
1698
1699	hdr->flags = NTFS_INDEX_HDR_HAS_SUBNODES;
1700	hdr->used = hdr->total =
1701		cpu_to_le32(new_root_size - offsetof(struct INDEX_ROOT, ihdr));
1702
1703	fnd->root_de = hdr_first_de(hdr);
1704	mi->dirty = true;
1705
1706	/* Create alloc and bitmap attributes (if not). */
1707	err = run_is_empty(&indx->alloc_run) ?
1708		      indx_create_allocate(indx, ni, &new_vbn) :
1709		      indx_add_allocate(indx, ni, &new_vbn);
1710
1711	/* Layout of record may be changed, so rescan root. */
1712	root = indx_get_root(indx, ni, &attr, &mi);
1713	if (!root) {
1714		/* Bug? */
1715		ntfs_set_state(sbi, NTFS_DIRTY_ERROR);
1716		err = -EINVAL;
1717		goto out_free_re;
1718	}
1719
1720	if (err) {
1721		/* Restore root. */
1722		if (mi_resize_attr(mi, attr, -ds_root)) {
1723			memcpy(attr, a_root, asize);
1724		} else {
1725			/* Bug? */
1726			ntfs_set_state(sbi, NTFS_DIRTY_ERROR);
1727		}
1728		goto out_free_re;
1729	}
1730
1731	e = (struct NTFS_DE *)(root + 1);
1732	*(__le64 *)(e + 1) = cpu_to_le64(new_vbn);
1733	mi->dirty = true;
1734
1735	/* Now we can create/format the new buffer and copy the entries into. */
1736	n = indx_new(indx, ni, new_vbn, sub_vbn);
1737	if (IS_ERR(n)) {
1738		err = PTR_ERR(n);
1739		goto out_free_re;
1740	}
1741
1742	hdr = &n->index->ihdr;
1743	hdr_used = le32_to_cpu(hdr->used);
1744	hdr_total = le32_to_cpu(hdr->total);
1745
1746	/* Copy root entries into new buffer. */
1747	hdr_insert_head(hdr, re, to_move);
1748
1749	/* Update bitmap attribute. */
1750	indx_mark_used(indx, ni, new_vbn >> indx->idx2vbn_bits);
1751
1752	/* Check if we can insert new entry new index buffer. */
1753	if (hdr_used + new_de_size > hdr_total) {
1754		/*
1755		 * This occurs if MFT record is the same or bigger than index
1756		 * buffer. Move all root new index and have no space to add
1757		 * new entry classic case when MFT record is 1K and index
1758		 * buffer 4K the problem should not occurs.
1759		 */
1760		kfree(re);
1761		indx_write(indx, ni, n, 0);
1762
1763		put_indx_node(n);
1764		fnd_clear(fnd);
1765		err = indx_insert_entry(indx, ni, new_de, ctx, fnd, undo);
1766		goto out_free_root;
1767	}
1768
1769	/*
1770	 * Now root is a parent for new index buffer.
1771	 * Insert NewEntry a new buffer.
1772	 */
1773	e = hdr_insert_de(indx, hdr, new_de, NULL, ctx);
1774	if (!e) {
1775		err = -EINVAL;
1776		goto out_put_n;
1777	}
1778	fnd_push(fnd, n, e);
1779
1780	/* Just write updates index into disk. */
1781	indx_write(indx, ni, n, 0);
1782
1783	n = NULL;
1784
1785out_put_n:
1786	put_indx_node(n);
1787out_free_re:
1788	kfree(re);
1789out_free_root:
1790	kfree(a_root);
1791	return err;
1792}
1793
1794/*
1795 * indx_insert_into_buffer
1796 *
1797 * Attempt to insert an entry into an Index Allocation Buffer.
1798 * If necessary, it will split the buffer.
1799 */
1800static int
1801indx_insert_into_buffer(struct ntfs_index *indx, struct ntfs_inode *ni,
1802			struct INDEX_ROOT *root, const struct NTFS_DE *new_de,
1803			const void *ctx, int level, struct ntfs_fnd *fnd)
1804{
1805	int err;
1806	const struct NTFS_DE *sp;
1807	struct NTFS_DE *e, *de_t, *up_e;
1808	struct indx_node *n2;
1809	struct indx_node *n1 = fnd->nodes[level];
1810	struct INDEX_HDR *hdr1 = &n1->index->ihdr;
1811	struct INDEX_HDR *hdr2;
1812	u32 to_copy, used, used1;
1813	CLST new_vbn;
1814	__le64 t_vbn, *sub_vbn;
1815	u16 sp_size;
1816	void *hdr1_saved = NULL;
1817
1818	/* Try the most easy case. */
1819	e = fnd->level - 1 == level ? fnd->de[level] : NULL;
1820	e = hdr_insert_de(indx, hdr1, new_de, e, ctx);
1821	fnd->de[level] = e;
1822	if (e) {
1823		/* Just write updated index into disk. */
1824		indx_write(indx, ni, n1, 0);
1825		return 0;
1826	}
1827
1828	/*
1829	 * No space to insert into buffer. Split it.
1830	 * To split we:
1831	 *  - Save split point ('cause index buffers will be changed)
1832	 * - Allocate NewBuffer and copy all entries <= sp into new buffer
1833	 * - Remove all entries (sp including) from TargetBuffer
1834	 * - Insert NewEntry into left or right buffer (depending on sp <=>
1835	 *     NewEntry)
1836	 * - Insert sp into parent buffer (or root)
1837	 * - Make sp a parent for new buffer
1838	 */
1839	sp = hdr_find_split(hdr1);
1840	if (!sp)
1841		return -EINVAL;
1842
1843	sp_size = le16_to_cpu(sp->size);
1844	up_e = kmalloc(sp_size + sizeof(u64), GFP_NOFS);
1845	if (!up_e)
1846		return -ENOMEM;
1847	memcpy(up_e, sp, sp_size);
1848
1849	used1 = le32_to_cpu(hdr1->used);
1850	hdr1_saved = kmemdup(hdr1, used1, GFP_NOFS);
1851	if (!hdr1_saved) {
1852		err = -ENOMEM;
1853		goto out;
1854	}
1855
1856	if (!hdr1->flags) {
1857		up_e->flags |= NTFS_IE_HAS_SUBNODES;
1858		up_e->size = cpu_to_le16(sp_size + sizeof(u64));
1859		sub_vbn = NULL;
1860	} else {
1861		t_vbn = de_get_vbn_le(up_e);
1862		sub_vbn = &t_vbn;
1863	}
1864
1865	/* Allocate on disk a new index allocation buffer. */
1866	err = indx_add_allocate(indx, ni, &new_vbn);
1867	if (err)
1868		goto out;
1869
1870	/* Allocate and format memory a new index buffer. */
1871	n2 = indx_new(indx, ni, new_vbn, sub_vbn);
1872	if (IS_ERR(n2)) {
1873		err = PTR_ERR(n2);
1874		goto out;
1875	}
1876
1877	hdr2 = &n2->index->ihdr;
1878
1879	/* Make sp a parent for new buffer. */
1880	de_set_vbn(up_e, new_vbn);
1881
1882	/* Copy all the entries <= sp into the new buffer. */
1883	de_t = hdr_first_de(hdr1);
1884	to_copy = PtrOffset(de_t, sp);
1885	hdr_insert_head(hdr2, de_t, to_copy);
1886
1887	/* Remove all entries (sp including) from hdr1. */
1888	used = used1 - to_copy - sp_size;
1889	memmove(de_t, Add2Ptr(sp, sp_size), used - le32_to_cpu(hdr1->de_off));
1890	hdr1->used = cpu_to_le32(used);
1891
1892	/*
1893	 * Insert new entry into left or right buffer
1894	 * (depending on sp <=> new_de).
1895	 */
1896	hdr_insert_de(indx,
1897		      (*indx->cmp)(new_de + 1, le16_to_cpu(new_de->key_size),
1898				   up_e + 1, le16_to_cpu(up_e->key_size),
1899				   ctx) < 0 ?
1900			      hdr2 :
1901			      hdr1,
1902		      new_de, NULL, ctx);
1903
1904	indx_mark_used(indx, ni, new_vbn >> indx->idx2vbn_bits);
1905
1906	indx_write(indx, ni, n1, 0);
1907	indx_write(indx, ni, n2, 0);
1908
1909	put_indx_node(n2);
1910
1911	/*
1912	 * We've finished splitting everybody, so we are ready to
1913	 * insert the promoted entry into the parent.
1914	 */
1915	if (!level) {
1916		/* Insert in root. */
1917		err = indx_insert_into_root(indx, ni, up_e, NULL, ctx, fnd, 0);
1918	} else {
1919		/*
1920		 * The target buffer's parent is another index buffer.
1921		 * TODO: Remove recursion.
1922		 */
1923		err = indx_insert_into_buffer(indx, ni, root, up_e, ctx,
1924					      level - 1, fnd);
1925	}
1926
1927	if (err) {
1928		/*
1929		 * Undo critical operations.
1930		 */
1931		indx_mark_free(indx, ni, new_vbn >> indx->idx2vbn_bits);
1932		unsafe_memcpy(hdr1, hdr1_saved, used1,
1933			      "There are entries after the structure");
1934		indx_write(indx, ni, n1, 0);
1935	}
1936
1937out:
1938	kfree(up_e);
1939	kfree(hdr1_saved);
1940
1941	return err;
1942}
1943
1944/*
1945 * indx_insert_entry - Insert new entry into index.
1946 *
1947 * @undo - True if we undoing previous remove.
1948 */
1949int indx_insert_entry(struct ntfs_index *indx, struct ntfs_inode *ni,
1950		      const struct NTFS_DE *new_de, const void *ctx,
1951		      struct ntfs_fnd *fnd, bool undo)
1952{
1953	int err;
1954	int diff;
1955	struct NTFS_DE *e;
1956	struct ntfs_fnd *fnd_a = NULL;
1957	struct INDEX_ROOT *root;
1958
1959	if (!fnd) {
1960		fnd_a = fnd_get();
1961		if (!fnd_a) {
1962			err = -ENOMEM;
1963			goto out1;
1964		}
1965		fnd = fnd_a;
1966	}
1967
1968	root = indx_get_root(indx, ni, NULL, NULL);
1969	if (!root) {
1970		err = -EINVAL;
1971		goto out;
1972	}
1973
1974	if (fnd_is_empty(fnd)) {
1975		/*
1976		 * Find the spot the tree where we want to
1977		 * insert the new entry.
1978		 */
1979		err = indx_find(indx, ni, root, new_de + 1,
1980				le16_to_cpu(new_de->key_size), ctx, &diff, &e,
1981				fnd);
1982		if (err)
1983			goto out;
1984
1985		if (!diff) {
1986			err = -EEXIST;
1987			goto out;
1988		}
1989	}
1990
1991	if (!fnd->level) {
1992		/*
1993		 * The root is also a leaf, so we'll insert the
1994		 * new entry into it.
1995		 */
1996		err = indx_insert_into_root(indx, ni, new_de, fnd->root_de, ctx,
1997					    fnd, undo);
1998	} else {
1999		/*
2000		 * Found a leaf buffer, so we'll insert the new entry into it.
2001		 */
2002		err = indx_insert_into_buffer(indx, ni, root, new_de, ctx,
2003					      fnd->level - 1, fnd);
2004	}
2005
2006out:
2007	fnd_put(fnd_a);
2008out1:
2009	return err;
2010}
2011
2012/*
2013 * indx_find_buffer - Locate a buffer from the tree.
2014 */
2015static struct indx_node *indx_find_buffer(struct ntfs_index *indx,
2016					  struct ntfs_inode *ni,
2017					  const struct INDEX_ROOT *root,
2018					  __le64 vbn, struct indx_node *n)
2019{
2020	int err;
2021	const struct NTFS_DE *e;
2022	struct indx_node *r;
2023	const struct INDEX_HDR *hdr = n ? &n->index->ihdr : &root->ihdr;
2024
2025	/* Step 1: Scan one level. */
2026	for (e = hdr_first_de(hdr);; e = hdr_next_de(hdr, e)) {
2027		if (!e)
2028			return ERR_PTR(-EINVAL);
2029
2030		if (de_has_vcn(e) && vbn == de_get_vbn_le(e))
2031			return n;
2032
2033		if (de_is_last(e))
2034			break;
2035	}
2036
2037	/* Step2: Do recursion. */
2038	e = Add2Ptr(hdr, le32_to_cpu(hdr->de_off));
2039	for (;;) {
2040		if (de_has_vcn_ex(e)) {
2041			err = indx_read(indx, ni, de_get_vbn(e), &n);
2042			if (err)
2043				return ERR_PTR(err);
2044
2045			r = indx_find_buffer(indx, ni, root, vbn, n);
2046			if (r)
2047				return r;
2048		}
2049
2050		if (de_is_last(e))
2051			break;
2052
2053		e = Add2Ptr(e, le16_to_cpu(e->size));
2054	}
2055
2056	return NULL;
2057}
2058
2059/*
2060 * indx_shrink - Deallocate unused tail indexes.
2061 */
2062static int indx_shrink(struct ntfs_index *indx, struct ntfs_inode *ni,
2063		       size_t bit)
2064{
2065	int err = 0;
2066	u64 bpb, new_data;
2067	size_t nbits;
2068	struct ATTRIB *b;
2069	struct ATTR_LIST_ENTRY *le = NULL;
2070	const struct INDEX_NAMES *in = &s_index_names[indx->type];
2071
2072	b = ni_find_attr(ni, NULL, &le, ATTR_BITMAP, in->name, in->name_len,
2073			 NULL, NULL);
2074
2075	if (!b)
2076		return -ENOENT;
2077
2078	if (!b->non_res) {
2079		unsigned long pos;
2080		const unsigned long *bm = resident_data(b);
2081
2082		nbits = (size_t)le32_to_cpu(b->res.data_size) * 8;
2083
2084		if (bit >= nbits)
2085			return 0;
2086
2087		pos = find_next_bit_le(bm, nbits, bit);
2088		if (pos < nbits)
2089			return 0;
2090	} else {
2091		size_t used = MINUS_ONE_T;
2092
2093		nbits = le64_to_cpu(b->nres.data_size) * 8;
2094
2095		if (bit >= nbits)
2096			return 0;
2097
2098		err = scan_nres_bitmap(ni, b, indx, bit, &scan_for_used, &used);
2099		if (err)
2100			return err;
2101
2102		if (used != MINUS_ONE_T)
2103			return 0;
2104	}
2105
2106	new_data = (u64)bit << indx->index_bits;
2107
2108	err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
2109			    &indx->alloc_run, new_data, &new_data, false, NULL);
2110	if (err)
2111		return err;
2112
2113	if (in->name == I30_NAME)
2114		i_size_write(&ni->vfs_inode, new_data);
2115
2116	bpb = ntfs3_bitmap_size(bit);
2117	if (bpb * 8 == nbits)
2118		return 0;
2119
2120	err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
2121			    &indx->bitmap_run, bpb, &bpb, false, NULL);
2122
2123	return err;
2124}
2125
2126static int indx_free_children(struct ntfs_index *indx, struct ntfs_inode *ni,
2127			      const struct NTFS_DE *e, bool trim)
2128{
2129	int err;
2130	struct indx_node *n = NULL;
2131	struct INDEX_HDR *hdr;
2132	CLST vbn = de_get_vbn(e);
2133	size_t i;
2134
2135	err = indx_read(indx, ni, vbn, &n);
2136	if (err)
2137		return err;
2138
2139	hdr = &n->index->ihdr;
2140	/* First, recurse into the children, if any. */
2141	if (hdr_has_subnode(hdr)) {
2142		for (e = hdr_first_de(hdr); e; e = hdr_next_de(hdr, e)) {
2143			indx_free_children(indx, ni, e, false);
2144			if (de_is_last(e))
2145				break;
2146		}
2147	}
2148
2149	put_indx_node(n);
2150
2151	i = vbn >> indx->idx2vbn_bits;
2152	/*
2153	 * We've gotten rid of the children; add this buffer to the free list.
2154	 */
2155	indx_mark_free(indx, ni, i);
2156
2157	if (!trim)
2158		return 0;
2159
2160	/*
2161	 * If there are no used indexes after current free index
2162	 * then we can truncate allocation and bitmap.
2163	 * Use bitmap to estimate the case.
2164	 */
2165	indx_shrink(indx, ni, i + 1);
2166	return 0;
2167}
2168
2169/*
2170 * indx_get_entry_to_replace
2171 *
2172 * Find a replacement entry for a deleted entry.
2173 * Always returns a node entry:
2174 * NTFS_IE_HAS_SUBNODES is set the flags and the size includes the sub_vcn.
2175 */
2176static int indx_get_entry_to_replace(struct ntfs_index *indx,
2177				     struct ntfs_inode *ni,
2178				     const struct NTFS_DE *de_next,
2179				     struct NTFS_DE **de_to_replace,
2180				     struct ntfs_fnd *fnd)
2181{
2182	int err;
2183	int level = -1;
2184	CLST vbn;
2185	struct NTFS_DE *e, *te, *re;
2186	struct indx_node *n;
2187	struct INDEX_BUFFER *ib;
2188
2189	*de_to_replace = NULL;
2190
2191	/* Find first leaf entry down from de_next. */
2192	vbn = de_get_vbn(de_next);
2193	for (;;) {
2194		n = NULL;
2195		err = indx_read(indx, ni, vbn, &n);
2196		if (err)
2197			goto out;
2198
2199		e = hdr_first_de(&n->index->ihdr);
2200		fnd_push(fnd, n, e);
2201		if (!e) {
2202			err = -EINVAL;
2203			goto out;
2204		}
2205
2206		if (!de_is_last(e)) {
2207			/*
2208			 * This buffer is non-empty, so its first entry
2209			 * could be used as the replacement entry.
2210			 */
2211			level = fnd->level - 1;
2212		}
2213
2214		if (!de_has_vcn(e))
2215			break;
2216
2217		/* This buffer is a node. Continue to go down. */
2218		vbn = de_get_vbn(e);
2219	}
2220
2221	if (level == -1)
2222		goto out;
2223
2224	n = fnd->nodes[level];
2225	te = hdr_first_de(&n->index->ihdr);
2226	if (!te) {
2227		err = -EINVAL;
2228		goto out;
2229	}
2230	/* Copy the candidate entry into the replacement entry buffer. */
2231	re = kmalloc(le16_to_cpu(te->size) + sizeof(u64), GFP_NOFS);
2232	if (!re) {
2233		err = -ENOMEM;
2234		goto out;
2235	}
2236
2237	*de_to_replace = re;
2238	memcpy(re, te, le16_to_cpu(te->size));
2239
2240	if (!de_has_vcn(re)) {
2241		/*
2242		 * The replacement entry we found doesn't have a sub_vcn.
2243		 * increase its size to hold one.
2244		 */
2245		le16_add_cpu(&re->size, sizeof(u64));
2246		re->flags |= NTFS_IE_HAS_SUBNODES;
2247	} else {
2248		/*
2249		 * The replacement entry we found was a node entry, which
2250		 * means that all its child buffers are empty. Return them
2251		 * to the free pool.
2252		 */
2253		indx_free_children(indx, ni, te, true);
2254	}
2255
2256	/*
2257	 * Expunge the replacement entry from its former location,
2258	 * and then write that buffer.
2259	 */
2260	ib = n->index;
2261	e = hdr_delete_de(&ib->ihdr, te);
2262
2263	fnd->de[level] = e;
2264	indx_write(indx, ni, n, 0);
2265
2266	if (ib_is_leaf(ib) && ib_is_empty(ib)) {
2267		/* An empty leaf. */
2268		return 0;
2269	}
2270
2271out:
2272	fnd_clear(fnd);
2273	return err;
2274}
2275
2276/*
2277 * indx_delete_entry - Delete an entry from the index.
2278 */
2279int indx_delete_entry(struct ntfs_index *indx, struct ntfs_inode *ni,
2280		      const void *key, u32 key_len, const void *ctx)
2281{
2282	int err, diff;
2283	struct INDEX_ROOT *root;
2284	struct INDEX_HDR *hdr;
2285	struct ntfs_fnd *fnd, *fnd2;
2286	struct INDEX_BUFFER *ib;
2287	struct NTFS_DE *e, *re, *next, *prev, *me;
2288	struct indx_node *n, *n2d = NULL;
2289	__le64 sub_vbn;
2290	int level, level2;
2291	struct ATTRIB *attr;
2292	struct mft_inode *mi;
2293	u32 e_size, root_size, new_root_size;
2294	size_t trim_bit;
2295	const struct INDEX_NAMES *in;
2296
2297	fnd = fnd_get();
2298	if (!fnd) {
2299		err = -ENOMEM;
2300		goto out2;
2301	}
2302
2303	fnd2 = fnd_get();
2304	if (!fnd2) {
2305		err = -ENOMEM;
2306		goto out1;
2307	}
2308
2309	root = indx_get_root(indx, ni, &attr, &mi);
2310	if (!root) {
2311		err = -EINVAL;
2312		goto out;
2313	}
2314
2315	/* Locate the entry to remove. */
2316	err = indx_find(indx, ni, root, key, key_len, ctx, &diff, &e, fnd);
2317	if (err)
2318		goto out;
2319
2320	if (!e || diff) {
2321		err = -ENOENT;
2322		goto out;
2323	}
2324
2325	level = fnd->level;
2326
2327	if (level) {
2328		n = fnd->nodes[level - 1];
2329		e = fnd->de[level - 1];
2330		ib = n->index;
2331		hdr = &ib->ihdr;
2332	} else {
2333		hdr = &root->ihdr;
2334		e = fnd->root_de;
2335		n = NULL;
2336	}
2337
2338	e_size = le16_to_cpu(e->size);
2339
2340	if (!de_has_vcn_ex(e)) {
2341		/* The entry to delete is a leaf, so we can just rip it out. */
2342		hdr_delete_de(hdr, e);
2343
2344		if (!level) {
2345			hdr->total = hdr->used;
2346
2347			/* Shrink resident root attribute. */
2348			mi_resize_attr(mi, attr, 0 - e_size);
2349			goto out;
2350		}
2351
2352		indx_write(indx, ni, n, 0);
2353
2354		/*
2355		 * Check to see if removing that entry made
2356		 * the leaf empty.
2357		 */
2358		if (ib_is_leaf(ib) && ib_is_empty(ib)) {
2359			fnd_pop(fnd);
2360			fnd_push(fnd2, n, e);
2361		}
2362	} else {
2363		/*
2364		 * The entry we wish to delete is a node buffer, so we
2365		 * have to find a replacement for it.
2366		 */
2367		next = de_get_next(e);
2368
2369		err = indx_get_entry_to_replace(indx, ni, next, &re, fnd2);
2370		if (err)
2371			goto out;
2372
2373		if (re) {
2374			de_set_vbn_le(re, de_get_vbn_le(e));
2375			hdr_delete_de(hdr, e);
2376
2377			err = level ? indx_insert_into_buffer(indx, ni, root,
2378							      re, ctx,
2379							      fnd->level - 1,
2380							      fnd) :
2381				      indx_insert_into_root(indx, ni, re, e,
2382							    ctx, fnd, 0);
2383			kfree(re);
2384
2385			if (err)
2386				goto out;
2387		} else {
2388			/*
2389			 * There is no replacement for the current entry.
2390			 * This means that the subtree rooted at its node
2391			 * is empty, and can be deleted, which turn means
2392			 * that the node can just inherit the deleted
2393			 * entry sub_vcn.
2394			 */
2395			indx_free_children(indx, ni, next, true);
2396
2397			de_set_vbn_le(next, de_get_vbn_le(e));
2398			hdr_delete_de(hdr, e);
2399			if (level) {
2400				indx_write(indx, ni, n, 0);
2401			} else {
2402				hdr->total = hdr->used;
2403
2404				/* Shrink resident root attribute. */
2405				mi_resize_attr(mi, attr, 0 - e_size);
2406			}
2407		}
2408	}
2409
2410	/* Delete a branch of tree. */
2411	if (!fnd2 || !fnd2->level)
2412		goto out;
2413
2414	/* Reinit root 'cause it can be changed. */
2415	root = indx_get_root(indx, ni, &attr, &mi);
2416	if (!root) {
2417		err = -EINVAL;
2418		goto out;
2419	}
2420
2421	n2d = NULL;
2422	sub_vbn = fnd2->nodes[0]->index->vbn;
2423	level2 = 0;
2424	level = fnd->level;
2425
2426	hdr = level ? &fnd->nodes[level - 1]->index->ihdr : &root->ihdr;
2427
2428	/* Scan current level. */
2429	for (e = hdr_first_de(hdr);; e = hdr_next_de(hdr, e)) {
2430		if (!e) {
2431			err = -EINVAL;
2432			goto out;
2433		}
2434
2435		if (de_has_vcn(e) && sub_vbn == de_get_vbn_le(e))
2436			break;
2437
2438		if (de_is_last(e)) {
2439			e = NULL;
2440			break;
2441		}
2442	}
2443
2444	if (!e) {
2445		/* Do slow search from root. */
2446		struct indx_node *in;
2447
2448		fnd_clear(fnd);
2449
2450		in = indx_find_buffer(indx, ni, root, sub_vbn, NULL);
2451		if (IS_ERR(in)) {
2452			err = PTR_ERR(in);
2453			goto out;
2454		}
2455
2456		if (in)
2457			fnd_push(fnd, in, NULL);
2458	}
2459
2460	/* Merge fnd2 -> fnd. */
2461	for (level = 0; level < fnd2->level; level++) {
2462		fnd_push(fnd, fnd2->nodes[level], fnd2->de[level]);
2463		fnd2->nodes[level] = NULL;
2464	}
2465	fnd2->level = 0;
2466
2467	hdr = NULL;
2468	for (level = fnd->level; level; level--) {
2469		struct indx_node *in = fnd->nodes[level - 1];
2470
2471		ib = in->index;
2472		if (ib_is_empty(ib)) {
2473			sub_vbn = ib->vbn;
2474		} else {
2475			hdr = &ib->ihdr;
2476			n2d = in;
2477			level2 = level;
2478			break;
2479		}
2480	}
2481
2482	if (!hdr)
2483		hdr = &root->ihdr;
2484
2485	e = hdr_first_de(hdr);
2486	if (!e) {
2487		err = -EINVAL;
2488		goto out;
2489	}
2490
2491	if (hdr != &root->ihdr || !de_is_last(e)) {
2492		prev = NULL;
2493		while (!de_is_last(e)) {
2494			if (de_has_vcn(e) && sub_vbn == de_get_vbn_le(e))
2495				break;
2496			prev = e;
2497			e = hdr_next_de(hdr, e);
2498			if (!e) {
2499				err = -EINVAL;
2500				goto out;
2501			}
2502		}
2503
2504		if (sub_vbn != de_get_vbn_le(e)) {
2505			/*
2506			 * Didn't find the parent entry, although this buffer
2507			 * is the parent trail. Something is corrupt.
2508			 */
2509			err = -EINVAL;
2510			goto out;
2511		}
2512
2513		if (de_is_last(e)) {
2514			/*
2515			 * Since we can't remove the end entry, we'll remove
2516			 * its predecessor instead. This means we have to
2517			 * transfer the predecessor's sub_vcn to the end entry.
2518			 * Note: This index block is not empty, so the
2519			 * predecessor must exist.
2520			 */
2521			if (!prev) {
2522				err = -EINVAL;
2523				goto out;
2524			}
2525
2526			if (de_has_vcn(prev)) {
2527				de_set_vbn_le(e, de_get_vbn_le(prev));
2528			} else if (de_has_vcn(e)) {
2529				le16_sub_cpu(&e->size, sizeof(u64));
2530				e->flags &= ~NTFS_IE_HAS_SUBNODES;
2531				le32_sub_cpu(&hdr->used, sizeof(u64));
2532			}
2533			e = prev;
2534		}
2535
2536		/*
2537		 * Copy the current entry into a temporary buffer (stripping
2538		 * off its down-pointer, if any) and delete it from the current
2539		 * buffer or root, as appropriate.
2540		 */
2541		e_size = le16_to_cpu(e->size);
2542		me = kmemdup(e, e_size, GFP_NOFS);
2543		if (!me) {
2544			err = -ENOMEM;
2545			goto out;
2546		}
2547
2548		if (de_has_vcn(me)) {
2549			me->flags &= ~NTFS_IE_HAS_SUBNODES;
2550			le16_sub_cpu(&me->size, sizeof(u64));
2551		}
2552
2553		hdr_delete_de(hdr, e);
2554
2555		if (hdr == &root->ihdr) {
2556			level = 0;
2557			hdr->total = hdr->used;
2558
2559			/* Shrink resident root attribute. */
2560			mi_resize_attr(mi, attr, 0 - e_size);
2561		} else {
2562			indx_write(indx, ni, n2d, 0);
2563			level = level2;
2564		}
2565
2566		/* Mark unused buffers as free. */
2567		trim_bit = -1;
2568		for (; level < fnd->level; level++) {
2569			ib = fnd->nodes[level]->index;
2570			if (ib_is_empty(ib)) {
2571				size_t k = le64_to_cpu(ib->vbn) >>
2572					   indx->idx2vbn_bits;
2573
2574				indx_mark_free(indx, ni, k);
2575				if (k < trim_bit)
2576					trim_bit = k;
2577			}
2578		}
2579
2580		fnd_clear(fnd);
2581		/*fnd->root_de = NULL;*/
2582
2583		/*
2584		 * Re-insert the entry into the tree.
2585		 * Find the spot the tree where we want to insert the new entry.
2586		 */
2587		err = indx_insert_entry(indx, ni, me, ctx, fnd, 0);
2588		kfree(me);
2589		if (err)
2590			goto out;
2591
2592		if (trim_bit != -1)
2593			indx_shrink(indx, ni, trim_bit);
2594	} else {
2595		/*
2596		 * This tree needs to be collapsed down to an empty root.
2597		 * Recreate the index root as an empty leaf and free all
2598		 * the bits the index allocation bitmap.
2599		 */
2600		fnd_clear(fnd);
2601		fnd_clear(fnd2);
2602
2603		in = &s_index_names[indx->type];
2604
2605		err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
2606				    &indx->alloc_run, 0, NULL, false, NULL);
2607		if (in->name == I30_NAME)
2608			i_size_write(&ni->vfs_inode, 0);
2609
2610		err = ni_remove_attr(ni, ATTR_ALLOC, in->name, in->name_len,
2611				     false, NULL);
2612		run_close(&indx->alloc_run);
2613
2614		err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
2615				    &indx->bitmap_run, 0, NULL, false, NULL);
2616		err = ni_remove_attr(ni, ATTR_BITMAP, in->name, in->name_len,
2617				     false, NULL);
2618		run_close(&indx->bitmap_run);
2619
2620		root = indx_get_root(indx, ni, &attr, &mi);
2621		if (!root) {
2622			err = -EINVAL;
2623			goto out;
2624		}
2625
2626		root_size = le32_to_cpu(attr->res.data_size);
2627		new_root_size =
2628			sizeof(struct INDEX_ROOT) + sizeof(struct NTFS_DE);
2629
2630		if (new_root_size != root_size &&
2631		    !mi_resize_attr(mi, attr, new_root_size - root_size)) {
2632			err = -EINVAL;
2633			goto out;
2634		}
2635
2636		/* Fill first entry. */
2637		e = (struct NTFS_DE *)(root + 1);
2638		e->ref.low = 0;
2639		e->ref.high = 0;
2640		e->ref.seq = 0;
2641		e->size = cpu_to_le16(sizeof(struct NTFS_DE));
2642		e->flags = NTFS_IE_LAST; // 0x02
2643		e->key_size = 0;
2644		e->res = 0;
2645
2646		hdr = &root->ihdr;
2647		hdr->flags = 0;
2648		hdr->used = hdr->total = cpu_to_le32(
2649			new_root_size - offsetof(struct INDEX_ROOT, ihdr));
2650		mi->dirty = true;
2651	}
2652
2653out:
2654	fnd_put(fnd2);
2655out1:
2656	fnd_put(fnd);
2657out2:
2658	return err;
2659}
2660
2661/*
2662 * Update duplicated information in directory entry
2663 * 'dup' - info from MFT record
2664 */
2665int indx_update_dup(struct ntfs_inode *ni, struct ntfs_sb_info *sbi,
2666		    const struct ATTR_FILE_NAME *fname,
2667		    const struct NTFS_DUP_INFO *dup, int sync)
2668{
2669	int err, diff;
2670	struct NTFS_DE *e = NULL;
2671	struct ATTR_FILE_NAME *e_fname;
2672	struct ntfs_fnd *fnd;
2673	struct INDEX_ROOT *root;
2674	struct mft_inode *mi;
2675	struct ntfs_index *indx = &ni->dir;
2676
2677	fnd = fnd_get();
2678	if (!fnd)
2679		return -ENOMEM;
2680
2681	root = indx_get_root(indx, ni, NULL, &mi);
2682	if (!root) {
2683		err = -EINVAL;
2684		goto out;
2685	}
2686
2687	/* Find entry in directory. */
2688	err = indx_find(indx, ni, root, fname, fname_full_size(fname), sbi,
2689			&diff, &e, fnd);
2690	if (err)
2691		goto out;
2692
2693	if (!e) {
2694		err = -EINVAL;
2695		goto out;
2696	}
2697
2698	if (diff) {
2699		err = -EINVAL;
2700		goto out;
2701	}
2702
2703	e_fname = (struct ATTR_FILE_NAME *)(e + 1);
2704
2705	if (!memcmp(&e_fname->dup, dup, sizeof(*dup))) {
2706		/*
2707		 * Nothing to update in index! Try to avoid this call.
2708		 */
2709		goto out;
2710	}
2711
2712	memcpy(&e_fname->dup, dup, sizeof(*dup));
2713
2714	if (fnd->level) {
2715		/* Directory entry in index. */
2716		err = indx_write(indx, ni, fnd->nodes[fnd->level - 1], sync);
2717	} else {
2718		/* Directory entry in directory MFT record. */
2719		mi->dirty = true;
2720		if (sync)
2721			err = mi_write(mi, 1);
2722		else
2723			mark_inode_dirty(&ni->vfs_inode);
2724	}
2725
2726out:
2727	fnd_put(fnd);
2728	return err;
2729}