xref: /linux/fs/ntfs3/index.c (revision ce335806b5ecc5132aed0a1af8bd48ae3b2ea178)
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 
17 static 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  */
cmp_fnames(const void * key1,size_t l1,const void * key2,size_t l2,const void * data)34 static 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  */
cmp_uint(const void * key1,size_t l1,const void * key2,size_t l2,const void * data)69 static 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  */
cmp_sdh(const void * key1,size_t l1,const void * key2,size_t l2,const void * data)88 static 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  */
cmp_uints(const void * key1,size_t l1,const void * key2,size_t l2,const void * data)123 static 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 
get_cmp_func(const struct INDEX_ROOT * root)168 static 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 
194 struct 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 
bmp_buf_get(struct ntfs_index * indx,struct ntfs_inode * ni,size_t bit,struct bmp_buf * bbuf)204 static 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 
bmp_buf_put(struct bmp_buf * bbuf,bool dirty)286 static 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 
308 out:
309 	unlock_buffer(bh);
310 	put_bh(bh);
311 }
312 
313 /*
314  * indx_mark_used - Mark the bit @bit as used.
315  */
indx_mark_used(struct ntfs_index * indx,struct ntfs_inode * ni,size_t bit)316 static 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  */
indx_mark_free(struct ntfs_index * indx,struct ntfs_inode * ni,size_t bit)336 static 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  */
scan_nres_bitmap(struct ntfs_inode * ni,struct ATTRIB * bitmap,struct ntfs_index * indx,size_t from,bool (* fn)(const ulong * buf,u32 bit,u32 bits,size_t * ret),size_t * ret)360 static 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 
396 next_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 
scan_for_free(const ulong * buf,u32 bit,u32 bits,size_t * ret)459 static 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  */
indx_find_free(struct ntfs_index * indx,struct ntfs_inode * ni,size_t * bit,struct ATTRIB ** bitmap)474 static 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 
scan_for_used(const ulong * buf,u32 bit,u32 bits,size_t * ret)507 static 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  */
indx_used_bit(struct ntfs_index * indx,struct ntfs_inode * ni,size_t * bit)522 int 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  */
hdr_find_split(const struct INDEX_HDR * hdr)559 static 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  */
hdr_insert_head(struct INDEX_HDR * hdr,const void * ins,u32 ins_bytes)590 static 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  */
index_hdr_check(const struct INDEX_HDR * hdr,u32 bytes)614 static 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 	    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  */
index_buf_check(const struct INDEX_BUFFER * ib,u32 bytes,const CLST * vbn)634 static 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 
fnd_clear(struct ntfs_fnd * fnd)656 void 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 
fnd_push(struct ntfs_fnd * fnd,struct indx_node * n,struct NTFS_DE * e)673 static 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 
fnd_pop(struct ntfs_fnd * fnd)686 static 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 
fnd_is_empty(struct ntfs_fnd * fnd)699 static 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  */
hdr_find_e(const struct ntfs_index * indx,const struct INDEX_HDR * hdr,const void * key,size_t key_len,const void * ctx,int * diff)717 static 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 
735 fill_table:
736 	if (end > total)
737 		return NULL;
738 
739 	if (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 
759 binary_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  */
hdr_insert_de(const struct ntfs_index * indx,struct INDEX_HDR * hdr,const struct NTFS_DE * de,struct NTFS_DE * before,const void * ctx)802 static 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 
833 ok:
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  */
hdr_delete_de(struct INDEX_HDR * hdr,struct NTFS_DE * re)846 static 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 
indx_clear(struct ntfs_index * indx)868 void indx_clear(struct ntfs_index *indx)
869 {
870 	run_close(&indx->alloc_run);
871 	run_close(&indx->bitmap_run);
872 }
873 
indx_init(struct ntfs_index * indx,struct ntfs_sb_info * sbi,const struct ATTRIB * attr,enum index_mutex_classed type)874 int 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 
926 out:
927 	ntfs_set_state(sbi, NTFS_DIRTY_DIRTY);
928 	return -EINVAL;
929 }
930 
indx_new(struct ntfs_index * indx,struct ntfs_inode * ni,CLST vbn,const __le64 * sub_vbn)931 static 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 
indx_get_root(struct ntfs_index * indx,struct ntfs_inode * ni,struct ATTRIB ** attr,struct mft_inode ** mi)994 struct 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 
indx_write(struct ntfs_index * indx,struct ntfs_inode * ni,struct indx_node * node,int sync)1022 static 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  */
indx_read(struct ntfs_index * indx,struct ntfs_inode * ni,CLST vbn,struct indx_node ** node)1037 int 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 
1095 ok:
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 
1117 out:
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  */
indx_find(struct ntfs_index * indx,struct ntfs_inode * ni,const struct INDEX_ROOT * root,const void * key,size_t key_len,const void * ctx,int * diff,struct NTFS_DE ** entry,struct ntfs_fnd * fnd)1137 int 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 		fnd_push(fnd, node, e);
1194 	}
1195 
1196 	*entry = e;
1197 	return 0;
1198 }
1199 
indx_find_sort(struct ntfs_index * indx,struct ntfs_inode * ni,const struct INDEX_ROOT * root,struct NTFS_DE ** entry,struct ntfs_fnd * fnd)1200 int indx_find_sort(struct ntfs_index *indx, struct ntfs_inode *ni,
1201 		   const struct INDEX_ROOT *root, struct NTFS_DE **entry,
1202 		   struct ntfs_fnd *fnd)
1203 {
1204 	int err;
1205 	struct indx_node *n = NULL;
1206 	struct NTFS_DE *e;
1207 	size_t iter = 0;
1208 	int level = fnd->level;
1209 
1210 	if (!*entry) {
1211 		/* Start find. */
1212 		e = hdr_first_de(&root->ihdr);
1213 		if (!e)
1214 			return 0;
1215 		fnd_clear(fnd);
1216 		fnd->root_de = e;
1217 	} else if (!level) {
1218 		if (de_is_last(fnd->root_de)) {
1219 			*entry = NULL;
1220 			return 0;
1221 		}
1222 
1223 		e = hdr_next_de(&root->ihdr, fnd->root_de);
1224 		if (!e)
1225 			return -EINVAL;
1226 		fnd->root_de = e;
1227 	} else {
1228 		n = fnd->nodes[level - 1];
1229 		e = fnd->de[level - 1];
1230 
1231 		if (de_is_last(e))
1232 			goto pop_level;
1233 
1234 		e = hdr_next_de(&n->index->ihdr, e);
1235 		if (!e)
1236 			return -EINVAL;
1237 
1238 		fnd->de[level - 1] = e;
1239 	}
1240 
1241 	/* Just to avoid tree cycle. */
1242 next_iter:
1243 	if (iter++ >= 1000)
1244 		return -EINVAL;
1245 
1246 	while (de_has_vcn_ex(e)) {
1247 		if (le16_to_cpu(e->size) <
1248 		    sizeof(struct NTFS_DE) + sizeof(u64)) {
1249 			if (n) {
1250 				fnd_pop(fnd);
1251 				kfree(n);
1252 			}
1253 			return -EINVAL;
1254 		}
1255 
1256 		/* Read next level. */
1257 		err = indx_read(indx, ni, de_get_vbn(e), &n);
1258 		if (err)
1259 			return err;
1260 
1261 		/* Try next level. */
1262 		e = hdr_first_de(&n->index->ihdr);
1263 		if (!e) {
1264 			kfree(n);
1265 			return -EINVAL;
1266 		}
1267 
1268 		fnd_push(fnd, n, e);
1269 	}
1270 
1271 	if (le16_to_cpu(e->size) > sizeof(struct NTFS_DE)) {
1272 		*entry = e;
1273 		return 0;
1274 	}
1275 
1276 pop_level:
1277 	for (;;) {
1278 		if (!de_is_last(e))
1279 			goto next_iter;
1280 
1281 		/* Pop one level. */
1282 		if (n) {
1283 			fnd_pop(fnd);
1284 			kfree(n);
1285 		}
1286 
1287 		level = fnd->level;
1288 
1289 		if (level) {
1290 			n = fnd->nodes[level - 1];
1291 			e = fnd->de[level - 1];
1292 		} else if (fnd->root_de) {
1293 			n = NULL;
1294 			e = fnd->root_de;
1295 			fnd->root_de = NULL;
1296 		} else {
1297 			*entry = NULL;
1298 			return 0;
1299 		}
1300 
1301 		if (le16_to_cpu(e->size) > sizeof(struct NTFS_DE)) {
1302 			*entry = e;
1303 			if (!fnd->root_de)
1304 				fnd->root_de = e;
1305 			return 0;
1306 		}
1307 	}
1308 }
1309 
indx_find_raw(struct ntfs_index * indx,struct ntfs_inode * ni,const struct INDEX_ROOT * root,struct NTFS_DE ** entry,size_t * off,struct ntfs_fnd * fnd)1310 int indx_find_raw(struct ntfs_index *indx, struct ntfs_inode *ni,
1311 		  const struct INDEX_ROOT *root, struct NTFS_DE **entry,
1312 		  size_t *off, struct ntfs_fnd *fnd)
1313 {
1314 	int err;
1315 	struct indx_node *n = NULL;
1316 	struct NTFS_DE *e = NULL;
1317 	struct NTFS_DE *e2;
1318 	size_t bit;
1319 	CLST next_used_vbn;
1320 	CLST next_vbn;
1321 	u32 record_size = ni->mi.sbi->record_size;
1322 
1323 	/* Use non sorted algorithm. */
1324 	if (!*entry) {
1325 		/* This is the first call. */
1326 		e = hdr_first_de(&root->ihdr);
1327 		if (!e)
1328 			return 0;
1329 		fnd_clear(fnd);
1330 		fnd->root_de = e;
1331 
1332 		/* The first call with setup of initial element. */
1333 		if (*off >= record_size) {
1334 			next_vbn = (((*off - record_size) >> indx->index_bits))
1335 				   << indx->idx2vbn_bits;
1336 			/* Jump inside cycle 'for'. */
1337 			goto next;
1338 		}
1339 
1340 		/* Start enumeration from root. */
1341 		*off = 0;
1342 	} else if (!fnd->root_de)
1343 		return -EINVAL;
1344 
1345 	for (;;) {
1346 		/* Check if current entry can be used. */
1347 		if (e && le16_to_cpu(e->size) > sizeof(struct NTFS_DE))
1348 			goto ok;
1349 
1350 		if (!fnd->level) {
1351 			/* Continue to enumerate root. */
1352 			if (!de_is_last(fnd->root_de)) {
1353 				e = hdr_next_de(&root->ihdr, fnd->root_de);
1354 				if (!e)
1355 					return -EINVAL;
1356 				fnd->root_de = e;
1357 				continue;
1358 			}
1359 
1360 			/* Start to enumerate indexes from 0. */
1361 			next_vbn = 0;
1362 		} else {
1363 			/* Continue to enumerate indexes. */
1364 			e2 = fnd->de[fnd->level - 1];
1365 
1366 			n = fnd->nodes[fnd->level - 1];
1367 
1368 			if (!de_is_last(e2)) {
1369 				e = hdr_next_de(&n->index->ihdr, e2);
1370 				if (!e)
1371 					return -EINVAL;
1372 				fnd->de[fnd->level - 1] = e;
1373 				continue;
1374 			}
1375 
1376 			/* Continue with next index. */
1377 			next_vbn = le64_to_cpu(n->index->vbn) +
1378 				   root->index_block_clst;
1379 		}
1380 
1381 next:
1382 		/* Release current index. */
1383 		if (n) {
1384 			fnd_pop(fnd);
1385 			put_indx_node(n);
1386 			n = NULL;
1387 		}
1388 
1389 		/* Skip all free indexes. */
1390 		bit = next_vbn >> indx->idx2vbn_bits;
1391 		err = indx_used_bit(indx, ni, &bit);
1392 		if (err == -ENOENT || bit == MINUS_ONE_T) {
1393 			/* No used indexes. */
1394 			*entry = NULL;
1395 			return 0;
1396 		}
1397 
1398 		next_used_vbn = bit << indx->idx2vbn_bits;
1399 
1400 		/* Read buffer into memory. */
1401 		err = indx_read(indx, ni, next_used_vbn, &n);
1402 		if (err)
1403 			return err;
1404 
1405 		e = hdr_first_de(&n->index->ihdr);
1406 		fnd_push(fnd, n, e);
1407 		if (!e)
1408 			return -EINVAL;
1409 	}
1410 
1411 ok:
1412 	/* Return offset to restore enumerator if necessary. */
1413 	if (!n) {
1414 		/* 'e' points in root, */
1415 		*off = PtrOffset(&root->ihdr, e);
1416 	} else {
1417 		/* 'e' points in index, */
1418 		*off = (le64_to_cpu(n->index->vbn) << indx->vbn2vbo_bits) +
1419 		       record_size + PtrOffset(&n->index->ihdr, e);
1420 	}
1421 
1422 	*entry = e;
1423 	return 0;
1424 }
1425 
1426 /*
1427  * indx_create_allocate - Create "Allocation + Bitmap" attributes.
1428  */
indx_create_allocate(struct ntfs_index * indx,struct ntfs_inode * ni,CLST * vbn)1429 static int indx_create_allocate(struct ntfs_index *indx, struct ntfs_inode *ni,
1430 				CLST *vbn)
1431 {
1432 	int err;
1433 	struct ntfs_sb_info *sbi = ni->mi.sbi;
1434 	struct ATTRIB *bitmap;
1435 	struct ATTRIB *alloc;
1436 	u32 data_size = 1u << indx->index_bits;
1437 	u32 alloc_size = ntfs_up_cluster(sbi, data_size);
1438 	CLST len = alloc_size >> sbi->cluster_bits;
1439 	const struct INDEX_NAMES *in = &s_index_names[indx->type];
1440 	CLST alen;
1441 	struct runs_tree run;
1442 
1443 	run_init(&run);
1444 
1445 	err = attr_allocate_clusters(sbi, &run, 0, 0, len, NULL, ALLOCATE_DEF,
1446 				     &alen, 0, NULL, NULL);
1447 	if (err)
1448 		goto out;
1449 
1450 	err = ni_insert_nonresident(ni, ATTR_ALLOC, in->name, in->name_len,
1451 				    &run, 0, len, 0, &alloc, NULL, NULL);
1452 	if (err)
1453 		goto out1;
1454 
1455 	alloc->nres.valid_size = alloc->nres.data_size = cpu_to_le64(data_size);
1456 
1457 	err = ni_insert_resident(ni, ntfs3_bitmap_size(1), ATTR_BITMAP,
1458 				 in->name, in->name_len, &bitmap, NULL, NULL);
1459 	if (err)
1460 		goto out2;
1461 
1462 	if (in->name == I30_NAME) {
1463 		i_size_write(&ni->vfs_inode, data_size);
1464 		inode_set_bytes(&ni->vfs_inode, alloc_size);
1465 	}
1466 
1467 	memcpy(&indx->alloc_run, &run, sizeof(run));
1468 
1469 	*vbn = 0;
1470 
1471 	return 0;
1472 
1473 out2:
1474 	mi_remove_attr(NULL, &ni->mi, alloc);
1475 
1476 out1:
1477 	run_deallocate(sbi, &run, false);
1478 
1479 out:
1480 	return err;
1481 }
1482 
1483 /*
1484  * indx_add_allocate - Add clusters to index.
1485  */
indx_add_allocate(struct ntfs_index * indx,struct ntfs_inode * ni,CLST * vbn)1486 static int indx_add_allocate(struct ntfs_index *indx, struct ntfs_inode *ni,
1487 			     CLST *vbn)
1488 {
1489 	int err;
1490 	size_t bit;
1491 	u64 data_size;
1492 	u64 bmp_size, bmp_size_v;
1493 	struct ATTRIB *bmp, *alloc;
1494 	struct mft_inode *mi;
1495 	const struct INDEX_NAMES *in = &s_index_names[indx->type];
1496 
1497 	err = indx_find_free(indx, ni, &bit, &bmp);
1498 	if (err)
1499 		goto out1;
1500 
1501 	if (bit != MINUS_ONE_T) {
1502 		bmp = NULL;
1503 	} else {
1504 		if (bmp->non_res) {
1505 			bmp_size = le64_to_cpu(bmp->nres.data_size);
1506 			bmp_size_v = le64_to_cpu(bmp->nres.valid_size);
1507 		} else {
1508 			bmp_size = bmp_size_v = le32_to_cpu(bmp->res.data_size);
1509 		}
1510 
1511 		bit = bmp_size << 3;
1512 	}
1513 
1514 	data_size = (u64)(bit + 1) << indx->index_bits;
1515 
1516 	if (bmp) {
1517 		/* Increase bitmap. */
1518 		err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
1519 				    &indx->bitmap_run,
1520 				    ntfs3_bitmap_size(bit + 1), NULL, true,
1521 				    NULL);
1522 		if (err)
1523 			goto out1;
1524 	}
1525 
1526 	alloc = ni_find_attr(ni, NULL, NULL, ATTR_ALLOC, in->name, in->name_len,
1527 			     NULL, &mi);
1528 	if (!alloc) {
1529 		err = -EINVAL;
1530 		if (bmp)
1531 			goto out2;
1532 		goto out1;
1533 	}
1534 
1535 	if (data_size <= le64_to_cpu(alloc->nres.data_size)) {
1536 		/* Reuse index. */
1537 		goto out;
1538 	}
1539 
1540 	/* Increase allocation. */
1541 	err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
1542 			    &indx->alloc_run, data_size, &data_size, true,
1543 			    NULL);
1544 	if (err) {
1545 		if (bmp)
1546 			goto out2;
1547 		goto out1;
1548 	}
1549 
1550 	if (in->name == I30_NAME)
1551 		i_size_write(&ni->vfs_inode, data_size);
1552 
1553 out:
1554 	*vbn = bit << indx->idx2vbn_bits;
1555 
1556 	return 0;
1557 
1558 out2:
1559 	/* Ops. No space? */
1560 	attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
1561 		      &indx->bitmap_run, bmp_size, &bmp_size_v, false, NULL);
1562 
1563 out1:
1564 	return err;
1565 }
1566 
1567 /*
1568  * indx_insert_into_root - Attempt to insert an entry into the index root.
1569  *
1570  * @undo - True if we undoing previous remove.
1571  * If necessary, it will twiddle the index b-tree.
1572  */
indx_insert_into_root(struct ntfs_index * indx,struct ntfs_inode * ni,const struct NTFS_DE * new_de,struct NTFS_DE * root_de,const void * ctx,struct ntfs_fnd * fnd,bool undo)1573 static int indx_insert_into_root(struct ntfs_index *indx, struct ntfs_inode *ni,
1574 				 const struct NTFS_DE *new_de,
1575 				 struct NTFS_DE *root_de, const void *ctx,
1576 				 struct ntfs_fnd *fnd, bool undo)
1577 {
1578 	int err = 0;
1579 	struct NTFS_DE *e, *e0, *re;
1580 	struct mft_inode *mi;
1581 	struct ATTRIB *attr;
1582 	struct INDEX_HDR *hdr;
1583 	struct indx_node *n;
1584 	CLST new_vbn;
1585 	__le64 *sub_vbn, t_vbn;
1586 	u16 new_de_size;
1587 	u32 hdr_used, hdr_total, asize, to_move;
1588 	u32 root_size, new_root_size;
1589 	struct ntfs_sb_info *sbi;
1590 	int ds_root;
1591 	struct INDEX_ROOT *root, *a_root;
1592 
1593 	/* Get the record this root placed in. */
1594 	root = indx_get_root(indx, ni, &attr, &mi);
1595 	if (!root)
1596 		return -EINVAL;
1597 
1598 	/*
1599 	 * Try easy case:
1600 	 * hdr_insert_de will succeed if there's
1601 	 * room the root for the new entry.
1602 	 */
1603 	hdr = &root->ihdr;
1604 	sbi = ni->mi.sbi;
1605 	new_de_size = le16_to_cpu(new_de->size);
1606 	hdr_used = le32_to_cpu(hdr->used);
1607 	hdr_total = le32_to_cpu(hdr->total);
1608 	asize = le32_to_cpu(attr->size);
1609 	root_size = le32_to_cpu(attr->res.data_size);
1610 
1611 	ds_root = new_de_size + hdr_used - hdr_total;
1612 
1613 	/* If 'undo' is set then reduce requirements. */
1614 	if ((undo || asize + ds_root < sbi->max_bytes_per_attr) &&
1615 	    mi_resize_attr(mi, attr, ds_root)) {
1616 		hdr->total = cpu_to_le32(hdr_total + ds_root);
1617 		e = hdr_insert_de(indx, hdr, new_de, root_de, ctx);
1618 		WARN_ON(!e);
1619 		fnd_clear(fnd);
1620 		fnd->root_de = e;
1621 
1622 		return 0;
1623 	}
1624 
1625 	/* Make a copy of root attribute to restore if error. */
1626 	a_root = kmemdup(attr, asize, GFP_NOFS);
1627 	if (!a_root)
1628 		return -ENOMEM;
1629 
1630 	/*
1631 	 * Copy all the non-end entries from
1632 	 * the index root to the new buffer.
1633 	 */
1634 	to_move = 0;
1635 	e0 = hdr_first_de(hdr);
1636 
1637 	/* Calculate the size to copy. */
1638 	for (e = e0;; e = hdr_next_de(hdr, e)) {
1639 		if (!e) {
1640 			err = -EINVAL;
1641 			goto out_free_root;
1642 		}
1643 
1644 		if (de_is_last(e))
1645 			break;
1646 		to_move += le16_to_cpu(e->size);
1647 	}
1648 
1649 	if (!to_move) {
1650 		re = NULL;
1651 	} else {
1652 		re = kmemdup(e0, to_move, GFP_NOFS);
1653 		if (!re) {
1654 			err = -ENOMEM;
1655 			goto out_free_root;
1656 		}
1657 	}
1658 
1659 	sub_vbn = NULL;
1660 	if (de_has_vcn(e)) {
1661 		t_vbn = de_get_vbn_le(e);
1662 		sub_vbn = &t_vbn;
1663 	}
1664 
1665 	new_root_size = sizeof(struct INDEX_ROOT) + sizeof(struct NTFS_DE) +
1666 			sizeof(u64);
1667 	ds_root = new_root_size - root_size;
1668 
1669 	if (ds_root > 0 && asize + ds_root > sbi->max_bytes_per_attr) {
1670 		/* Make root external. */
1671 		err = -EOPNOTSUPP;
1672 		goto out_free_re;
1673 	}
1674 
1675 	if (ds_root)
1676 		mi_resize_attr(mi, attr, ds_root);
1677 
1678 	/* Fill first entry (vcn will be set later). */
1679 	e = (struct NTFS_DE *)(root + 1);
1680 	memset(e, 0, sizeof(struct NTFS_DE));
1681 	e->size = cpu_to_le16(sizeof(struct NTFS_DE) + sizeof(u64));
1682 	e->flags = NTFS_IE_HAS_SUBNODES | NTFS_IE_LAST;
1683 
1684 	hdr->flags = NTFS_INDEX_HDR_HAS_SUBNODES;
1685 	hdr->used = hdr->total =
1686 		cpu_to_le32(new_root_size - offsetof(struct INDEX_ROOT, ihdr));
1687 
1688 	fnd->root_de = hdr_first_de(hdr);
1689 	mi->dirty = true;
1690 
1691 	/* Create alloc and bitmap attributes (if not). */
1692 	err = run_is_empty(&indx->alloc_run) ?
1693 		      indx_create_allocate(indx, ni, &new_vbn) :
1694 		      indx_add_allocate(indx, ni, &new_vbn);
1695 
1696 	/* Layout of record may be changed, so rescan root. */
1697 	root = indx_get_root(indx, ni, &attr, &mi);
1698 	if (!root) {
1699 		/* Bug? */
1700 		ntfs_set_state(sbi, NTFS_DIRTY_ERROR);
1701 		err = -EINVAL;
1702 		goto out_free_re;
1703 	}
1704 
1705 	if (err) {
1706 		/* Restore root. */
1707 		if (mi_resize_attr(mi, attr, -ds_root)) {
1708 			memcpy(attr, a_root, asize);
1709 		} else {
1710 			/* Bug? */
1711 			ntfs_set_state(sbi, NTFS_DIRTY_ERROR);
1712 		}
1713 		goto out_free_re;
1714 	}
1715 
1716 	e = (struct NTFS_DE *)(root + 1);
1717 	*(__le64 *)(e + 1) = cpu_to_le64(new_vbn);
1718 	mi->dirty = true;
1719 
1720 	/* Now we can create/format the new buffer and copy the entries into. */
1721 	n = indx_new(indx, ni, new_vbn, sub_vbn);
1722 	if (IS_ERR(n)) {
1723 		err = PTR_ERR(n);
1724 		goto out_free_re;
1725 	}
1726 
1727 	hdr = &n->index->ihdr;
1728 	hdr_used = le32_to_cpu(hdr->used);
1729 	hdr_total = le32_to_cpu(hdr->total);
1730 
1731 	/* Copy root entries into new buffer. */
1732 	hdr_insert_head(hdr, re, to_move);
1733 
1734 	/* Update bitmap attribute. */
1735 	indx_mark_used(indx, ni, new_vbn >> indx->idx2vbn_bits);
1736 
1737 	/* Check if we can insert new entry new index buffer. */
1738 	if (hdr_used + new_de_size > hdr_total) {
1739 		/*
1740 		 * This occurs if MFT record is the same or bigger than index
1741 		 * buffer. Move all root new index and have no space to add
1742 		 * new entry classic case when MFT record is 1K and index
1743 		 * buffer 4K the problem should not occurs.
1744 		 */
1745 		kfree(re);
1746 		indx_write(indx, ni, n, 0);
1747 
1748 		put_indx_node(n);
1749 		fnd_clear(fnd);
1750 		err = indx_insert_entry(indx, ni, new_de, ctx, fnd, undo);
1751 		goto out_free_root;
1752 	}
1753 
1754 	/*
1755 	 * Now root is a parent for new index buffer.
1756 	 * Insert NewEntry a new buffer.
1757 	 */
1758 	e = hdr_insert_de(indx, hdr, new_de, NULL, ctx);
1759 	if (!e) {
1760 		err = -EINVAL;
1761 		goto out_put_n;
1762 	}
1763 	fnd_push(fnd, n, e);
1764 
1765 	/* Just write updates index into disk. */
1766 	indx_write(indx, ni, n, 0);
1767 
1768 	n = NULL;
1769 
1770 out_put_n:
1771 	put_indx_node(n);
1772 out_free_re:
1773 	kfree(re);
1774 out_free_root:
1775 	kfree(a_root);
1776 	return err;
1777 }
1778 
1779 /*
1780  * indx_insert_into_buffer
1781  *
1782  * Attempt to insert an entry into an Index Allocation Buffer.
1783  * If necessary, it will split the buffer.
1784  */
1785 static int
indx_insert_into_buffer(struct ntfs_index * indx,struct ntfs_inode * ni,struct INDEX_ROOT * root,const struct NTFS_DE * new_de,const void * ctx,int level,struct ntfs_fnd * fnd)1786 indx_insert_into_buffer(struct ntfs_index *indx, struct ntfs_inode *ni,
1787 			struct INDEX_ROOT *root, const struct NTFS_DE *new_de,
1788 			const void *ctx, int level, struct ntfs_fnd *fnd)
1789 {
1790 	int err;
1791 	const struct NTFS_DE *sp;
1792 	struct NTFS_DE *e, *de_t, *up_e;
1793 	struct indx_node *n2;
1794 	struct indx_node *n1 = fnd->nodes[level];
1795 	struct INDEX_HDR *hdr1 = &n1->index->ihdr;
1796 	struct INDEX_HDR *hdr2;
1797 	u32 to_copy, used, used1;
1798 	CLST new_vbn;
1799 	__le64 t_vbn, *sub_vbn;
1800 	u16 sp_size;
1801 	void *hdr1_saved = NULL;
1802 
1803 	/* Try the most easy case. */
1804 	e = fnd->level - 1 == level ? fnd->de[level] : NULL;
1805 	e = hdr_insert_de(indx, hdr1, new_de, e, ctx);
1806 	fnd->de[level] = e;
1807 	if (e) {
1808 		/* Just write updated index into disk. */
1809 		indx_write(indx, ni, n1, 0);
1810 		return 0;
1811 	}
1812 
1813 	/*
1814 	 * No space to insert into buffer. Split it.
1815 	 * To split we:
1816 	 *  - Save split point ('cause index buffers will be changed)
1817 	 * - Allocate NewBuffer and copy all entries <= sp into new buffer
1818 	 * - Remove all entries (sp including) from TargetBuffer
1819 	 * - Insert NewEntry into left or right buffer (depending on sp <=>
1820 	 *     NewEntry)
1821 	 * - Insert sp into parent buffer (or root)
1822 	 * - Make sp a parent for new buffer
1823 	 */
1824 	sp = hdr_find_split(hdr1);
1825 	if (!sp)
1826 		return -EINVAL;
1827 
1828 	sp_size = le16_to_cpu(sp->size);
1829 	up_e = kmalloc(sp_size + sizeof(u64), GFP_NOFS);
1830 	if (!up_e)
1831 		return -ENOMEM;
1832 	memcpy(up_e, sp, sp_size);
1833 
1834 	used1 = le32_to_cpu(hdr1->used);
1835 	hdr1_saved = kmemdup(hdr1, used1, GFP_NOFS);
1836 	if (!hdr1_saved) {
1837 		err = -ENOMEM;
1838 		goto out;
1839 	}
1840 
1841 	if (!hdr1->flags) {
1842 		up_e->flags |= NTFS_IE_HAS_SUBNODES;
1843 		up_e->size = cpu_to_le16(sp_size + sizeof(u64));
1844 		sub_vbn = NULL;
1845 	} else {
1846 		t_vbn = de_get_vbn_le(up_e);
1847 		sub_vbn = &t_vbn;
1848 	}
1849 
1850 	/* Allocate on disk a new index allocation buffer. */
1851 	err = indx_add_allocate(indx, ni, &new_vbn);
1852 	if (err)
1853 		goto out;
1854 
1855 	/* Allocate and format memory a new index buffer. */
1856 	n2 = indx_new(indx, ni, new_vbn, sub_vbn);
1857 	if (IS_ERR(n2)) {
1858 		err = PTR_ERR(n2);
1859 		goto out;
1860 	}
1861 
1862 	hdr2 = &n2->index->ihdr;
1863 
1864 	/* Make sp a parent for new buffer. */
1865 	de_set_vbn(up_e, new_vbn);
1866 
1867 	/* Copy all the entries <= sp into the new buffer. */
1868 	de_t = hdr_first_de(hdr1);
1869 	to_copy = PtrOffset(de_t, sp);
1870 	hdr_insert_head(hdr2, de_t, to_copy);
1871 
1872 	/* Remove all entries (sp including) from hdr1. */
1873 	used = used1 - to_copy - sp_size;
1874 	memmove(de_t, Add2Ptr(sp, sp_size), used - le32_to_cpu(hdr1->de_off));
1875 	hdr1->used = cpu_to_le32(used);
1876 
1877 	/*
1878 	 * Insert new entry into left or right buffer
1879 	 * (depending on sp <=> new_de).
1880 	 */
1881 	hdr_insert_de(indx,
1882 		      (*indx->cmp)(new_de + 1, le16_to_cpu(new_de->key_size),
1883 				   up_e + 1, le16_to_cpu(up_e->key_size),
1884 				   ctx) < 0 ?
1885 			      hdr2 :
1886 			      hdr1,
1887 		      new_de, NULL, ctx);
1888 
1889 	indx_mark_used(indx, ni, new_vbn >> indx->idx2vbn_bits);
1890 
1891 	indx_write(indx, ni, n1, 0);
1892 	indx_write(indx, ni, n2, 0);
1893 
1894 	put_indx_node(n2);
1895 
1896 	/*
1897 	 * We've finished splitting everybody, so we are ready to
1898 	 * insert the promoted entry into the parent.
1899 	 */
1900 	if (!level) {
1901 		/* Insert in root. */
1902 		err = indx_insert_into_root(indx, ni, up_e, NULL, ctx, fnd, 0);
1903 	} else {
1904 		/*
1905 		 * The target buffer's parent is another index buffer.
1906 		 * TODO: Remove recursion.
1907 		 */
1908 		err = indx_insert_into_buffer(indx, ni, root, up_e, ctx,
1909 					      level - 1, fnd);
1910 	}
1911 
1912 	if (err) {
1913 		/*
1914 		 * Undo critical operations.
1915 		 */
1916 		indx_mark_free(indx, ni, new_vbn >> indx->idx2vbn_bits);
1917 		memcpy(hdr1, hdr1_saved, used1);
1918 		indx_write(indx, ni, n1, 0);
1919 	}
1920 
1921 out:
1922 	kfree(up_e);
1923 	kfree(hdr1_saved);
1924 
1925 	return err;
1926 }
1927 
1928 /*
1929  * indx_insert_entry - Insert new entry into index.
1930  *
1931  * @undo - True if we undoing previous remove.
1932  */
indx_insert_entry(struct ntfs_index * indx,struct ntfs_inode * ni,const struct NTFS_DE * new_de,const void * ctx,struct ntfs_fnd * fnd,bool undo)1933 int indx_insert_entry(struct ntfs_index *indx, struct ntfs_inode *ni,
1934 		      const struct NTFS_DE *new_de, const void *ctx,
1935 		      struct ntfs_fnd *fnd, bool undo)
1936 {
1937 	int err;
1938 	int diff;
1939 	struct NTFS_DE *e;
1940 	struct ntfs_fnd *fnd_a = NULL;
1941 	struct INDEX_ROOT *root;
1942 
1943 	if (!fnd) {
1944 		fnd_a = fnd_get();
1945 		if (!fnd_a) {
1946 			err = -ENOMEM;
1947 			goto out1;
1948 		}
1949 		fnd = fnd_a;
1950 	}
1951 
1952 	root = indx_get_root(indx, ni, NULL, NULL);
1953 	if (!root) {
1954 		err = -EINVAL;
1955 		goto out;
1956 	}
1957 
1958 	if (fnd_is_empty(fnd)) {
1959 		/*
1960 		 * Find the spot the tree where we want to
1961 		 * insert the new entry.
1962 		 */
1963 		err = indx_find(indx, ni, root, new_de + 1,
1964 				le16_to_cpu(new_de->key_size), ctx, &diff, &e,
1965 				fnd);
1966 		if (err)
1967 			goto out;
1968 
1969 		if (!diff) {
1970 			err = -EEXIST;
1971 			goto out;
1972 		}
1973 	}
1974 
1975 	if (!fnd->level) {
1976 		/*
1977 		 * The root is also a leaf, so we'll insert the
1978 		 * new entry into it.
1979 		 */
1980 		err = indx_insert_into_root(indx, ni, new_de, fnd->root_de, ctx,
1981 					    fnd, undo);
1982 	} else {
1983 		/*
1984 		 * Found a leaf buffer, so we'll insert the new entry into it.
1985 		 */
1986 		err = indx_insert_into_buffer(indx, ni, root, new_de, ctx,
1987 					      fnd->level - 1, fnd);
1988 	}
1989 
1990 out:
1991 	fnd_put(fnd_a);
1992 out1:
1993 	return err;
1994 }
1995 
1996 /*
1997  * indx_find_buffer - Locate a buffer from the tree.
1998  */
indx_find_buffer(struct ntfs_index * indx,struct ntfs_inode * ni,const struct INDEX_ROOT * root,__le64 vbn,struct indx_node * n)1999 static struct indx_node *indx_find_buffer(struct ntfs_index *indx,
2000 					  struct ntfs_inode *ni,
2001 					  const struct INDEX_ROOT *root,
2002 					  __le64 vbn, struct indx_node *n)
2003 {
2004 	int err;
2005 	const struct NTFS_DE *e;
2006 	struct indx_node *r;
2007 	const struct INDEX_HDR *hdr = n ? &n->index->ihdr : &root->ihdr;
2008 
2009 	/* Step 1: Scan one level. */
2010 	for (e = hdr_first_de(hdr);; e = hdr_next_de(hdr, e)) {
2011 		if (!e)
2012 			return ERR_PTR(-EINVAL);
2013 
2014 		if (de_has_vcn(e) && vbn == de_get_vbn_le(e))
2015 			return n;
2016 
2017 		if (de_is_last(e))
2018 			break;
2019 	}
2020 
2021 	/* Step2: Do recursion. */
2022 	e = Add2Ptr(hdr, le32_to_cpu(hdr->de_off));
2023 	for (;;) {
2024 		if (de_has_vcn_ex(e)) {
2025 			err = indx_read(indx, ni, de_get_vbn(e), &n);
2026 			if (err)
2027 				return ERR_PTR(err);
2028 
2029 			r = indx_find_buffer(indx, ni, root, vbn, n);
2030 			if (r)
2031 				return r;
2032 		}
2033 
2034 		if (de_is_last(e))
2035 			break;
2036 
2037 		e = Add2Ptr(e, le16_to_cpu(e->size));
2038 	}
2039 
2040 	return NULL;
2041 }
2042 
2043 /*
2044  * indx_shrink - Deallocate unused tail indexes.
2045  */
indx_shrink(struct ntfs_index * indx,struct ntfs_inode * ni,size_t bit)2046 static int indx_shrink(struct ntfs_index *indx, struct ntfs_inode *ni,
2047 		       size_t bit)
2048 {
2049 	int err = 0;
2050 	u64 bpb, new_data;
2051 	size_t nbits;
2052 	struct ATTRIB *b;
2053 	struct ATTR_LIST_ENTRY *le = NULL;
2054 	const struct INDEX_NAMES *in = &s_index_names[indx->type];
2055 
2056 	b = ni_find_attr(ni, NULL, &le, ATTR_BITMAP, in->name, in->name_len,
2057 			 NULL, NULL);
2058 
2059 	if (!b)
2060 		return -ENOENT;
2061 
2062 	if (!b->non_res) {
2063 		unsigned long pos;
2064 		const unsigned long *bm = resident_data(b);
2065 
2066 		nbits = (size_t)le32_to_cpu(b->res.data_size) * 8;
2067 
2068 		if (bit >= nbits)
2069 			return 0;
2070 
2071 		pos = find_next_bit_le(bm, nbits, bit);
2072 		if (pos < nbits)
2073 			return 0;
2074 	} else {
2075 		size_t used = MINUS_ONE_T;
2076 
2077 		nbits = le64_to_cpu(b->nres.data_size) * 8;
2078 
2079 		if (bit >= nbits)
2080 			return 0;
2081 
2082 		err = scan_nres_bitmap(ni, b, indx, bit, &scan_for_used, &used);
2083 		if (err)
2084 			return err;
2085 
2086 		if (used != MINUS_ONE_T)
2087 			return 0;
2088 	}
2089 
2090 	new_data = (u64)bit << indx->index_bits;
2091 
2092 	err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
2093 			    &indx->alloc_run, new_data, &new_data, false, NULL);
2094 	if (err)
2095 		return err;
2096 
2097 	if (in->name == I30_NAME)
2098 		i_size_write(&ni->vfs_inode, new_data);
2099 
2100 	bpb = ntfs3_bitmap_size(bit);
2101 	if (bpb * 8 == nbits)
2102 		return 0;
2103 
2104 	err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
2105 			    &indx->bitmap_run, bpb, &bpb, false, NULL);
2106 
2107 	return err;
2108 }
2109 
indx_free_children(struct ntfs_index * indx,struct ntfs_inode * ni,const struct NTFS_DE * e,bool trim)2110 static int indx_free_children(struct ntfs_index *indx, struct ntfs_inode *ni,
2111 			      const struct NTFS_DE *e, bool trim)
2112 {
2113 	int err;
2114 	struct indx_node *n = NULL;
2115 	struct INDEX_HDR *hdr;
2116 	CLST vbn = de_get_vbn(e);
2117 	size_t i;
2118 
2119 	err = indx_read(indx, ni, vbn, &n);
2120 	if (err)
2121 		return err;
2122 
2123 	hdr = &n->index->ihdr;
2124 	/* First, recurse into the children, if any. */
2125 	if (hdr_has_subnode(hdr)) {
2126 		for (e = hdr_first_de(hdr); e; e = hdr_next_de(hdr, e)) {
2127 			indx_free_children(indx, ni, e, false);
2128 			if (de_is_last(e))
2129 				break;
2130 		}
2131 	}
2132 
2133 	put_indx_node(n);
2134 
2135 	i = vbn >> indx->idx2vbn_bits;
2136 	/*
2137 	 * We've gotten rid of the children; add this buffer to the free list.
2138 	 */
2139 	indx_mark_free(indx, ni, i);
2140 
2141 	if (!trim)
2142 		return 0;
2143 
2144 	/*
2145 	 * If there are no used indexes after current free index
2146 	 * then we can truncate allocation and bitmap.
2147 	 * Use bitmap to estimate the case.
2148 	 */
2149 	indx_shrink(indx, ni, i + 1);
2150 	return 0;
2151 }
2152 
2153 /*
2154  * indx_get_entry_to_replace
2155  *
2156  * Find a replacement entry for a deleted entry.
2157  * Always returns a node entry:
2158  * NTFS_IE_HAS_SUBNODES is set the flags and the size includes the sub_vcn.
2159  */
indx_get_entry_to_replace(struct ntfs_index * indx,struct ntfs_inode * ni,const struct NTFS_DE * de_next,struct NTFS_DE ** de_to_replace,struct ntfs_fnd * fnd)2160 static int indx_get_entry_to_replace(struct ntfs_index *indx,
2161 				     struct ntfs_inode *ni,
2162 				     const struct NTFS_DE *de_next,
2163 				     struct NTFS_DE **de_to_replace,
2164 				     struct ntfs_fnd *fnd)
2165 {
2166 	int err;
2167 	int level = -1;
2168 	CLST vbn;
2169 	struct NTFS_DE *e, *te, *re;
2170 	struct indx_node *n;
2171 	struct INDEX_BUFFER *ib;
2172 
2173 	*de_to_replace = NULL;
2174 
2175 	/* Find first leaf entry down from de_next. */
2176 	vbn = de_get_vbn(de_next);
2177 	for (;;) {
2178 		n = NULL;
2179 		err = indx_read(indx, ni, vbn, &n);
2180 		if (err)
2181 			goto out;
2182 
2183 		e = hdr_first_de(&n->index->ihdr);
2184 		fnd_push(fnd, n, e);
2185 
2186 		if (!de_is_last(e)) {
2187 			/*
2188 			 * This buffer is non-empty, so its first entry
2189 			 * could be used as the replacement entry.
2190 			 */
2191 			level = fnd->level - 1;
2192 		}
2193 
2194 		if (!de_has_vcn(e))
2195 			break;
2196 
2197 		/* This buffer is a node. Continue to go down. */
2198 		vbn = de_get_vbn(e);
2199 	}
2200 
2201 	if (level == -1)
2202 		goto out;
2203 
2204 	n = fnd->nodes[level];
2205 	te = hdr_first_de(&n->index->ihdr);
2206 	/* Copy the candidate entry into the replacement entry buffer. */
2207 	re = kmalloc(le16_to_cpu(te->size) + sizeof(u64), GFP_NOFS);
2208 	if (!re) {
2209 		err = -ENOMEM;
2210 		goto out;
2211 	}
2212 
2213 	*de_to_replace = re;
2214 	memcpy(re, te, le16_to_cpu(te->size));
2215 
2216 	if (!de_has_vcn(re)) {
2217 		/*
2218 		 * The replacement entry we found doesn't have a sub_vcn.
2219 		 * increase its size to hold one.
2220 		 */
2221 		le16_add_cpu(&re->size, sizeof(u64));
2222 		re->flags |= NTFS_IE_HAS_SUBNODES;
2223 	} else {
2224 		/*
2225 		 * The replacement entry we found was a node entry, which
2226 		 * means that all its child buffers are empty. Return them
2227 		 * to the free pool.
2228 		 */
2229 		indx_free_children(indx, ni, te, true);
2230 	}
2231 
2232 	/*
2233 	 * Expunge the replacement entry from its former location,
2234 	 * and then write that buffer.
2235 	 */
2236 	ib = n->index;
2237 	e = hdr_delete_de(&ib->ihdr, te);
2238 
2239 	fnd->de[level] = e;
2240 	indx_write(indx, ni, n, 0);
2241 
2242 	if (ib_is_leaf(ib) && ib_is_empty(ib)) {
2243 		/* An empty leaf. */
2244 		return 0;
2245 	}
2246 
2247 out:
2248 	fnd_clear(fnd);
2249 	return err;
2250 }
2251 
2252 /*
2253  * indx_delete_entry - Delete an entry from the index.
2254  */
indx_delete_entry(struct ntfs_index * indx,struct ntfs_inode * ni,const void * key,u32 key_len,const void * ctx)2255 int indx_delete_entry(struct ntfs_index *indx, struct ntfs_inode *ni,
2256 		      const void *key, u32 key_len, const void *ctx)
2257 {
2258 	int err, diff;
2259 	struct INDEX_ROOT *root;
2260 	struct INDEX_HDR *hdr;
2261 	struct ntfs_fnd *fnd, *fnd2;
2262 	struct INDEX_BUFFER *ib;
2263 	struct NTFS_DE *e, *re, *next, *prev, *me;
2264 	struct indx_node *n, *n2d = NULL;
2265 	__le64 sub_vbn;
2266 	int level, level2;
2267 	struct ATTRIB *attr;
2268 	struct mft_inode *mi;
2269 	u32 e_size, root_size, new_root_size;
2270 	size_t trim_bit;
2271 	const struct INDEX_NAMES *in;
2272 
2273 	fnd = fnd_get();
2274 	if (!fnd) {
2275 		err = -ENOMEM;
2276 		goto out2;
2277 	}
2278 
2279 	fnd2 = fnd_get();
2280 	if (!fnd2) {
2281 		err = -ENOMEM;
2282 		goto out1;
2283 	}
2284 
2285 	root = indx_get_root(indx, ni, &attr, &mi);
2286 	if (!root) {
2287 		err = -EINVAL;
2288 		goto out;
2289 	}
2290 
2291 	/* Locate the entry to remove. */
2292 	err = indx_find(indx, ni, root, key, key_len, ctx, &diff, &e, fnd);
2293 	if (err)
2294 		goto out;
2295 
2296 	if (!e || diff) {
2297 		err = -ENOENT;
2298 		goto out;
2299 	}
2300 
2301 	level = fnd->level;
2302 
2303 	if (level) {
2304 		n = fnd->nodes[level - 1];
2305 		e = fnd->de[level - 1];
2306 		ib = n->index;
2307 		hdr = &ib->ihdr;
2308 	} else {
2309 		hdr = &root->ihdr;
2310 		e = fnd->root_de;
2311 		n = NULL;
2312 	}
2313 
2314 	e_size = le16_to_cpu(e->size);
2315 
2316 	if (!de_has_vcn_ex(e)) {
2317 		/* The entry to delete is a leaf, so we can just rip it out. */
2318 		hdr_delete_de(hdr, e);
2319 
2320 		if (!level) {
2321 			hdr->total = hdr->used;
2322 
2323 			/* Shrink resident root attribute. */
2324 			mi_resize_attr(mi, attr, 0 - e_size);
2325 			goto out;
2326 		}
2327 
2328 		indx_write(indx, ni, n, 0);
2329 
2330 		/*
2331 		 * Check to see if removing that entry made
2332 		 * the leaf empty.
2333 		 */
2334 		if (ib_is_leaf(ib) && ib_is_empty(ib)) {
2335 			fnd_pop(fnd);
2336 			fnd_push(fnd2, n, e);
2337 		}
2338 	} else {
2339 		/*
2340 		 * The entry we wish to delete is a node buffer, so we
2341 		 * have to find a replacement for it.
2342 		 */
2343 		next = de_get_next(e);
2344 
2345 		err = indx_get_entry_to_replace(indx, ni, next, &re, fnd2);
2346 		if (err)
2347 			goto out;
2348 
2349 		if (re) {
2350 			de_set_vbn_le(re, de_get_vbn_le(e));
2351 			hdr_delete_de(hdr, e);
2352 
2353 			err = level ? indx_insert_into_buffer(indx, ni, root,
2354 							      re, ctx,
2355 							      fnd->level - 1,
2356 							      fnd) :
2357 				      indx_insert_into_root(indx, ni, re, e,
2358 							    ctx, fnd, 0);
2359 			kfree(re);
2360 
2361 			if (err)
2362 				goto out;
2363 		} else {
2364 			/*
2365 			 * There is no replacement for the current entry.
2366 			 * This means that the subtree rooted at its node
2367 			 * is empty, and can be deleted, which turn means
2368 			 * that the node can just inherit the deleted
2369 			 * entry sub_vcn.
2370 			 */
2371 			indx_free_children(indx, ni, next, true);
2372 
2373 			de_set_vbn_le(next, de_get_vbn_le(e));
2374 			hdr_delete_de(hdr, e);
2375 			if (level) {
2376 				indx_write(indx, ni, n, 0);
2377 			} else {
2378 				hdr->total = hdr->used;
2379 
2380 				/* Shrink resident root attribute. */
2381 				mi_resize_attr(mi, attr, 0 - e_size);
2382 			}
2383 		}
2384 	}
2385 
2386 	/* Delete a branch of tree. */
2387 	if (!fnd2 || !fnd2->level)
2388 		goto out;
2389 
2390 	/* Reinit root 'cause it can be changed. */
2391 	root = indx_get_root(indx, ni, &attr, &mi);
2392 	if (!root) {
2393 		err = -EINVAL;
2394 		goto out;
2395 	}
2396 
2397 	n2d = NULL;
2398 	sub_vbn = fnd2->nodes[0]->index->vbn;
2399 	level2 = 0;
2400 	level = fnd->level;
2401 
2402 	hdr = level ? &fnd->nodes[level - 1]->index->ihdr : &root->ihdr;
2403 
2404 	/* Scan current level. */
2405 	for (e = hdr_first_de(hdr);; e = hdr_next_de(hdr, e)) {
2406 		if (!e) {
2407 			err = -EINVAL;
2408 			goto out;
2409 		}
2410 
2411 		if (de_has_vcn(e) && sub_vbn == de_get_vbn_le(e))
2412 			break;
2413 
2414 		if (de_is_last(e)) {
2415 			e = NULL;
2416 			break;
2417 		}
2418 	}
2419 
2420 	if (!e) {
2421 		/* Do slow search from root. */
2422 		struct indx_node *in;
2423 
2424 		fnd_clear(fnd);
2425 
2426 		in = indx_find_buffer(indx, ni, root, sub_vbn, NULL);
2427 		if (IS_ERR(in)) {
2428 			err = PTR_ERR(in);
2429 			goto out;
2430 		}
2431 
2432 		if (in)
2433 			fnd_push(fnd, in, NULL);
2434 	}
2435 
2436 	/* Merge fnd2 -> fnd. */
2437 	for (level = 0; level < fnd2->level; level++) {
2438 		fnd_push(fnd, fnd2->nodes[level], fnd2->de[level]);
2439 		fnd2->nodes[level] = NULL;
2440 	}
2441 	fnd2->level = 0;
2442 
2443 	hdr = NULL;
2444 	for (level = fnd->level; level; level--) {
2445 		struct indx_node *in = fnd->nodes[level - 1];
2446 
2447 		ib = in->index;
2448 		if (ib_is_empty(ib)) {
2449 			sub_vbn = ib->vbn;
2450 		} else {
2451 			hdr = &ib->ihdr;
2452 			n2d = in;
2453 			level2 = level;
2454 			break;
2455 		}
2456 	}
2457 
2458 	if (!hdr)
2459 		hdr = &root->ihdr;
2460 
2461 	e = hdr_first_de(hdr);
2462 	if (!e) {
2463 		err = -EINVAL;
2464 		goto out;
2465 	}
2466 
2467 	if (hdr != &root->ihdr || !de_is_last(e)) {
2468 		prev = NULL;
2469 		while (!de_is_last(e)) {
2470 			if (de_has_vcn(e) && sub_vbn == de_get_vbn_le(e))
2471 				break;
2472 			prev = e;
2473 			e = hdr_next_de(hdr, e);
2474 			if (!e) {
2475 				err = -EINVAL;
2476 				goto out;
2477 			}
2478 		}
2479 
2480 		if (sub_vbn != de_get_vbn_le(e)) {
2481 			/*
2482 			 * Didn't find the parent entry, although this buffer
2483 			 * is the parent trail. Something is corrupt.
2484 			 */
2485 			err = -EINVAL;
2486 			goto out;
2487 		}
2488 
2489 		if (de_is_last(e)) {
2490 			/*
2491 			 * Since we can't remove the end entry, we'll remove
2492 			 * its predecessor instead. This means we have to
2493 			 * transfer the predecessor's sub_vcn to the end entry.
2494 			 * Note: This index block is not empty, so the
2495 			 * predecessor must exist.
2496 			 */
2497 			if (!prev) {
2498 				err = -EINVAL;
2499 				goto out;
2500 			}
2501 
2502 			if (de_has_vcn(prev)) {
2503 				de_set_vbn_le(e, de_get_vbn_le(prev));
2504 			} else if (de_has_vcn(e)) {
2505 				le16_sub_cpu(&e->size, sizeof(u64));
2506 				e->flags &= ~NTFS_IE_HAS_SUBNODES;
2507 				le32_sub_cpu(&hdr->used, sizeof(u64));
2508 			}
2509 			e = prev;
2510 		}
2511 
2512 		/*
2513 		 * Copy the current entry into a temporary buffer (stripping
2514 		 * off its down-pointer, if any) and delete it from the current
2515 		 * buffer or root, as appropriate.
2516 		 */
2517 		e_size = le16_to_cpu(e->size);
2518 		me = kmemdup(e, e_size, GFP_NOFS);
2519 		if (!me) {
2520 			err = -ENOMEM;
2521 			goto out;
2522 		}
2523 
2524 		if (de_has_vcn(me)) {
2525 			me->flags &= ~NTFS_IE_HAS_SUBNODES;
2526 			le16_sub_cpu(&me->size, sizeof(u64));
2527 		}
2528 
2529 		hdr_delete_de(hdr, e);
2530 
2531 		if (hdr == &root->ihdr) {
2532 			level = 0;
2533 			hdr->total = hdr->used;
2534 
2535 			/* Shrink resident root attribute. */
2536 			mi_resize_attr(mi, attr, 0 - e_size);
2537 		} else {
2538 			indx_write(indx, ni, n2d, 0);
2539 			level = level2;
2540 		}
2541 
2542 		/* Mark unused buffers as free. */
2543 		trim_bit = -1;
2544 		for (; level < fnd->level; level++) {
2545 			ib = fnd->nodes[level]->index;
2546 			if (ib_is_empty(ib)) {
2547 				size_t k = le64_to_cpu(ib->vbn) >>
2548 					   indx->idx2vbn_bits;
2549 
2550 				indx_mark_free(indx, ni, k);
2551 				if (k < trim_bit)
2552 					trim_bit = k;
2553 			}
2554 		}
2555 
2556 		fnd_clear(fnd);
2557 		/*fnd->root_de = NULL;*/
2558 
2559 		/*
2560 		 * Re-insert the entry into the tree.
2561 		 * Find the spot the tree where we want to insert the new entry.
2562 		 */
2563 		err = indx_insert_entry(indx, ni, me, ctx, fnd, 0);
2564 		kfree(me);
2565 		if (err)
2566 			goto out;
2567 
2568 		if (trim_bit != -1)
2569 			indx_shrink(indx, ni, trim_bit);
2570 	} else {
2571 		/*
2572 		 * This tree needs to be collapsed down to an empty root.
2573 		 * Recreate the index root as an empty leaf and free all
2574 		 * the bits the index allocation bitmap.
2575 		 */
2576 		fnd_clear(fnd);
2577 		fnd_clear(fnd2);
2578 
2579 		in = &s_index_names[indx->type];
2580 
2581 		err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
2582 				    &indx->alloc_run, 0, NULL, false, NULL);
2583 		if (in->name == I30_NAME)
2584 			i_size_write(&ni->vfs_inode, 0);
2585 
2586 		err = ni_remove_attr(ni, ATTR_ALLOC, in->name, in->name_len,
2587 				     false, NULL);
2588 		run_close(&indx->alloc_run);
2589 
2590 		err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
2591 				    &indx->bitmap_run, 0, NULL, false, NULL);
2592 		err = ni_remove_attr(ni, ATTR_BITMAP, in->name, in->name_len,
2593 				     false, NULL);
2594 		run_close(&indx->bitmap_run);
2595 
2596 		root = indx_get_root(indx, ni, &attr, &mi);
2597 		if (!root) {
2598 			err = -EINVAL;
2599 			goto out;
2600 		}
2601 
2602 		root_size = le32_to_cpu(attr->res.data_size);
2603 		new_root_size =
2604 			sizeof(struct INDEX_ROOT) + sizeof(struct NTFS_DE);
2605 
2606 		if (new_root_size != root_size &&
2607 		    !mi_resize_attr(mi, attr, new_root_size - root_size)) {
2608 			err = -EINVAL;
2609 			goto out;
2610 		}
2611 
2612 		/* Fill first entry. */
2613 		e = (struct NTFS_DE *)(root + 1);
2614 		e->ref.low = 0;
2615 		e->ref.high = 0;
2616 		e->ref.seq = 0;
2617 		e->size = cpu_to_le16(sizeof(struct NTFS_DE));
2618 		e->flags = NTFS_IE_LAST; // 0x02
2619 		e->key_size = 0;
2620 		e->res = 0;
2621 
2622 		hdr = &root->ihdr;
2623 		hdr->flags = 0;
2624 		hdr->used = hdr->total = cpu_to_le32(
2625 			new_root_size - offsetof(struct INDEX_ROOT, ihdr));
2626 		mi->dirty = true;
2627 	}
2628 
2629 out:
2630 	fnd_put(fnd2);
2631 out1:
2632 	fnd_put(fnd);
2633 out2:
2634 	return err;
2635 }
2636 
2637 /*
2638  * Update duplicated information in directory entry
2639  * 'dup' - info from MFT record
2640  */
indx_update_dup(struct ntfs_inode * ni,struct ntfs_sb_info * sbi,const struct ATTR_FILE_NAME * fname,const struct NTFS_DUP_INFO * dup,int sync)2641 int indx_update_dup(struct ntfs_inode *ni, struct ntfs_sb_info *sbi,
2642 		    const struct ATTR_FILE_NAME *fname,
2643 		    const struct NTFS_DUP_INFO *dup, int sync)
2644 {
2645 	int err, diff;
2646 	struct NTFS_DE *e = NULL;
2647 	struct ATTR_FILE_NAME *e_fname;
2648 	struct ntfs_fnd *fnd;
2649 	struct INDEX_ROOT *root;
2650 	struct mft_inode *mi;
2651 	struct ntfs_index *indx = &ni->dir;
2652 
2653 	fnd = fnd_get();
2654 	if (!fnd)
2655 		return -ENOMEM;
2656 
2657 	root = indx_get_root(indx, ni, NULL, &mi);
2658 	if (!root) {
2659 		err = -EINVAL;
2660 		goto out;
2661 	}
2662 
2663 	/* Find entry in directory. */
2664 	err = indx_find(indx, ni, root, fname, fname_full_size(fname), sbi,
2665 			&diff, &e, fnd);
2666 	if (err)
2667 		goto out;
2668 
2669 	if (!e) {
2670 		err = -EINVAL;
2671 		goto out;
2672 	}
2673 
2674 	if (diff) {
2675 		err = -EINVAL;
2676 		goto out;
2677 	}
2678 
2679 	e_fname = (struct ATTR_FILE_NAME *)(e + 1);
2680 
2681 	if (!memcmp(&e_fname->dup, dup, sizeof(*dup))) {
2682 		/*
2683 		 * Nothing to update in index! Try to avoid this call.
2684 		 */
2685 		goto out;
2686 	}
2687 
2688 	memcpy(&e_fname->dup, dup, sizeof(*dup));
2689 
2690 	if (fnd->level) {
2691 		/* Directory entry in index. */
2692 		err = indx_write(indx, ni, fnd->nodes[fnd->level - 1], sync);
2693 	} else {
2694 		/* Directory entry in directory MFT record. */
2695 		mi->dirty = true;
2696 		if (sync)
2697 			err = mi_write(mi, 1);
2698 		else
2699 			mark_inode_dirty(&ni->vfs_inode);
2700 	}
2701 
2702 out:
2703 	fnd_put(fnd);
2704 	return err;
2705 }
2706