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