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