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