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