1 // SPDX-License-Identifier: GPL-2.0
4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
8 #include <linux/blkdev.h>
9 #include <linux/buffer_head.h>
11 #include <linux/kernel.h>
17 static const struct INDEX_NAMES
{
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
) },
27 * cmp_fnames - Compare two names in index.
30 * Both names are little endian on-disk ATTR_FILE_NAME structs.
32 * key1 - cpu_str, key2 - ATTR_FILE_NAME
34 static int cmp_fnames(const void *key1
, size_t l1
, const void *key2
, size_t l2
,
37 const struct ATTR_FILE_NAME
*f2
= key2
;
38 const struct ntfs_sb_info
*sbi
= data
;
39 const struct ATTR_FILE_NAME
*f1
;
43 if (l2
<= offsetof(struct ATTR_FILE_NAME
, name
))
46 fsize2
= fname_full_size(f2
);
50 both_case
= f2
->type
!= FILE_NAME_DOS
&& !sbi
->options
->nocase
;
52 const struct le_str
*s2
= (struct le_str
*)&f2
->name_len
;
55 * If names are equal (case insensitive)
56 * try to compare it case sensitive.
58 return ntfs_cmp_names_cpu(key1
, s2
, sbi
->upcase
, both_case
);
62 return ntfs_cmp_names(f1
->name
, f1
->name_len
, f2
->name
, f2
->name_len
,
63 sbi
->upcase
, both_case
);
67 * cmp_uint - $SII of $Secure and $Q of Quota
69 static int cmp_uint(const void *key1
, size_t l1
, const void *key2
, size_t l2
,
86 * cmp_sdh - $SDH of $Secure
88 static int cmp_sdh(const void *key1
, size_t l1
, const void *key2
, size_t l2
,
91 const struct SECURITY_KEY
*k1
= key1
;
92 const struct SECURITY_KEY
*k2
= key2
;
95 if (l2
< sizeof(struct SECURITY_KEY
))
98 t1
= le32_to_cpu(k1
->hash
);
99 t2
= le32_to_cpu(k2
->hash
);
101 /* First value is a hash value itself. */
107 /* Second value is security Id. */
109 t1
= le32_to_cpu(k1
->sec_id
);
110 t2
= le32_to_cpu(k2
->sec_id
);
121 * cmp_uints - $O of ObjId and "$R" for Reparse.
123 static int cmp_uints(const void *key1
, size_t l1
, const void *key2
, size_t l2
,
126 const __le32
*k1
= key1
;
127 const __le32
*k2
= key2
;
130 if ((size_t)data
== 1) {
132 * ni_delete_all -> ntfs_remove_reparse ->
133 * delete all with this reference.
134 * k1, k2 - pointers to REPARSE_KEY
137 k1
+= 1; // Skip REPARSE_KEY.ReparseTag
138 k2
+= 1; // Skip REPARSE_KEY.ReparseTag
139 if (l2
<= sizeof(int))
142 if (l1
<= sizeof(int))
147 if (l2
< sizeof(int))
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
);
168 static inline NTFS_CMP_FUNC
get_cmp_func(const struct INDEX_ROOT
*root
)
170 switch (root
->type
) {
172 if (root
->rule
== NTFS_COLLATION_TYPE_FILENAME
)
176 switch (root
->rule
) {
177 case NTFS_COLLATION_TYPE_UINT
:
179 case NTFS_COLLATION_TYPE_SECURITY_HASH
:
181 case NTFS_COLLATION_TYPE_UINTS
:
196 struct mft_inode
*mi
;
197 struct buffer_head
*bh
;
204 static int bmp_buf_get(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
205 size_t bit
, struct bmp_buf
*bbuf
)
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
;
215 const struct INDEX_NAMES
*in
= &s_index_names
[indx
->type
];
219 b
= ni_find_attr(ni
, NULL
, &le
, ATTR_BITMAP
, in
->name
, in
->name_len
,
226 data_size
= le32_to_cpu(b
->res
.data_size
);
228 if (off
>= data_size
)
231 bbuf
->buf
= (ulong
*)resident_data(b
);
233 bbuf
->nbits
= data_size
* 8;
238 data_size
= le64_to_cpu(b
->nres
.data_size
);
239 if (WARN_ON(off
>= data_size
)) {
240 /* Looks like filesystem error. */
244 valid_size
= le64_to_cpu(b
->nres
.valid_size
);
246 bh
= ntfs_bread_run(sbi
, &indx
->bitmap_run
, off
);
255 if (buffer_locked(bh
))
256 __wait_on_buffer(bh
);
261 blocksize
= sb
->s_blocksize
;
263 vbo
= off
& ~(size_t)sbi
->block_mask
;
265 bbuf
->new_valid
= vbo
+ blocksize
;
266 if (bbuf
->new_valid
<= valid_size
)
268 else if (bbuf
->new_valid
> data_size
)
269 bbuf
->new_valid
= data_size
;
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
;
276 memset(bh
->b_data
+ voff
, 0, blocksize
- voff
);
279 bbuf
->buf
= (ulong
*)bh
->b_data
;
280 bbuf
->bit
= 8 * (off
& ~(size_t)sbi
->block_mask
);
281 bbuf
->nbits
= 8 * blocksize
;
286 static void bmp_buf_put(struct bmp_buf
*bbuf
, bool dirty
)
288 struct buffer_head
*bh
= bbuf
->bh
;
289 struct ATTRIB
*b
= bbuf
->b
;
292 if (b
&& !b
->non_res
&& dirty
)
293 bbuf
->mi
->dirty
= true;
300 if (bbuf
->new_valid
) {
301 b
->nres
.valid_size
= cpu_to_le64(bbuf
->new_valid
);
302 bbuf
->mi
->dirty
= true;
305 set_buffer_uptodate(bh
);
306 mark_buffer_dirty(bh
);
314 * indx_mark_used - Mark the bit @bit as used.
316 static int indx_mark_used(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
322 err
= bmp_buf_get(indx
, ni
, bit
, &bbuf
);
326 __set_bit_le(bit
- bbuf
.bit
, bbuf
.buf
);
328 bmp_buf_put(&bbuf
, true);
334 * indx_mark_free - Mark the bit @bit as free.
336 static int indx_mark_free(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
342 err
= bmp_buf_get(indx
, ni
, bit
, &bbuf
);
346 __clear_bit_le(bit
- bbuf
.bit
, bbuf
.buf
);
348 bmp_buf_put(&bbuf
, true);
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.
360 static int scan_nres_bitmap(struct ntfs_inode
*ni
, struct ATTRIB
*bitmap
,
361 struct ntfs_index
*indx
, size_t from
,
362 bool (*fn
)(const ulong
*buf
, u32 bit
, u32 bits
,
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
;
381 struct buffer_head
*bh
;
386 if (vblock
>= eblock
)
390 vcn
= vbo
>> sbi
->cluster_bits
;
393 ok
= run_lookup_entry(run
, vcn
, &lcn
, &clen
, &idx
);
399 const struct INDEX_NAMES
*name
= &s_index_names
[indx
->type
];
402 err
= attr_load_runs_vcn(ni
, ATTR_BITMAP
, name
->name
,
403 name
->name_len
, run
, vcn
);
408 ok
= run_lookup_entry(run
, vcn
, &lcn
, &clen
, &idx
);
414 blen
= (sector_t
)clen
* sbi
->blocks_per_cluster
;
415 block
= (sector_t
)lcn
* sbi
->blocks_per_cluster
;
417 for (; blk
< blen
; blk
++, from
= 0) {
418 bh
= ntfs_bread(sb
, block
+ blk
);
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
;
428 memset(bh
->b_data
+ voff
, 0, blocksize
- voff
);
431 if (vbo
+ blocksize
> data_size
)
432 nbits
= 8 * (data_size
- vbo
);
434 ok
= nbits
> from
? (*fn
)((ulong
*)bh
->b_data
, from
, nbits
, ret
)
443 if (++vblock
>= eblock
) {
449 vcn_next
= vcn
+ clen
;
451 ok
= run_get_entry(run
, ++idx
, &vcn
, &lcn
, &clen
) && vcn
== vcn_next
;
458 static bool scan_for_free(const ulong
*buf
, u32 bit
, u32 bits
, size_t *ret
)
460 size_t pos
= find_next_zero_bit_le(buf
, bits
, bit
);
469 * indx_find_free - Look for free bit.
471 * Return: -1 if no free bits.
473 static int indx_find_free(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
474 size_t *bit
, struct ATTRIB
**bitmap
)
477 struct ATTR_LIST_ENTRY
*le
= NULL
;
478 const struct INDEX_NAMES
*in
= &s_index_names
[indx
->type
];
481 b
= ni_find_attr(ni
, NULL
, &le
, ATTR_BITMAP
, in
->name
, in
->name_len
,
491 u32 nbits
= 8 * le32_to_cpu(b
->res
.data_size
);
492 size_t pos
= find_next_zero_bit_le(resident_data(b
), nbits
, 0);
497 err
= scan_nres_bitmap(ni
, b
, indx
, 0, &scan_for_free
, bit
);
506 static bool scan_for_used(const ulong
*buf
, u32 bit
, u32 bits
, size_t *ret
)
508 size_t pos
= find_next_bit_le(buf
, bits
, bit
);
517 * indx_used_bit - Look for used bit.
519 * Return: MINUS_ONE_T if no used bits.
521 int indx_used_bit(struct ntfs_index
*indx
, struct ntfs_inode
*ni
, size_t *bit
)
524 struct ATTR_LIST_ENTRY
*le
= NULL
;
526 const struct INDEX_NAMES
*in
= &s_index_names
[indx
->type
];
529 b
= ni_find_attr(ni
, NULL
, &le
, ATTR_BITMAP
, in
->name
, in
->name_len
,
538 u32 nbits
= le32_to_cpu(b
->res
.data_size
) * 8;
539 size_t pos
= find_next_bit_le(resident_data(b
), nbits
, from
);
544 err
= scan_nres_bitmap(ni
, b
, indx
, from
, &scan_for_used
, bit
);
555 * Find a point at which the index allocation buffer would like to be split.
556 * NOTE: This function should never return 'END' entry NULL returns on error.
558 static const struct NTFS_DE
*hdr_find_split(const struct INDEX_HDR
*hdr
)
561 const struct NTFS_DE
*e
= hdr_first_de(hdr
);
562 u32 used_2
= le32_to_cpu(hdr
->used
) >> 1;
565 if (!e
|| de_is_last(e
))
568 esize
= le16_to_cpu(e
->size
);
569 for (o
= le32_to_cpu(hdr
->de_off
) + esize
; o
< used_2
; o
+= esize
) {
570 const struct NTFS_DE
*p
= e
;
574 /* We must not return END entry. */
578 esize
= le16_to_cpu(e
->size
);
585 * hdr_insert_head - Insert some entries at the beginning of the buffer.
587 * It is used to insert entries into a newly-created buffer.
589 static const struct NTFS_DE
*hdr_insert_head(struct INDEX_HDR
*hdr
,
590 const void *ins
, u32 ins_bytes
)
593 struct NTFS_DE
*e
= hdr_first_de(hdr
);
594 u32 used
= le32_to_cpu(hdr
->used
);
599 /* Now we just make room for the inserted entries and jam it in. */
600 to_move
= used
- le32_to_cpu(hdr
->de_off
);
601 memmove(Add2Ptr(e
, ins_bytes
), e
, to_move
);
602 memcpy(e
, ins
, ins_bytes
);
603 hdr
->used
= cpu_to_le32(used
+ ins_bytes
);
611 * return true if INDEX_HDR is valid
613 static bool index_hdr_check(const struct INDEX_HDR
*hdr
, u32 bytes
)
615 u32 end
= le32_to_cpu(hdr
->used
);
616 u32 tot
= le32_to_cpu(hdr
->total
);
617 u32 off
= le32_to_cpu(hdr
->de_off
);
619 if (!IS_ALIGNED(off
, 8) || tot
> bytes
|| end
> tot
||
620 off
+ sizeof(struct NTFS_DE
) > end
) {
621 /* incorrect index buffer. */
631 * return true if INDEX_BUFFER seems is valid
633 static bool index_buf_check(const struct INDEX_BUFFER
*ib
, u32 bytes
,
636 const struct NTFS_RECORD_HEADER
*rhdr
= &ib
->rhdr
;
637 u16 fo
= le16_to_cpu(rhdr
->fix_off
);
638 u16 fn
= le16_to_cpu(rhdr
->fix_num
);
640 if (bytes
<= offsetof(struct INDEX_BUFFER
, ihdr
) ||
641 rhdr
->sign
!= NTFS_INDX_SIGNATURE
||
642 fo
< sizeof(struct INDEX_BUFFER
)
643 /* Check index buffer vbn. */
644 || (vbn
&& *vbn
!= le64_to_cpu(ib
->vbn
)) || (fo
% sizeof(short)) ||
645 fo
+ fn
* sizeof(short) >= bytes
||
646 fn
!= ((bytes
>> SECTOR_SHIFT
) + 1)) {
647 /* incorrect index buffer. */
651 return index_hdr_check(&ib
->ihdr
,
652 bytes
- offsetof(struct INDEX_BUFFER
, ihdr
));
655 void fnd_clear(struct ntfs_fnd
*fnd
)
659 for (i
= fnd
->level
- 1; i
>= 0; i
--) {
660 struct indx_node
*n
= fnd
->nodes
[i
];
666 fnd
->nodes
[i
] = NULL
;
672 static int fnd_push(struct ntfs_fnd
*fnd
, struct indx_node
*n
,
677 if (i
< 0 || i
>= ARRAY_SIZE(fnd
->nodes
))
685 static struct indx_node
*fnd_pop(struct ntfs_fnd
*fnd
)
692 fnd
->nodes
[i
] = NULL
;
698 static bool fnd_is_empty(struct ntfs_fnd
*fnd
)
701 return !fnd
->root_de
;
703 return !fnd
->de
[fnd
->level
- 1];
707 * hdr_find_e - Locate an entry the index buffer.
709 * If no matching entry is found, it returns the first entry which is greater
710 * than the desired entry If the search key is greater than all the entries the
711 * buffer, it returns the 'end' entry. This function does a binary search of the
712 * current index buffer, for the first entry that is <= to the search value.
714 * Return: NULL if error.
716 static struct NTFS_DE
*hdr_find_e(const struct ntfs_index
*indx
,
717 const struct INDEX_HDR
*hdr
, const void *key
,
718 size_t key_len
, const void *ctx
, int *diff
)
720 struct NTFS_DE
*e
, *found
= NULL
;
721 NTFS_CMP_FUNC cmp
= indx
->cmp
;
722 int min_idx
= 0, mid_idx
, max_idx
= 0;
725 u32 e_size
, e_key_len
;
726 u32 end
= le32_to_cpu(hdr
->used
);
727 u32 off
= le32_to_cpu(hdr
->de_off
);
731 if (off
+ sizeof(struct NTFS_DE
) > end
)
734 e
= Add2Ptr(hdr
, off
);
735 e_size
= le16_to_cpu(e
->size
);
737 if (e_size
< sizeof(struct NTFS_DE
) || off
+ e_size
> end
)
740 if (!de_is_last(e
)) {
745 if (max_idx
< table_size
)
752 e_key_len
= le16_to_cpu(e
->key_size
);
754 diff2
= (*cmp
)(key
, key_len
, e
+ 1, e_key_len
, ctx
);
757 min_idx
= mid_idx
+ 1;
763 table_size
= min(table_size
* 2,
764 (int)ARRAY_SIZE(offs
));
767 } else if (diff2
< 0) {
769 max_idx
= mid_idx
- 1;
779 if (min_idx
> max_idx
) {
784 mid_idx
= (min_idx
+ max_idx
) >> 1;
785 e
= Add2Ptr(hdr
, offs
[mid_idx
]);
791 * hdr_insert_de - Insert an index entry into the buffer.
793 * 'before' should be a pointer previously returned from hdr_find_e.
795 static struct NTFS_DE
*hdr_insert_de(const struct ntfs_index
*indx
,
796 struct INDEX_HDR
*hdr
,
797 const struct NTFS_DE
*de
,
798 struct NTFS_DE
*before
, const void *ctx
)
801 size_t off
= PtrOffset(hdr
, before
);
802 u32 used
= le32_to_cpu(hdr
->used
);
803 u32 total
= le32_to_cpu(hdr
->total
);
804 u16 de_size
= le16_to_cpu(de
->size
);
806 /* First, check to see if there's enough room. */
807 if (used
+ de_size
> total
)
810 /* We know there's enough space, so we know we'll succeed. */
812 /* Check that before is inside Index. */
813 if (off
>= used
|| off
< le32_to_cpu(hdr
->de_off
) ||
814 off
+ le16_to_cpu(before
->size
) > total
) {
819 /* No insert point is applied. Get it manually. */
820 before
= hdr_find_e(indx
, hdr
, de
+ 1, le16_to_cpu(de
->key_size
), ctx
,
824 off
= PtrOffset(hdr
, before
);
827 /* Now we just make room for the entry and jam it in. */
828 memmove(Add2Ptr(before
, de_size
), before
, used
- off
);
830 hdr
->used
= cpu_to_le32(used
+ de_size
);
831 memcpy(before
, de
, de_size
);
837 * hdr_delete_de - Remove an entry from the index buffer.
839 static inline struct NTFS_DE
*hdr_delete_de(struct INDEX_HDR
*hdr
,
842 u32 used
= le32_to_cpu(hdr
->used
);
843 u16 esize
= le16_to_cpu(re
->size
);
844 u32 off
= PtrOffset(hdr
, re
);
845 int bytes
= used
- (off
+ esize
);
847 if (off
>= used
|| esize
< sizeof(struct NTFS_DE
) ||
848 bytes
< sizeof(struct NTFS_DE
))
851 hdr
->used
= cpu_to_le32(used
- esize
);
852 memmove(re
, Add2Ptr(re
, esize
), bytes
);
857 void indx_clear(struct ntfs_index
*indx
)
859 run_close(&indx
->alloc_run
);
860 run_close(&indx
->bitmap_run
);
863 int indx_init(struct ntfs_index
*indx
, struct ntfs_sb_info
*sbi
,
864 const struct ATTRIB
*attr
, enum index_mutex_classed type
)
867 const struct INDEX_ROOT
*root
= resident_data(attr
);
869 t32
= le32_to_cpu(attr
->res
.data_size
);
870 if (t32
<= offsetof(struct INDEX_ROOT
, ihdr
) ||
871 !index_hdr_check(&root
->ihdr
,
872 t32
- offsetof(struct INDEX_ROOT
, ihdr
))) {
876 /* Check root fields. */
877 if (!root
->index_block_clst
)
881 indx
->idx2vbn_bits
= __ffs(root
->index_block_clst
);
883 t32
= le32_to_cpu(root
->index_block_size
);
884 indx
->index_bits
= blksize_bits(t32
);
886 /* Check index record size. */
887 if (t32
< sbi
->cluster_size
) {
888 /* Index record is smaller than a cluster, use 512 blocks. */
889 if (t32
!= root
->index_block_clst
* SECTOR_SIZE
)
892 /* Check alignment to a cluster. */
893 if ((sbi
->cluster_size
>> SECTOR_SHIFT
) &
894 (root
->index_block_clst
- 1)) {
898 indx
->vbn2vbo_bits
= SECTOR_SHIFT
;
900 /* Index record must be a multiple of cluster size. */
901 if (t32
!= root
->index_block_clst
<< sbi
->cluster_bits
)
904 indx
->vbn2vbo_bits
= sbi
->cluster_bits
;
907 init_rwsem(&indx
->run_lock
);
909 indx
->cmp
= get_cmp_func(root
);
916 ntfs_set_state(sbi
, NTFS_DIRTY_DIRTY
);
920 static struct indx_node
*indx_new(struct ntfs_index
*indx
,
921 struct ntfs_inode
*ni
, CLST vbn
,
922 const __le64
*sub_vbn
)
927 struct INDEX_HDR
*hdr
;
928 struct INDEX_BUFFER
*index
;
929 u64 vbo
= (u64
)vbn
<< indx
->vbn2vbo_bits
;
930 u32 bytes
= 1u << indx
->index_bits
;
934 r
= kzalloc(sizeof(struct indx_node
), GFP_NOFS
);
936 return ERR_PTR(-ENOMEM
);
938 index
= kzalloc(bytes
, GFP_NOFS
);
941 return ERR_PTR(-ENOMEM
);
944 err
= ntfs_get_bh(ni
->mi
.sbi
, &indx
->alloc_run
, vbo
, bytes
, &r
->nb
);
953 index
->rhdr
.sign
= NTFS_INDX_SIGNATURE
;
954 index
->rhdr
.fix_off
= cpu_to_le16(sizeof(struct INDEX_BUFFER
)); // 0x28
955 fn
= (bytes
>> SECTOR_SHIFT
) + 1; // 9
956 index
->rhdr
.fix_num
= cpu_to_le16(fn
);
957 index
->vbn
= cpu_to_le64(vbn
);
959 eo
= ALIGN(sizeof(struct INDEX_BUFFER
) + fn
* sizeof(short), 8);
960 hdr
->de_off
= cpu_to_le32(eo
);
962 e
= Add2Ptr(hdr
, eo
);
965 e
->flags
= NTFS_IE_LAST
| NTFS_IE_HAS_SUBNODES
;
966 e
->size
= cpu_to_le16(sizeof(struct NTFS_DE
) + sizeof(u64
));
968 cpu_to_le32(eo
+ sizeof(struct NTFS_DE
) + sizeof(u64
));
969 de_set_vbn_le(e
, *sub_vbn
);
972 e
->size
= cpu_to_le16(sizeof(struct NTFS_DE
));
973 hdr
->used
= cpu_to_le32(eo
+ sizeof(struct NTFS_DE
));
974 e
->flags
= NTFS_IE_LAST
;
977 hdr
->total
= cpu_to_le32(bytes
- offsetof(struct INDEX_BUFFER
, ihdr
));
983 struct INDEX_ROOT
*indx_get_root(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
984 struct ATTRIB
**attr
, struct mft_inode
**mi
)
986 struct ATTR_LIST_ENTRY
*le
= NULL
;
988 const struct INDEX_NAMES
*in
= &s_index_names
[indx
->type
];
990 a
= ni_find_attr(ni
, NULL
, &le
, ATTR_ROOT
, in
->name
, in
->name_len
, NULL
,
998 return resident_data_ex(a
, sizeof(struct INDEX_ROOT
));
1001 static int indx_write(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1002 struct indx_node
*node
, int sync
)
1004 struct INDEX_BUFFER
*ib
= node
->index
;
1006 return ntfs_write_bh(ni
->mi
.sbi
, &ib
->rhdr
, &node
->nb
, sync
);
1012 * If ntfs_readdir calls this function
1013 * inode is shared locked and no ni_lock.
1014 * Use rw_semaphore for read/write access to alloc_run.
1016 int indx_read(struct ntfs_index
*indx
, struct ntfs_inode
*ni
, CLST vbn
,
1017 struct indx_node
**node
)
1020 struct INDEX_BUFFER
*ib
;
1021 struct runs_tree
*run
= &indx
->alloc_run
;
1022 struct rw_semaphore
*lock
= &indx
->run_lock
;
1023 u64 vbo
= (u64
)vbn
<< indx
->vbn2vbo_bits
;
1024 u32 bytes
= 1u << indx
->index_bits
;
1025 struct indx_node
*in
= *node
;
1026 const struct INDEX_NAMES
*name
;
1029 in
= kzalloc(sizeof(struct indx_node
), GFP_NOFS
);
1038 ib
= kmalloc(bytes
, GFP_NOFS
);
1046 err
= ntfs_read_bh(ni
->mi
.sbi
, run
, vbo
, &ib
->rhdr
, bytes
, &in
->nb
);
1051 if (err
== -E_NTFS_FIXUP
)
1057 name
= &s_index_names
[indx
->type
];
1059 err
= attr_load_runs_range(ni
, ATTR_ALLOC
, name
->name
, name
->name_len
,
1060 run
, vbo
, vbo
+ bytes
);
1066 err
= ntfs_read_bh(ni
->mi
.sbi
, run
, vbo
, &ib
->rhdr
, bytes
, &in
->nb
);
1068 if (err
== -E_NTFS_FIXUP
)
1075 if (!index_buf_check(ib
, bytes
, &vbn
)) {
1076 ntfs_inode_err(&ni
->vfs_inode
, "directory corrupted");
1077 ntfs_set_state(ni
->mi
.sbi
, NTFS_DIRTY_ERROR
);
1082 if (err
== -E_NTFS_FIXUP
) {
1083 ntfs_write_bh(ni
->mi
.sbi
, &ib
->rhdr
, &in
->nb
, 0);
1087 /* check for index header length */
1088 if (offsetof(struct INDEX_BUFFER
, ihdr
) + ib
->ihdr
.used
> bytes
) {
1097 if (ib
!= in
->index
)
1109 * indx_find - Scan NTFS directory for given entry.
1111 int indx_find(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1112 const struct INDEX_ROOT
*root
, const void *key
, size_t key_len
,
1113 const void *ctx
, int *diff
, struct NTFS_DE
**entry
,
1114 struct ntfs_fnd
*fnd
)
1118 struct indx_node
*node
;
1121 root
= indx_get_root(&ni
->dir
, ni
, NULL
, NULL
);
1124 /* Should not happen. */
1129 e
= fnd
->level
? fnd
->de
[fnd
->level
- 1] : fnd
->root_de
;
1130 if (e
&& !de_is_last(e
) &&
1131 !(*indx
->cmp
)(key
, key_len
, e
+ 1, le16_to_cpu(e
->key_size
), ctx
)) {
1137 /* Soft finder reset. */
1140 /* Lookup entry that is <= to the search value. */
1141 e
= hdr_find_e(indx
, &root
->ihdr
, key
, key_len
, ctx
, diff
);
1149 if (*diff
>= 0 || !de_has_vcn_ex(e
))
1152 /* Read next level. */
1153 err
= indx_read(indx
, ni
, de_get_vbn(e
), &node
);
1157 /* Lookup entry that is <= to the search value. */
1158 e
= hdr_find_e(indx
, &node
->index
->ihdr
, key
, key_len
, ctx
,
1161 put_indx_node(node
);
1165 fnd_push(fnd
, node
, e
);
1172 int indx_find_sort(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1173 const struct INDEX_ROOT
*root
, struct NTFS_DE
**entry
,
1174 struct ntfs_fnd
*fnd
)
1177 struct indx_node
*n
= NULL
;
1180 int level
= fnd
->level
;
1184 e
= hdr_first_de(&root
->ihdr
);
1189 } else if (!level
) {
1190 if (de_is_last(fnd
->root_de
)) {
1195 e
= hdr_next_de(&root
->ihdr
, fnd
->root_de
);
1200 n
= fnd
->nodes
[level
- 1];
1201 e
= fnd
->de
[level
- 1];
1206 e
= hdr_next_de(&n
->index
->ihdr
, e
);
1210 fnd
->de
[level
- 1] = e
;
1213 /* Just to avoid tree cycle. */
1218 while (de_has_vcn_ex(e
)) {
1219 if (le16_to_cpu(e
->size
) <
1220 sizeof(struct NTFS_DE
) + sizeof(u64
)) {
1228 /* Read next level. */
1229 err
= indx_read(indx
, ni
, de_get_vbn(e
), &n
);
1233 /* Try next level. */
1234 e
= hdr_first_de(&n
->index
->ihdr
);
1240 fnd_push(fnd
, n
, e
);
1243 if (le16_to_cpu(e
->size
) > sizeof(struct NTFS_DE
)) {
1253 /* Pop one level. */
1262 n
= fnd
->nodes
[level
- 1];
1263 e
= fnd
->de
[level
- 1];
1264 } else if (fnd
->root_de
) {
1267 fnd
->root_de
= NULL
;
1273 if (le16_to_cpu(e
->size
) > sizeof(struct NTFS_DE
)) {
1282 int indx_find_raw(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1283 const struct INDEX_ROOT
*root
, struct NTFS_DE
**entry
,
1284 size_t *off
, struct ntfs_fnd
*fnd
)
1287 struct indx_node
*n
= NULL
;
1288 struct NTFS_DE
*e
= NULL
;
1293 u32 record_size
= ni
->mi
.sbi
->record_size
;
1295 /* Use non sorted algorithm. */
1297 /* This is the first call. */
1298 e
= hdr_first_de(&root
->ihdr
);
1304 /* The first call with setup of initial element. */
1305 if (*off
>= record_size
) {
1306 next_vbn
= (((*off
- record_size
) >> indx
->index_bits
))
1307 << indx
->idx2vbn_bits
;
1308 /* Jump inside cycle 'for'. */
1312 /* Start enumeration from root. */
1314 } else if (!fnd
->root_de
)
1318 /* Check if current entry can be used. */
1319 if (e
&& le16_to_cpu(e
->size
) > sizeof(struct NTFS_DE
))
1323 /* Continue to enumerate root. */
1324 if (!de_is_last(fnd
->root_de
)) {
1325 e
= hdr_next_de(&root
->ihdr
, fnd
->root_de
);
1332 /* Start to enumerate indexes from 0. */
1335 /* Continue to enumerate indexes. */
1336 e2
= fnd
->de
[fnd
->level
- 1];
1338 n
= fnd
->nodes
[fnd
->level
- 1];
1340 if (!de_is_last(e2
)) {
1341 e
= hdr_next_de(&n
->index
->ihdr
, e2
);
1344 fnd
->de
[fnd
->level
- 1] = e
;
1348 /* Continue with next index. */
1349 next_vbn
= le64_to_cpu(n
->index
->vbn
) +
1350 root
->index_block_clst
;
1354 /* Release current index. */
1361 /* Skip all free indexes. */
1362 bit
= next_vbn
>> indx
->idx2vbn_bits
;
1363 err
= indx_used_bit(indx
, ni
, &bit
);
1364 if (err
== -ENOENT
|| bit
== MINUS_ONE_T
) {
1365 /* No used indexes. */
1370 next_used_vbn
= bit
<< indx
->idx2vbn_bits
;
1372 /* Read buffer into memory. */
1373 err
= indx_read(indx
, ni
, next_used_vbn
, &n
);
1377 e
= hdr_first_de(&n
->index
->ihdr
);
1378 fnd_push(fnd
, n
, e
);
1384 /* Return offset to restore enumerator if necessary. */
1386 /* 'e' points in root, */
1387 *off
= PtrOffset(&root
->ihdr
, e
);
1389 /* 'e' points in index, */
1390 *off
= (le64_to_cpu(n
->index
->vbn
) << indx
->vbn2vbo_bits
) +
1391 record_size
+ PtrOffset(&n
->index
->ihdr
, e
);
1399 * indx_create_allocate - Create "Allocation + Bitmap" attributes.
1401 static int indx_create_allocate(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1405 struct ntfs_sb_info
*sbi
= ni
->mi
.sbi
;
1406 struct ATTRIB
*bitmap
;
1407 struct ATTRIB
*alloc
;
1408 u32 data_size
= 1u << indx
->index_bits
;
1409 u32 alloc_size
= ntfs_up_cluster(sbi
, data_size
);
1410 CLST len
= alloc_size
>> sbi
->cluster_bits
;
1411 const struct INDEX_NAMES
*in
= &s_index_names
[indx
->type
];
1413 struct runs_tree run
;
1417 err
= attr_allocate_clusters(sbi
, &run
, 0, 0, len
, NULL
, ALLOCATE_DEF
,
1418 &alen
, 0, NULL
, NULL
);
1422 err
= ni_insert_nonresident(ni
, ATTR_ALLOC
, in
->name
, in
->name_len
,
1423 &run
, 0, len
, 0, &alloc
, NULL
, NULL
);
1427 alloc
->nres
.valid_size
= alloc
->nres
.data_size
= cpu_to_le64(data_size
);
1429 err
= ni_insert_resident(ni
, bitmap_size(1), ATTR_BITMAP
, in
->name
,
1430 in
->name_len
, &bitmap
, NULL
, NULL
);
1434 if (in
->name
== I30_NAME
) {
1435 ni
->vfs_inode
.i_size
= data_size
;
1436 inode_set_bytes(&ni
->vfs_inode
, alloc_size
);
1439 memcpy(&indx
->alloc_run
, &run
, sizeof(run
));
1446 mi_remove_attr(NULL
, &ni
->mi
, alloc
);
1449 run_deallocate(sbi
, &run
, false);
1456 * indx_add_allocate - Add clusters to index.
1458 static int indx_add_allocate(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1464 u64 bmp_size
, bmp_size_v
;
1465 struct ATTRIB
*bmp
, *alloc
;
1466 struct mft_inode
*mi
;
1467 const struct INDEX_NAMES
*in
= &s_index_names
[indx
->type
];
1469 err
= indx_find_free(indx
, ni
, &bit
, &bmp
);
1473 if (bit
!= MINUS_ONE_T
) {
1477 bmp_size
= le64_to_cpu(bmp
->nres
.data_size
);
1478 bmp_size_v
= le64_to_cpu(bmp
->nres
.valid_size
);
1480 bmp_size
= bmp_size_v
= le32_to_cpu(bmp
->res
.data_size
);
1483 bit
= bmp_size
<< 3;
1486 data_size
= (u64
)(bit
+ 1) << indx
->index_bits
;
1489 /* Increase bitmap. */
1490 err
= attr_set_size(ni
, ATTR_BITMAP
, in
->name
, in
->name_len
,
1491 &indx
->bitmap_run
, bitmap_size(bit
+ 1),
1497 alloc
= ni_find_attr(ni
, NULL
, NULL
, ATTR_ALLOC
, in
->name
, in
->name_len
,
1506 /* Increase allocation. */
1507 err
= attr_set_size(ni
, ATTR_ALLOC
, in
->name
, in
->name_len
,
1508 &indx
->alloc_run
, data_size
, &data_size
, true,
1516 if (in
->name
== I30_NAME
)
1517 ni
->vfs_inode
.i_size
= data_size
;
1519 *vbn
= bit
<< indx
->idx2vbn_bits
;
1524 /* Ops. No space? */
1525 attr_set_size(ni
, ATTR_BITMAP
, in
->name
, in
->name_len
,
1526 &indx
->bitmap_run
, bmp_size
, &bmp_size_v
, false, NULL
);
1533 * indx_insert_into_root - Attempt to insert an entry into the index root.
1535 * @undo - True if we undoing previous remove.
1536 * If necessary, it will twiddle the index b-tree.
1538 static int indx_insert_into_root(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1539 const struct NTFS_DE
*new_de
,
1540 struct NTFS_DE
*root_de
, const void *ctx
,
1541 struct ntfs_fnd
*fnd
, bool undo
)
1544 struct NTFS_DE
*e
, *e0
, *re
;
1545 struct mft_inode
*mi
;
1546 struct ATTRIB
*attr
;
1547 struct INDEX_HDR
*hdr
;
1548 struct indx_node
*n
;
1550 __le64
*sub_vbn
, t_vbn
;
1552 u32 hdr_used
, hdr_total
, asize
, to_move
;
1553 u32 root_size
, new_root_size
;
1554 struct ntfs_sb_info
*sbi
;
1556 struct INDEX_ROOT
*root
, *a_root
;
1558 /* Get the record this root placed in. */
1559 root
= indx_get_root(indx
, ni
, &attr
, &mi
);
1565 * hdr_insert_de will succeed if there's
1566 * room the root for the new entry.
1570 new_de_size
= le16_to_cpu(new_de
->size
);
1571 hdr_used
= le32_to_cpu(hdr
->used
);
1572 hdr_total
= le32_to_cpu(hdr
->total
);
1573 asize
= le32_to_cpu(attr
->size
);
1574 root_size
= le32_to_cpu(attr
->res
.data_size
);
1576 ds_root
= new_de_size
+ hdr_used
- hdr_total
;
1578 /* If 'undo' is set then reduce requirements. */
1579 if ((undo
|| asize
+ ds_root
< sbi
->max_bytes_per_attr
) &&
1580 mi_resize_attr(mi
, attr
, ds_root
)) {
1581 hdr
->total
= cpu_to_le32(hdr_total
+ ds_root
);
1582 e
= hdr_insert_de(indx
, hdr
, new_de
, root_de
, ctx
);
1590 /* Make a copy of root attribute to restore if error. */
1591 a_root
= kmemdup(attr
, asize
, GFP_NOFS
);
1596 * Copy all the non-end entries from
1597 * the index root to the new buffer.
1600 e0
= hdr_first_de(hdr
);
1602 /* Calculate the size to copy. */
1603 for (e
= e0
;; e
= hdr_next_de(hdr
, e
)) {
1611 to_move
+= le16_to_cpu(e
->size
);
1617 re
= kmemdup(e0
, to_move
, GFP_NOFS
);
1625 if (de_has_vcn(e
)) {
1626 t_vbn
= de_get_vbn_le(e
);
1630 new_root_size
= sizeof(struct INDEX_ROOT
) + sizeof(struct NTFS_DE
) +
1632 ds_root
= new_root_size
- root_size
;
1634 if (ds_root
> 0 && asize
+ ds_root
> sbi
->max_bytes_per_attr
) {
1635 /* Make root external. */
1641 mi_resize_attr(mi
, attr
, ds_root
);
1643 /* Fill first entry (vcn will be set later). */
1644 e
= (struct NTFS_DE
*)(root
+ 1);
1645 memset(e
, 0, sizeof(struct NTFS_DE
));
1646 e
->size
= cpu_to_le16(sizeof(struct NTFS_DE
) + sizeof(u64
));
1647 e
->flags
= NTFS_IE_HAS_SUBNODES
| NTFS_IE_LAST
;
1650 hdr
->used
= hdr
->total
=
1651 cpu_to_le32(new_root_size
- offsetof(struct INDEX_ROOT
, ihdr
));
1653 fnd
->root_de
= hdr_first_de(hdr
);
1656 /* Create alloc and bitmap attributes (if not). */
1657 err
= run_is_empty(&indx
->alloc_run
)
1658 ? indx_create_allocate(indx
, ni
, &new_vbn
)
1659 : indx_add_allocate(indx
, ni
, &new_vbn
);
1661 /* Layout of record may be changed, so rescan root. */
1662 root
= indx_get_root(indx
, ni
, &attr
, &mi
);
1665 ntfs_set_state(sbi
, NTFS_DIRTY_ERROR
);
1672 if (mi_resize_attr(mi
, attr
, -ds_root
)) {
1673 memcpy(attr
, a_root
, asize
);
1676 ntfs_set_state(sbi
, NTFS_DIRTY_ERROR
);
1681 e
= (struct NTFS_DE
*)(root
+ 1);
1682 *(__le64
*)(e
+ 1) = cpu_to_le64(new_vbn
);
1685 /* Now we can create/format the new buffer and copy the entries into. */
1686 n
= indx_new(indx
, ni
, new_vbn
, sub_vbn
);
1692 hdr
= &n
->index
->ihdr
;
1693 hdr_used
= le32_to_cpu(hdr
->used
);
1694 hdr_total
= le32_to_cpu(hdr
->total
);
1696 /* Copy root entries into new buffer. */
1697 hdr_insert_head(hdr
, re
, to_move
);
1699 /* Update bitmap attribute. */
1700 indx_mark_used(indx
, ni
, new_vbn
>> indx
->idx2vbn_bits
);
1702 /* Check if we can insert new entry new index buffer. */
1703 if (hdr_used
+ new_de_size
> hdr_total
) {
1705 * This occurs if MFT record is the same or bigger than index
1706 * buffer. Move all root new index and have no space to add
1707 * new entry classic case when MFT record is 1K and index
1708 * buffer 4K the problem should not occurs.
1711 indx_write(indx
, ni
, n
, 0);
1715 err
= indx_insert_entry(indx
, ni
, new_de
, ctx
, fnd
, undo
);
1720 * Now root is a parent for new index buffer.
1721 * Insert NewEntry a new buffer.
1723 e
= hdr_insert_de(indx
, hdr
, new_de
, NULL
, ctx
);
1728 fnd_push(fnd
, n
, e
);
1730 /* Just write updates index into disk. */
1731 indx_write(indx
, ni
, n
, 0);
1745 * indx_insert_into_buffer
1747 * Attempt to insert an entry into an Index Allocation Buffer.
1748 * If necessary, it will split the buffer.
1751 indx_insert_into_buffer(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1752 struct INDEX_ROOT
*root
, const struct NTFS_DE
*new_de
,
1753 const void *ctx
, int level
, struct ntfs_fnd
*fnd
)
1756 const struct NTFS_DE
*sp
;
1757 struct NTFS_DE
*e
, *de_t
, *up_e
;
1758 struct indx_node
*n2
;
1759 struct indx_node
*n1
= fnd
->nodes
[level
];
1760 struct INDEX_HDR
*hdr1
= &n1
->index
->ihdr
;
1761 struct INDEX_HDR
*hdr2
;
1764 __le64 t_vbn
, *sub_vbn
;
1767 /* Try the most easy case. */
1768 e
= fnd
->level
- 1 == level
? fnd
->de
[level
] : NULL
;
1769 e
= hdr_insert_de(indx
, hdr1
, new_de
, e
, ctx
);
1772 /* Just write updated index into disk. */
1773 indx_write(indx
, ni
, n1
, 0);
1778 * No space to insert into buffer. Split it.
1780 * - Save split point ('cause index buffers will be changed)
1781 * - Allocate NewBuffer and copy all entries <= sp into new buffer
1782 * - Remove all entries (sp including) from TargetBuffer
1783 * - Insert NewEntry into left or right buffer (depending on sp <=>
1785 * - Insert sp into parent buffer (or root)
1786 * - Make sp a parent for new buffer
1788 sp
= hdr_find_split(hdr1
);
1792 sp_size
= le16_to_cpu(sp
->size
);
1793 up_e
= kmalloc(sp_size
+ sizeof(u64
), GFP_NOFS
);
1796 memcpy(up_e
, sp
, sp_size
);
1799 up_e
->flags
|= NTFS_IE_HAS_SUBNODES
;
1800 up_e
->size
= cpu_to_le16(sp_size
+ sizeof(u64
));
1803 t_vbn
= de_get_vbn_le(up_e
);
1807 /* Allocate on disk a new index allocation buffer. */
1808 err
= indx_add_allocate(indx
, ni
, &new_vbn
);
1812 /* Allocate and format memory a new index buffer. */
1813 n2
= indx_new(indx
, ni
, new_vbn
, sub_vbn
);
1819 hdr2
= &n2
->index
->ihdr
;
1821 /* Make sp a parent for new buffer. */
1822 de_set_vbn(up_e
, new_vbn
);
1824 /* Copy all the entries <= sp into the new buffer. */
1825 de_t
= hdr_first_de(hdr1
);
1826 to_copy
= PtrOffset(de_t
, sp
);
1827 hdr_insert_head(hdr2
, de_t
, to_copy
);
1829 /* Remove all entries (sp including) from hdr1. */
1830 used
= le32_to_cpu(hdr1
->used
) - to_copy
- sp_size
;
1831 memmove(de_t
, Add2Ptr(sp
, sp_size
), used
- le32_to_cpu(hdr1
->de_off
));
1832 hdr1
->used
= cpu_to_le32(used
);
1835 * Insert new entry into left or right buffer
1836 * (depending on sp <=> new_de).
1839 (*indx
->cmp
)(new_de
+ 1, le16_to_cpu(new_de
->key_size
),
1840 up_e
+ 1, le16_to_cpu(up_e
->key_size
),
1846 indx_mark_used(indx
, ni
, new_vbn
>> indx
->idx2vbn_bits
);
1848 indx_write(indx
, ni
, n1
, 0);
1849 indx_write(indx
, ni
, n2
, 0);
1854 * We've finished splitting everybody, so we are ready to
1855 * insert the promoted entry into the parent.
1858 /* Insert in root. */
1859 err
= indx_insert_into_root(indx
, ni
, up_e
, NULL
, ctx
, fnd
, 0);
1864 * The target buffer's parent is another index buffer.
1865 * TODO: Remove recursion.
1867 err
= indx_insert_into_buffer(indx
, ni
, root
, up_e
, ctx
,
1880 * indx_insert_entry - Insert new entry into index.
1882 * @undo - True if we undoing previous remove.
1884 int indx_insert_entry(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1885 const struct NTFS_DE
*new_de
, const void *ctx
,
1886 struct ntfs_fnd
*fnd
, bool undo
)
1891 struct ntfs_fnd
*fnd_a
= NULL
;
1892 struct INDEX_ROOT
*root
;
1903 root
= indx_get_root(indx
, ni
, NULL
, NULL
);
1909 if (fnd_is_empty(fnd
)) {
1911 * Find the spot the tree where we want to
1912 * insert the new entry.
1914 err
= indx_find(indx
, ni
, root
, new_de
+ 1,
1915 le16_to_cpu(new_de
->key_size
), ctx
, &diff
, &e
,
1928 * The root is also a leaf, so we'll insert the
1929 * new entry into it.
1931 err
= indx_insert_into_root(indx
, ni
, new_de
, fnd
->root_de
, ctx
,
1937 * Found a leaf buffer, so we'll insert the new entry into it.
1939 err
= indx_insert_into_buffer(indx
, ni
, root
, new_de
, ctx
,
1940 fnd
->level
- 1, fnd
);
1952 * indx_find_buffer - Locate a buffer from the tree.
1954 static struct indx_node
*indx_find_buffer(struct ntfs_index
*indx
,
1955 struct ntfs_inode
*ni
,
1956 const struct INDEX_ROOT
*root
,
1957 __le64 vbn
, struct indx_node
*n
)
1960 const struct NTFS_DE
*e
;
1961 struct indx_node
*r
;
1962 const struct INDEX_HDR
*hdr
= n
? &n
->index
->ihdr
: &root
->ihdr
;
1964 /* Step 1: Scan one level. */
1965 for (e
= hdr_first_de(hdr
);; e
= hdr_next_de(hdr
, e
)) {
1967 return ERR_PTR(-EINVAL
);
1969 if (de_has_vcn(e
) && vbn
== de_get_vbn_le(e
))
1976 /* Step2: Do recursion. */
1977 e
= Add2Ptr(hdr
, le32_to_cpu(hdr
->de_off
));
1979 if (de_has_vcn_ex(e
)) {
1980 err
= indx_read(indx
, ni
, de_get_vbn(e
), &n
);
1982 return ERR_PTR(err
);
1984 r
= indx_find_buffer(indx
, ni
, root
, vbn
, n
);
1992 e
= Add2Ptr(e
, le16_to_cpu(e
->size
));
1999 * indx_shrink - Deallocate unused tail indexes.
2001 static int indx_shrink(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
2008 struct ATTR_LIST_ENTRY
*le
= NULL
;
2009 const struct INDEX_NAMES
*in
= &s_index_names
[indx
->type
];
2011 b
= ni_find_attr(ni
, NULL
, &le
, ATTR_BITMAP
, in
->name
, in
->name_len
,
2019 const unsigned long *bm
= resident_data(b
);
2021 nbits
= (size_t)le32_to_cpu(b
->res
.data_size
) * 8;
2026 pos
= find_next_bit_le(bm
, nbits
, bit
);
2030 size_t used
= MINUS_ONE_T
;
2032 nbits
= le64_to_cpu(b
->nres
.data_size
) * 8;
2037 err
= scan_nres_bitmap(ni
, b
, indx
, bit
, &scan_for_used
, &used
);
2041 if (used
!= MINUS_ONE_T
)
2045 new_data
= (u64
)bit
<< indx
->index_bits
;
2047 err
= attr_set_size(ni
, ATTR_ALLOC
, in
->name
, in
->name_len
,
2048 &indx
->alloc_run
, new_data
, &new_data
, false, NULL
);
2052 if (in
->name
== I30_NAME
)
2053 ni
->vfs_inode
.i_size
= new_data
;
2055 bpb
= bitmap_size(bit
);
2056 if (bpb
* 8 == nbits
)
2059 err
= attr_set_size(ni
, ATTR_BITMAP
, in
->name
, in
->name_len
,
2060 &indx
->bitmap_run
, bpb
, &bpb
, false, NULL
);
2065 static int indx_free_children(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
2066 const struct NTFS_DE
*e
, bool trim
)
2069 struct indx_node
*n
= NULL
;
2070 struct INDEX_HDR
*hdr
;
2071 CLST vbn
= de_get_vbn(e
);
2074 err
= indx_read(indx
, ni
, vbn
, &n
);
2078 hdr
= &n
->index
->ihdr
;
2079 /* First, recurse into the children, if any. */
2080 if (hdr_has_subnode(hdr
)) {
2081 for (e
= hdr_first_de(hdr
); e
; e
= hdr_next_de(hdr
, e
)) {
2082 indx_free_children(indx
, ni
, e
, false);
2090 i
= vbn
>> indx
->idx2vbn_bits
;
2092 * We've gotten rid of the children; add this buffer to the free list.
2094 indx_mark_free(indx
, ni
, i
);
2100 * If there are no used indexes after current free index
2101 * then we can truncate allocation and bitmap.
2102 * Use bitmap to estimate the case.
2104 indx_shrink(indx
, ni
, i
+ 1);
2109 * indx_get_entry_to_replace
2111 * Find a replacement entry for a deleted entry.
2112 * Always returns a node entry:
2113 * NTFS_IE_HAS_SUBNODES is set the flags and the size includes the sub_vcn.
2115 static int indx_get_entry_to_replace(struct ntfs_index
*indx
,
2116 struct ntfs_inode
*ni
,
2117 const struct NTFS_DE
*de_next
,
2118 struct NTFS_DE
**de_to_replace
,
2119 struct ntfs_fnd
*fnd
)
2124 struct NTFS_DE
*e
, *te
, *re
;
2125 struct indx_node
*n
;
2126 struct INDEX_BUFFER
*ib
;
2128 *de_to_replace
= NULL
;
2130 /* Find first leaf entry down from de_next. */
2131 vbn
= de_get_vbn(de_next
);
2134 err
= indx_read(indx
, ni
, vbn
, &n
);
2138 e
= hdr_first_de(&n
->index
->ihdr
);
2139 fnd_push(fnd
, n
, e
);
2141 if (!de_is_last(e
)) {
2143 * This buffer is non-empty, so its first entry
2144 * could be used as the replacement entry.
2146 level
= fnd
->level
- 1;
2152 /* This buffer is a node. Continue to go down. */
2153 vbn
= de_get_vbn(e
);
2159 n
= fnd
->nodes
[level
];
2160 te
= hdr_first_de(&n
->index
->ihdr
);
2161 /* Copy the candidate entry into the replacement entry buffer. */
2162 re
= kmalloc(le16_to_cpu(te
->size
) + sizeof(u64
), GFP_NOFS
);
2168 *de_to_replace
= re
;
2169 memcpy(re
, te
, le16_to_cpu(te
->size
));
2171 if (!de_has_vcn(re
)) {
2173 * The replacement entry we found doesn't have a sub_vcn.
2174 * increase its size to hold one.
2176 le16_add_cpu(&re
->size
, sizeof(u64
));
2177 re
->flags
|= NTFS_IE_HAS_SUBNODES
;
2180 * The replacement entry we found was a node entry, which
2181 * means that all its child buffers are empty. Return them
2184 indx_free_children(indx
, ni
, te
, true);
2188 * Expunge the replacement entry from its former location,
2189 * and then write that buffer.
2192 e
= hdr_delete_de(&ib
->ihdr
, te
);
2195 indx_write(indx
, ni
, n
, 0);
2197 if (ib_is_leaf(ib
) && ib_is_empty(ib
)) {
2198 /* An empty leaf. */
2208 * indx_delete_entry - Delete an entry from the index.
2210 int indx_delete_entry(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
2211 const void *key
, u32 key_len
, const void *ctx
)
2214 struct INDEX_ROOT
*root
;
2215 struct INDEX_HDR
*hdr
;
2216 struct ntfs_fnd
*fnd
, *fnd2
;
2217 struct INDEX_BUFFER
*ib
;
2218 struct NTFS_DE
*e
, *re
, *next
, *prev
, *me
;
2219 struct indx_node
*n
, *n2d
= NULL
;
2222 struct ATTRIB
*attr
;
2223 struct mft_inode
*mi
;
2224 u32 e_size
, root_size
, new_root_size
;
2226 const struct INDEX_NAMES
*in
;
2240 root
= indx_get_root(indx
, ni
, &attr
, &mi
);
2246 /* Locate the entry to remove. */
2247 err
= indx_find(indx
, ni
, root
, key
, key_len
, ctx
, &diff
, &e
, fnd
);
2259 n
= fnd
->nodes
[level
- 1];
2260 e
= fnd
->de
[level
- 1];
2269 e_size
= le16_to_cpu(e
->size
);
2271 if (!de_has_vcn_ex(e
)) {
2272 /* The entry to delete is a leaf, so we can just rip it out. */
2273 hdr_delete_de(hdr
, e
);
2276 hdr
->total
= hdr
->used
;
2278 /* Shrink resident root attribute. */
2279 mi_resize_attr(mi
, attr
, 0 - e_size
);
2283 indx_write(indx
, ni
, n
, 0);
2286 * Check to see if removing that entry made
2289 if (ib_is_leaf(ib
) && ib_is_empty(ib
)) {
2291 fnd_push(fnd2
, n
, e
);
2295 * The entry we wish to delete is a node buffer, so we
2296 * have to find a replacement for it.
2298 next
= de_get_next(e
);
2300 err
= indx_get_entry_to_replace(indx
, ni
, next
, &re
, fnd2
);
2305 de_set_vbn_le(re
, de_get_vbn_le(e
));
2306 hdr_delete_de(hdr
, e
);
2308 err
= level
? indx_insert_into_buffer(indx
, ni
, root
,
2312 : indx_insert_into_root(indx
, ni
, re
, e
,
2320 * There is no replacement for the current entry.
2321 * This means that the subtree rooted at its node
2322 * is empty, and can be deleted, which turn means
2323 * that the node can just inherit the deleted
2326 indx_free_children(indx
, ni
, next
, true);
2328 de_set_vbn_le(next
, de_get_vbn_le(e
));
2329 hdr_delete_de(hdr
, e
);
2331 indx_write(indx
, ni
, n
, 0);
2333 hdr
->total
= hdr
->used
;
2335 /* Shrink resident root attribute. */
2336 mi_resize_attr(mi
, attr
, 0 - e_size
);
2341 /* Delete a branch of tree. */
2342 if (!fnd2
|| !fnd2
->level
)
2345 /* Reinit root 'cause it can be changed. */
2346 root
= indx_get_root(indx
, ni
, &attr
, &mi
);
2353 sub_vbn
= fnd2
->nodes
[0]->index
->vbn
;
2357 hdr
= level
? &fnd
->nodes
[level
- 1]->index
->ihdr
: &root
->ihdr
;
2359 /* Scan current level. */
2360 for (e
= hdr_first_de(hdr
);; e
= hdr_next_de(hdr
, e
)) {
2366 if (de_has_vcn(e
) && sub_vbn
== de_get_vbn_le(e
))
2369 if (de_is_last(e
)) {
2376 /* Do slow search from root. */
2377 struct indx_node
*in
;
2381 in
= indx_find_buffer(indx
, ni
, root
, sub_vbn
, NULL
);
2388 fnd_push(fnd
, in
, NULL
);
2391 /* Merge fnd2 -> fnd. */
2392 for (level
= 0; level
< fnd2
->level
; level
++) {
2393 fnd_push(fnd
, fnd2
->nodes
[level
], fnd2
->de
[level
]);
2394 fnd2
->nodes
[level
] = NULL
;
2399 for (level
= fnd
->level
; level
; level
--) {
2400 struct indx_node
*in
= fnd
->nodes
[level
- 1];
2403 if (ib_is_empty(ib
)) {
2416 e
= hdr_first_de(hdr
);
2422 if (hdr
!= &root
->ihdr
|| !de_is_last(e
)) {
2424 while (!de_is_last(e
)) {
2425 if (de_has_vcn(e
) && sub_vbn
== de_get_vbn_le(e
))
2428 e
= hdr_next_de(hdr
, e
);
2435 if (sub_vbn
!= de_get_vbn_le(e
)) {
2437 * Didn't find the parent entry, although this buffer
2438 * is the parent trail. Something is corrupt.
2444 if (de_is_last(e
)) {
2446 * Since we can't remove the end entry, we'll remove
2447 * its predecessor instead. This means we have to
2448 * transfer the predecessor's sub_vcn to the end entry.
2449 * Note: This index block is not empty, so the
2450 * predecessor must exist.
2457 if (de_has_vcn(prev
)) {
2458 de_set_vbn_le(e
, de_get_vbn_le(prev
));
2459 } else if (de_has_vcn(e
)) {
2460 le16_sub_cpu(&e
->size
, sizeof(u64
));
2461 e
->flags
&= ~NTFS_IE_HAS_SUBNODES
;
2462 le32_sub_cpu(&hdr
->used
, sizeof(u64
));
2468 * Copy the current entry into a temporary buffer (stripping
2469 * off its down-pointer, if any) and delete it from the current
2470 * buffer or root, as appropriate.
2472 e_size
= le16_to_cpu(e
->size
);
2473 me
= kmemdup(e
, e_size
, GFP_NOFS
);
2479 if (de_has_vcn(me
)) {
2480 me
->flags
&= ~NTFS_IE_HAS_SUBNODES
;
2481 le16_sub_cpu(&me
->size
, sizeof(u64
));
2484 hdr_delete_de(hdr
, e
);
2486 if (hdr
== &root
->ihdr
) {
2488 hdr
->total
= hdr
->used
;
2490 /* Shrink resident root attribute. */
2491 mi_resize_attr(mi
, attr
, 0 - e_size
);
2493 indx_write(indx
, ni
, n2d
, 0);
2497 /* Mark unused buffers as free. */
2499 for (; level
< fnd
->level
; level
++) {
2500 ib
= fnd
->nodes
[level
]->index
;
2501 if (ib_is_empty(ib
)) {
2502 size_t k
= le64_to_cpu(ib
->vbn
) >>
2505 indx_mark_free(indx
, ni
, k
);
2512 /*fnd->root_de = NULL;*/
2515 * Re-insert the entry into the tree.
2516 * Find the spot the tree where we want to insert the new entry.
2518 err
= indx_insert_entry(indx
, ni
, me
, ctx
, fnd
, 0);
2524 indx_shrink(indx
, ni
, trim_bit
);
2527 * This tree needs to be collapsed down to an empty root.
2528 * Recreate the index root as an empty leaf and free all
2529 * the bits the index allocation bitmap.
2534 in
= &s_index_names
[indx
->type
];
2536 err
= attr_set_size(ni
, ATTR_ALLOC
, in
->name
, in
->name_len
,
2537 &indx
->alloc_run
, 0, NULL
, false, NULL
);
2538 if (in
->name
== I30_NAME
)
2539 ni
->vfs_inode
.i_size
= 0;
2541 err
= ni_remove_attr(ni
, ATTR_ALLOC
, in
->name
, in
->name_len
,
2543 run_close(&indx
->alloc_run
);
2545 err
= attr_set_size(ni
, ATTR_BITMAP
, in
->name
, in
->name_len
,
2546 &indx
->bitmap_run
, 0, NULL
, false, NULL
);
2547 err
= ni_remove_attr(ni
, ATTR_BITMAP
, in
->name
, in
->name_len
,
2549 run_close(&indx
->bitmap_run
);
2551 root
= indx_get_root(indx
, ni
, &attr
, &mi
);
2557 root_size
= le32_to_cpu(attr
->res
.data_size
);
2559 sizeof(struct INDEX_ROOT
) + sizeof(struct NTFS_DE
);
2561 if (new_root_size
!= root_size
&&
2562 !mi_resize_attr(mi
, attr
, new_root_size
- root_size
)) {
2567 /* Fill first entry. */
2568 e
= (struct NTFS_DE
*)(root
+ 1);
2572 e
->size
= cpu_to_le16(sizeof(struct NTFS_DE
));
2573 e
->flags
= NTFS_IE_LAST
; // 0x02
2579 hdr
->used
= hdr
->total
= cpu_to_le32(
2580 new_root_size
- offsetof(struct INDEX_ROOT
, ihdr
));
2593 * Update duplicated information in directory entry
2594 * 'dup' - info from MFT record
2596 int indx_update_dup(struct ntfs_inode
*ni
, struct ntfs_sb_info
*sbi
,
2597 const struct ATTR_FILE_NAME
*fname
,
2598 const struct NTFS_DUP_INFO
*dup
, int sync
)
2601 struct NTFS_DE
*e
= NULL
;
2602 struct ATTR_FILE_NAME
*e_fname
;
2603 struct ntfs_fnd
*fnd
;
2604 struct INDEX_ROOT
*root
;
2605 struct mft_inode
*mi
;
2606 struct ntfs_index
*indx
= &ni
->dir
;
2612 root
= indx_get_root(indx
, ni
, NULL
, &mi
);
2618 /* Find entry in directory. */
2619 err
= indx_find(indx
, ni
, root
, fname
, fname_full_size(fname
), sbi
,
2634 e_fname
= (struct ATTR_FILE_NAME
*)(e
+ 1);
2636 if (!memcmp(&e_fname
->dup
, dup
, sizeof(*dup
))) {
2638 * Nothing to update in index! Try to avoid this call.
2643 memcpy(&e_fname
->dup
, dup
, sizeof(*dup
));
2646 /* Directory entry in index. */
2647 err
= indx_write(indx
, ni
, fnd
->nodes
[fnd
->level
- 1], sync
);
2649 /* Directory entry in directory MFT record. */
2652 err
= mi_write(mi
, 1);
2654 mark_inode_dirty(&ni
->vfs_inode
);