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(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(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(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(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(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(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
);
608 void fnd_clear(struct ntfs_fnd
*fnd
)
612 for (i
= 0; i
< fnd
->level
; i
++) {
613 struct indx_node
*n
= fnd
->nodes
[i
];
619 fnd
->nodes
[i
] = NULL
;
625 static int fnd_push(struct ntfs_fnd
*fnd
, struct indx_node
*n
,
631 if (i
< 0 || i
>= ARRAY_SIZE(fnd
->nodes
))
639 static struct indx_node
*fnd_pop(struct ntfs_fnd
*fnd
)
646 fnd
->nodes
[i
] = NULL
;
652 static bool fnd_is_empty(struct ntfs_fnd
*fnd
)
655 return !fnd
->root_de
;
657 return !fnd
->de
[fnd
->level
- 1];
661 * hdr_find_e - Locate an entry the index buffer.
663 * If no matching entry is found, it returns the first entry which is greater
664 * than the desired entry If the search key is greater than all the entries the
665 * buffer, it returns the 'end' entry. This function does a binary search of the
666 * current index buffer, for the first entry that is <= to the search value.
668 * Return: NULL if error.
670 static struct NTFS_DE
*hdr_find_e(const struct ntfs_index
*indx
,
671 const struct INDEX_HDR
*hdr
, const void *key
,
672 size_t key_len
, const void *ctx
, int *diff
)
674 struct NTFS_DE
*e
, *found
= NULL
;
675 NTFS_CMP_FUNC cmp
= indx
->cmp
;
676 int min_idx
= 0, mid_idx
, max_idx
= 0;
679 u32 e_size
, e_key_len
;
680 u32 end
= le32_to_cpu(hdr
->used
);
681 u32 off
= le32_to_cpu(hdr
->de_off
);
685 if (off
+ sizeof(struct NTFS_DE
) > end
)
688 e
= Add2Ptr(hdr
, off
);
689 e_size
= le16_to_cpu(e
->size
);
691 if (e_size
< sizeof(struct NTFS_DE
) || off
+ e_size
> end
)
694 if (!de_is_last(e
)) {
699 if (max_idx
< table_size
)
706 e_key_len
= le16_to_cpu(e
->key_size
);
708 diff2
= (*cmp
)(key
, key_len
, e
+ 1, e_key_len
, ctx
);
711 min_idx
= mid_idx
+ 1;
717 table_size
= min(table_size
* 2,
718 (int)ARRAY_SIZE(offs
));
721 } else if (diff2
< 0) {
723 max_idx
= mid_idx
- 1;
733 if (min_idx
> max_idx
) {
738 mid_idx
= (min_idx
+ max_idx
) >> 1;
739 e
= Add2Ptr(hdr
, offs
[mid_idx
]);
745 * hdr_insert_de - Insert an index entry into the buffer.
747 * 'before' should be a pointer previously returned from hdr_find_e.
749 static struct NTFS_DE
*hdr_insert_de(const struct ntfs_index
*indx
,
750 struct INDEX_HDR
*hdr
,
751 const struct NTFS_DE
*de
,
752 struct NTFS_DE
*before
, const void *ctx
)
755 size_t off
= PtrOffset(hdr
, before
);
756 u32 used
= le32_to_cpu(hdr
->used
);
757 u32 total
= le32_to_cpu(hdr
->total
);
758 u16 de_size
= le16_to_cpu(de
->size
);
760 /* First, check to see if there's enough room. */
761 if (used
+ de_size
> total
)
764 /* We know there's enough space, so we know we'll succeed. */
766 /* Check that before is inside Index. */
767 if (off
>= used
|| off
< le32_to_cpu(hdr
->de_off
) ||
768 off
+ le16_to_cpu(before
->size
) > total
) {
773 /* No insert point is applied. Get it manually. */
774 before
= hdr_find_e(indx
, hdr
, de
+ 1, le16_to_cpu(de
->key_size
), ctx
,
778 off
= PtrOffset(hdr
, before
);
781 /* Now we just make room for the entry and jam it in. */
782 memmove(Add2Ptr(before
, de_size
), before
, used
- off
);
784 hdr
->used
= cpu_to_le32(used
+ de_size
);
785 memcpy(before
, de
, de_size
);
791 * hdr_delete_de - Remove an entry from the index buffer.
793 static inline struct NTFS_DE
*hdr_delete_de(struct INDEX_HDR
*hdr
,
796 u32 used
= le32_to_cpu(hdr
->used
);
797 u16 esize
= le16_to_cpu(re
->size
);
798 u32 off
= PtrOffset(hdr
, re
);
799 int bytes
= used
- (off
+ esize
);
801 if (off
>= used
|| esize
< sizeof(struct NTFS_DE
) ||
802 bytes
< sizeof(struct NTFS_DE
))
805 hdr
->used
= cpu_to_le32(used
- esize
);
806 memmove(re
, Add2Ptr(re
, esize
), bytes
);
811 void indx_clear(struct ntfs_index
*indx
)
813 run_close(&indx
->alloc_run
);
814 run_close(&indx
->bitmap_run
);
817 int indx_init(struct ntfs_index
*indx
, struct ntfs_sb_info
*sbi
,
818 const struct ATTRIB
*attr
, enum index_mutex_classed type
)
821 const struct INDEX_ROOT
*root
= resident_data(attr
);
823 /* Check root fields. */
824 if (!root
->index_block_clst
)
828 indx
->idx2vbn_bits
= __ffs(root
->index_block_clst
);
830 t32
= le32_to_cpu(root
->index_block_size
);
831 indx
->index_bits
= blksize_bits(t32
);
833 /* Check index record size. */
834 if (t32
< sbi
->cluster_size
) {
835 /* Index record is smaller than a cluster, use 512 blocks. */
836 if (t32
!= root
->index_block_clst
* SECTOR_SIZE
)
839 /* Check alignment to a cluster. */
840 if ((sbi
->cluster_size
>> SECTOR_SHIFT
) &
841 (root
->index_block_clst
- 1)) {
845 indx
->vbn2vbo_bits
= SECTOR_SHIFT
;
847 /* Index record must be a multiple of cluster size. */
848 if (t32
!= root
->index_block_clst
<< sbi
->cluster_bits
)
851 indx
->vbn2vbo_bits
= sbi
->cluster_bits
;
854 init_rwsem(&indx
->run_lock
);
856 indx
->cmp
= get_cmp_func(root
);
857 return indx
->cmp
? 0 : -EINVAL
;
860 static struct indx_node
*indx_new(struct ntfs_index
*indx
,
861 struct ntfs_inode
*ni
, CLST vbn
,
862 const __le64
*sub_vbn
)
867 struct INDEX_HDR
*hdr
;
868 struct INDEX_BUFFER
*index
;
869 u64 vbo
= (u64
)vbn
<< indx
->vbn2vbo_bits
;
870 u32 bytes
= 1u << indx
->index_bits
;
874 r
= kzalloc(sizeof(struct indx_node
), GFP_NOFS
);
876 return ERR_PTR(-ENOMEM
);
878 index
= kzalloc(bytes
, GFP_NOFS
);
881 return ERR_PTR(-ENOMEM
);
884 err
= ntfs_get_bh(ni
->mi
.sbi
, &indx
->alloc_run
, vbo
, bytes
, &r
->nb
);
893 index
->rhdr
.sign
= NTFS_INDX_SIGNATURE
;
894 index
->rhdr
.fix_off
= cpu_to_le16(sizeof(struct INDEX_BUFFER
)); // 0x28
895 fn
= (bytes
>> SECTOR_SHIFT
) + 1; // 9
896 index
->rhdr
.fix_num
= cpu_to_le16(fn
);
897 index
->vbn
= cpu_to_le64(vbn
);
899 eo
= ALIGN(sizeof(struct INDEX_BUFFER
) + fn
* sizeof(short), 8);
900 hdr
->de_off
= cpu_to_le32(eo
);
902 e
= Add2Ptr(hdr
, eo
);
905 e
->flags
= NTFS_IE_LAST
| NTFS_IE_HAS_SUBNODES
;
906 e
->size
= cpu_to_le16(sizeof(struct NTFS_DE
) + sizeof(u64
));
908 cpu_to_le32(eo
+ sizeof(struct NTFS_DE
) + sizeof(u64
));
909 de_set_vbn_le(e
, *sub_vbn
);
912 e
->size
= cpu_to_le16(sizeof(struct NTFS_DE
));
913 hdr
->used
= cpu_to_le32(eo
+ sizeof(struct NTFS_DE
));
914 e
->flags
= NTFS_IE_LAST
;
917 hdr
->total
= cpu_to_le32(bytes
- offsetof(struct INDEX_BUFFER
, ihdr
));
923 struct INDEX_ROOT
*indx_get_root(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
924 struct ATTRIB
**attr
, struct mft_inode
**mi
)
926 struct ATTR_LIST_ENTRY
*le
= NULL
;
928 const struct INDEX_NAMES
*in
= &s_index_names
[indx
->type
];
930 a
= ni_find_attr(ni
, NULL
, &le
, ATTR_ROOT
, in
->name
, in
->name_len
, NULL
,
938 return resident_data_ex(a
, sizeof(struct INDEX_ROOT
));
941 static int indx_write(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
942 struct indx_node
*node
, int sync
)
944 struct INDEX_BUFFER
*ib
= node
->index
;
946 return ntfs_write_bh(ni
->mi
.sbi
, &ib
->rhdr
, &node
->nb
, sync
);
952 * If ntfs_readdir calls this function
953 * inode is shared locked and no ni_lock.
954 * Use rw_semaphore for read/write access to alloc_run.
956 int indx_read(struct ntfs_index
*indx
, struct ntfs_inode
*ni
, CLST vbn
,
957 struct indx_node
**node
)
960 struct INDEX_BUFFER
*ib
;
961 struct runs_tree
*run
= &indx
->alloc_run
;
962 struct rw_semaphore
*lock
= &indx
->run_lock
;
963 u64 vbo
= (u64
)vbn
<< indx
->vbn2vbo_bits
;
964 u32 bytes
= 1u << indx
->index_bits
;
965 struct indx_node
*in
= *node
;
966 const struct INDEX_NAMES
*name
;
969 in
= kzalloc(sizeof(struct indx_node
), GFP_NOFS
);
978 ib
= kmalloc(bytes
, GFP_NOFS
);
986 err
= ntfs_read_bh(ni
->mi
.sbi
, run
, vbo
, &ib
->rhdr
, bytes
, &in
->nb
);
991 if (err
== -E_NTFS_FIXUP
)
997 name
= &s_index_names
[indx
->type
];
999 err
= attr_load_runs_range(ni
, ATTR_ALLOC
, name
->name
, name
->name_len
,
1000 run
, vbo
, vbo
+ bytes
);
1006 err
= ntfs_read_bh(ni
->mi
.sbi
, run
, vbo
, &ib
->rhdr
, bytes
, &in
->nb
);
1008 if (err
== -E_NTFS_FIXUP
)
1015 if (err
== -E_NTFS_FIXUP
) {
1016 ntfs_write_bh(ni
->mi
.sbi
, &ib
->rhdr
, &in
->nb
, 0);
1024 if (ib
!= in
->index
)
1036 * indx_find - Scan NTFS directory for given entry.
1038 int indx_find(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1039 const struct INDEX_ROOT
*root
, const void *key
, size_t key_len
,
1040 const void *ctx
, int *diff
, struct NTFS_DE
**entry
,
1041 struct ntfs_fnd
*fnd
)
1045 struct indx_node
*node
;
1048 root
= indx_get_root(&ni
->dir
, ni
, NULL
, NULL
);
1051 /* Should not happen. */
1056 e
= fnd
->level
? fnd
->de
[fnd
->level
- 1] : fnd
->root_de
;
1057 if (e
&& !de_is_last(e
) &&
1058 !(*indx
->cmp
)(key
, key_len
, e
+ 1, le16_to_cpu(e
->key_size
), ctx
)) {
1064 /* Soft finder reset. */
1067 /* Lookup entry that is <= to the search value. */
1068 e
= hdr_find_e(indx
, &root
->ihdr
, key
, key_len
, ctx
, diff
);
1076 if (*diff
>= 0 || !de_has_vcn_ex(e
))
1079 /* Read next level. */
1080 err
= indx_read(indx
, ni
, de_get_vbn(e
), &node
);
1084 /* Lookup entry that is <= to the search value. */
1085 e
= hdr_find_e(indx
, &node
->index
->ihdr
, key
, key_len
, ctx
,
1088 put_indx_node(node
);
1092 fnd_push(fnd
, node
, e
);
1099 int indx_find_sort(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1100 const struct INDEX_ROOT
*root
, struct NTFS_DE
**entry
,
1101 struct ntfs_fnd
*fnd
)
1104 struct indx_node
*n
= NULL
;
1107 int level
= fnd
->level
;
1111 e
= hdr_first_de(&root
->ihdr
);
1116 } else if (!level
) {
1117 if (de_is_last(fnd
->root_de
)) {
1122 e
= hdr_next_de(&root
->ihdr
, fnd
->root_de
);
1127 n
= fnd
->nodes
[level
- 1];
1128 e
= fnd
->de
[level
- 1];
1133 e
= hdr_next_de(&n
->index
->ihdr
, e
);
1137 fnd
->de
[level
- 1] = e
;
1140 /* Just to avoid tree cycle. */
1145 while (de_has_vcn_ex(e
)) {
1146 if (le16_to_cpu(e
->size
) <
1147 sizeof(struct NTFS_DE
) + sizeof(u64
)) {
1155 /* Read next level. */
1156 err
= indx_read(indx
, ni
, de_get_vbn(e
), &n
);
1160 /* Try next level. */
1161 e
= hdr_first_de(&n
->index
->ihdr
);
1167 fnd_push(fnd
, n
, e
);
1170 if (le16_to_cpu(e
->size
) > sizeof(struct NTFS_DE
)) {
1180 /* Pop one level. */
1189 n
= fnd
->nodes
[level
- 1];
1190 e
= fnd
->de
[level
- 1];
1191 } else if (fnd
->root_de
) {
1194 fnd
->root_de
= NULL
;
1200 if (le16_to_cpu(e
->size
) > sizeof(struct NTFS_DE
)) {
1209 int indx_find_raw(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1210 const struct INDEX_ROOT
*root
, struct NTFS_DE
**entry
,
1211 size_t *off
, struct ntfs_fnd
*fnd
)
1214 struct indx_node
*n
= NULL
;
1215 struct NTFS_DE
*e
= NULL
;
1220 u32 record_size
= ni
->mi
.sbi
->record_size
;
1222 /* Use non sorted algorithm. */
1224 /* This is the first call. */
1225 e
= hdr_first_de(&root
->ihdr
);
1231 /* The first call with setup of initial element. */
1232 if (*off
>= record_size
) {
1233 next_vbn
= (((*off
- record_size
) >> indx
->index_bits
))
1234 << indx
->idx2vbn_bits
;
1235 /* Jump inside cycle 'for'. */
1239 /* Start enumeration from root. */
1241 } else if (!fnd
->root_de
)
1245 /* Check if current entry can be used. */
1246 if (e
&& le16_to_cpu(e
->size
) > sizeof(struct NTFS_DE
))
1250 /* Continue to enumerate root. */
1251 if (!de_is_last(fnd
->root_de
)) {
1252 e
= hdr_next_de(&root
->ihdr
, fnd
->root_de
);
1259 /* Start to enumerate indexes from 0. */
1262 /* Continue to enumerate indexes. */
1263 e2
= fnd
->de
[fnd
->level
- 1];
1265 n
= fnd
->nodes
[fnd
->level
- 1];
1267 if (!de_is_last(e2
)) {
1268 e
= hdr_next_de(&n
->index
->ihdr
, e2
);
1271 fnd
->de
[fnd
->level
- 1] = e
;
1275 /* Continue with next index. */
1276 next_vbn
= le64_to_cpu(n
->index
->vbn
) +
1277 root
->index_block_clst
;
1281 /* Release current index. */
1288 /* Skip all free indexes. */
1289 bit
= next_vbn
>> indx
->idx2vbn_bits
;
1290 err
= indx_used_bit(indx
, ni
, &bit
);
1291 if (err
== -ENOENT
|| bit
== MINUS_ONE_T
) {
1292 /* No used indexes. */
1297 next_used_vbn
= bit
<< indx
->idx2vbn_bits
;
1299 /* Read buffer into memory. */
1300 err
= indx_read(indx
, ni
, next_used_vbn
, &n
);
1304 e
= hdr_first_de(&n
->index
->ihdr
);
1305 fnd_push(fnd
, n
, e
);
1311 /* Return offset to restore enumerator if necessary. */
1313 /* 'e' points in root, */
1314 *off
= PtrOffset(&root
->ihdr
, e
);
1316 /* 'e' points in index, */
1317 *off
= (le64_to_cpu(n
->index
->vbn
) << indx
->vbn2vbo_bits
) +
1318 record_size
+ PtrOffset(&n
->index
->ihdr
, e
);
1326 * indx_create_allocate - Create "Allocation + Bitmap" attributes.
1328 static int indx_create_allocate(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1332 struct ntfs_sb_info
*sbi
= ni
->mi
.sbi
;
1333 struct ATTRIB
*bitmap
;
1334 struct ATTRIB
*alloc
;
1335 u32 data_size
= 1u << indx
->index_bits
;
1336 u32 alloc_size
= ntfs_up_cluster(sbi
, data_size
);
1337 CLST len
= alloc_size
>> sbi
->cluster_bits
;
1338 const struct INDEX_NAMES
*in
= &s_index_names
[indx
->type
];
1340 struct runs_tree run
;
1344 err
= attr_allocate_clusters(sbi
, &run
, 0, 0, len
, NULL
, 0, &alen
, 0,
1349 err
= ni_insert_nonresident(ni
, ATTR_ALLOC
, in
->name
, in
->name_len
,
1350 &run
, 0, len
, 0, &alloc
, NULL
, NULL
);
1354 alloc
->nres
.valid_size
= alloc
->nres
.data_size
= cpu_to_le64(data_size
);
1356 err
= ni_insert_resident(ni
, bitmap_size(1), ATTR_BITMAP
, in
->name
,
1357 in
->name_len
, &bitmap
, NULL
, NULL
);
1361 if (in
->name
== I30_NAME
) {
1362 ni
->vfs_inode
.i_size
= data_size
;
1363 inode_set_bytes(&ni
->vfs_inode
, alloc_size
);
1366 memcpy(&indx
->alloc_run
, &run
, sizeof(run
));
1373 mi_remove_attr(NULL
, &ni
->mi
, alloc
);
1376 run_deallocate(sbi
, &run
, false);
1383 * indx_add_allocate - Add clusters to index.
1385 static int indx_add_allocate(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1391 u64 bmp_size
, bmp_size_v
;
1392 struct ATTRIB
*bmp
, *alloc
;
1393 struct mft_inode
*mi
;
1394 const struct INDEX_NAMES
*in
= &s_index_names
[indx
->type
];
1396 err
= indx_find_free(indx
, ni
, &bit
, &bmp
);
1400 if (bit
!= MINUS_ONE_T
) {
1404 bmp_size
= le64_to_cpu(bmp
->nres
.data_size
);
1405 bmp_size_v
= le64_to_cpu(bmp
->nres
.valid_size
);
1407 bmp_size
= bmp_size_v
= le32_to_cpu(bmp
->res
.data_size
);
1410 bit
= bmp_size
<< 3;
1413 data_size
= (u64
)(bit
+ 1) << indx
->index_bits
;
1416 /* Increase bitmap. */
1417 err
= attr_set_size(ni
, ATTR_BITMAP
, in
->name
, in
->name_len
,
1418 &indx
->bitmap_run
, bitmap_size(bit
+ 1),
1424 alloc
= ni_find_attr(ni
, NULL
, NULL
, ATTR_ALLOC
, in
->name
, in
->name_len
,
1433 /* Increase allocation. */
1434 err
= attr_set_size(ni
, ATTR_ALLOC
, in
->name
, in
->name_len
,
1435 &indx
->alloc_run
, data_size
, &data_size
, true,
1443 *vbn
= bit
<< indx
->idx2vbn_bits
;
1448 /* Ops. No space? */
1449 attr_set_size(ni
, ATTR_BITMAP
, in
->name
, in
->name_len
,
1450 &indx
->bitmap_run
, bmp_size
, &bmp_size_v
, false, NULL
);
1457 * indx_insert_into_root - Attempt to insert an entry into the index root.
1459 * @undo - True if we undoing previous remove.
1460 * If necessary, it will twiddle the index b-tree.
1462 static int indx_insert_into_root(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1463 const struct NTFS_DE
*new_de
,
1464 struct NTFS_DE
*root_de
, const void *ctx
,
1465 struct ntfs_fnd
*fnd
, bool undo
)
1468 struct NTFS_DE
*e
, *e0
, *re
;
1469 struct mft_inode
*mi
;
1470 struct ATTRIB
*attr
;
1471 struct INDEX_HDR
*hdr
;
1472 struct indx_node
*n
;
1474 __le64
*sub_vbn
, t_vbn
;
1476 u32 hdr_used
, hdr_total
, asize
, to_move
;
1477 u32 root_size
, new_root_size
;
1478 struct ntfs_sb_info
*sbi
;
1480 struct INDEX_ROOT
*root
, *a_root
;
1482 /* Get the record this root placed in. */
1483 root
= indx_get_root(indx
, ni
, &attr
, &mi
);
1489 * hdr_insert_de will succeed if there's
1490 * room the root for the new entry.
1494 new_de_size
= le16_to_cpu(new_de
->size
);
1495 hdr_used
= le32_to_cpu(hdr
->used
);
1496 hdr_total
= le32_to_cpu(hdr
->total
);
1497 asize
= le32_to_cpu(attr
->size
);
1498 root_size
= le32_to_cpu(attr
->res
.data_size
);
1500 ds_root
= new_de_size
+ hdr_used
- hdr_total
;
1502 /* If 'undo' is set then reduce requirements. */
1503 if ((undo
|| asize
+ ds_root
< sbi
->max_bytes_per_attr
) &&
1504 mi_resize_attr(mi
, attr
, ds_root
)) {
1505 hdr
->total
= cpu_to_le32(hdr_total
+ ds_root
);
1506 e
= hdr_insert_de(indx
, hdr
, new_de
, root_de
, ctx
);
1514 /* Make a copy of root attribute to restore if error. */
1515 a_root
= kmemdup(attr
, asize
, GFP_NOFS
);
1520 * Copy all the non-end entries from
1521 * the index root to the new buffer.
1524 e0
= hdr_first_de(hdr
);
1526 /* Calculate the size to copy. */
1527 for (e
= e0
;; e
= hdr_next_de(hdr
, e
)) {
1535 to_move
+= le16_to_cpu(e
->size
);
1541 re
= kmemdup(e0
, to_move
, GFP_NOFS
);
1549 if (de_has_vcn(e
)) {
1550 t_vbn
= de_get_vbn_le(e
);
1554 new_root_size
= sizeof(struct INDEX_ROOT
) + sizeof(struct NTFS_DE
) +
1556 ds_root
= new_root_size
- root_size
;
1558 if (ds_root
> 0 && asize
+ ds_root
> sbi
->max_bytes_per_attr
) {
1559 /* Make root external. */
1565 mi_resize_attr(mi
, attr
, ds_root
);
1567 /* Fill first entry (vcn will be set later). */
1568 e
= (struct NTFS_DE
*)(root
+ 1);
1569 memset(e
, 0, sizeof(struct NTFS_DE
));
1570 e
->size
= cpu_to_le16(sizeof(struct NTFS_DE
) + sizeof(u64
));
1571 e
->flags
= NTFS_IE_HAS_SUBNODES
| NTFS_IE_LAST
;
1574 hdr
->used
= hdr
->total
=
1575 cpu_to_le32(new_root_size
- offsetof(struct INDEX_ROOT
, ihdr
));
1577 fnd
->root_de
= hdr_first_de(hdr
);
1580 /* Create alloc and bitmap attributes (if not). */
1581 err
= run_is_empty(&indx
->alloc_run
)
1582 ? indx_create_allocate(indx
, ni
, &new_vbn
)
1583 : indx_add_allocate(indx
, ni
, &new_vbn
);
1585 /* Layout of record may be changed, so rescan root. */
1586 root
= indx_get_root(indx
, ni
, &attr
, &mi
);
1589 ntfs_set_state(sbi
, NTFS_DIRTY_ERROR
);
1596 if (mi_resize_attr(mi
, attr
, -ds_root
))
1597 memcpy(attr
, a_root
, asize
);
1600 ntfs_set_state(sbi
, NTFS_DIRTY_ERROR
);
1605 e
= (struct NTFS_DE
*)(root
+ 1);
1606 *(__le64
*)(e
+ 1) = cpu_to_le64(new_vbn
);
1609 /* Now we can create/format the new buffer and copy the entries into. */
1610 n
= indx_new(indx
, ni
, new_vbn
, sub_vbn
);
1616 hdr
= &n
->index
->ihdr
;
1617 hdr_used
= le32_to_cpu(hdr
->used
);
1618 hdr_total
= le32_to_cpu(hdr
->total
);
1620 /* Copy root entries into new buffer. */
1621 hdr_insert_head(hdr
, re
, to_move
);
1623 /* Update bitmap attribute. */
1624 indx_mark_used(indx
, ni
, new_vbn
>> indx
->idx2vbn_bits
);
1626 /* Check if we can insert new entry new index buffer. */
1627 if (hdr_used
+ new_de_size
> hdr_total
) {
1629 * This occurs if MFT record is the same or bigger than index
1630 * buffer. Move all root new index and have no space to add
1631 * new entry classic case when MFT record is 1K and index
1632 * buffer 4K the problem should not occurs.
1635 indx_write(indx
, ni
, n
, 0);
1639 err
= indx_insert_entry(indx
, ni
, new_de
, ctx
, fnd
, undo
);
1644 * Now root is a parent for new index buffer.
1645 * Insert NewEntry a new buffer.
1647 e
= hdr_insert_de(indx
, hdr
, new_de
, NULL
, ctx
);
1652 fnd_push(fnd
, n
, e
);
1654 /* Just write updates index into disk. */
1655 indx_write(indx
, ni
, n
, 0);
1669 * indx_insert_into_buffer
1671 * Attempt to insert an entry into an Index Allocation Buffer.
1672 * If necessary, it will split the buffer.
1675 indx_insert_into_buffer(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1676 struct INDEX_ROOT
*root
, const struct NTFS_DE
*new_de
,
1677 const void *ctx
, int level
, struct ntfs_fnd
*fnd
)
1680 const struct NTFS_DE
*sp
;
1681 struct NTFS_DE
*e
, *de_t
, *up_e
;
1682 struct indx_node
*n2
;
1683 struct indx_node
*n1
= fnd
->nodes
[level
];
1684 struct INDEX_HDR
*hdr1
= &n1
->index
->ihdr
;
1685 struct INDEX_HDR
*hdr2
;
1688 __le64 t_vbn
, *sub_vbn
;
1691 /* Try the most easy case. */
1692 e
= fnd
->level
- 1 == level
? fnd
->de
[level
] : NULL
;
1693 e
= hdr_insert_de(indx
, hdr1
, new_de
, e
, ctx
);
1696 /* Just write updated index into disk. */
1697 indx_write(indx
, ni
, n1
, 0);
1702 * No space to insert into buffer. Split it.
1704 * - Save split point ('cause index buffers will be changed)
1705 * - Allocate NewBuffer and copy all entries <= sp into new buffer
1706 * - Remove all entries (sp including) from TargetBuffer
1707 * - Insert NewEntry into left or right buffer (depending on sp <=>
1709 * - Insert sp into parent buffer (or root)
1710 * - Make sp a parent for new buffer
1712 sp
= hdr_find_split(hdr1
);
1716 sp_size
= le16_to_cpu(sp
->size
);
1717 up_e
= kmalloc(sp_size
+ sizeof(u64
), GFP_NOFS
);
1720 memcpy(up_e
, sp
, sp_size
);
1723 up_e
->flags
|= NTFS_IE_HAS_SUBNODES
;
1724 up_e
->size
= cpu_to_le16(sp_size
+ sizeof(u64
));
1727 t_vbn
= de_get_vbn_le(up_e
);
1731 /* Allocate on disk a new index allocation buffer. */
1732 err
= indx_add_allocate(indx
, ni
, &new_vbn
);
1736 /* Allocate and format memory a new index buffer. */
1737 n2
= indx_new(indx
, ni
, new_vbn
, sub_vbn
);
1743 hdr2
= &n2
->index
->ihdr
;
1745 /* Make sp a parent for new buffer. */
1746 de_set_vbn(up_e
, new_vbn
);
1748 /* Copy all the entries <= sp into the new buffer. */
1749 de_t
= hdr_first_de(hdr1
);
1750 to_copy
= PtrOffset(de_t
, sp
);
1751 hdr_insert_head(hdr2
, de_t
, to_copy
);
1753 /* Remove all entries (sp including) from hdr1. */
1754 used
= le32_to_cpu(hdr1
->used
) - to_copy
- sp_size
;
1755 memmove(de_t
, Add2Ptr(sp
, sp_size
), used
- le32_to_cpu(hdr1
->de_off
));
1756 hdr1
->used
= cpu_to_le32(used
);
1759 * Insert new entry into left or right buffer
1760 * (depending on sp <=> new_de).
1763 (*indx
->cmp
)(new_de
+ 1, le16_to_cpu(new_de
->key_size
),
1764 up_e
+ 1, le16_to_cpu(up_e
->key_size
),
1770 indx_mark_used(indx
, ni
, new_vbn
>> indx
->idx2vbn_bits
);
1772 indx_write(indx
, ni
, n1
, 0);
1773 indx_write(indx
, ni
, n2
, 0);
1778 * We've finished splitting everybody, so we are ready to
1779 * insert the promoted entry into the parent.
1782 /* Insert in root. */
1783 err
= indx_insert_into_root(indx
, ni
, up_e
, NULL
, ctx
, fnd
, 0);
1788 * The target buffer's parent is another index buffer.
1789 * TODO: Remove recursion.
1791 err
= indx_insert_into_buffer(indx
, ni
, root
, up_e
, ctx
,
1804 * indx_insert_entry - Insert new entry into index.
1806 * @undo - True if we undoing previous remove.
1808 int indx_insert_entry(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1809 const struct NTFS_DE
*new_de
, const void *ctx
,
1810 struct ntfs_fnd
*fnd
, bool undo
)
1815 struct ntfs_fnd
*fnd_a
= NULL
;
1816 struct INDEX_ROOT
*root
;
1827 root
= indx_get_root(indx
, ni
, NULL
, NULL
);
1833 if (fnd_is_empty(fnd
)) {
1835 * Find the spot the tree where we want to
1836 * insert the new entry.
1838 err
= indx_find(indx
, ni
, root
, new_de
+ 1,
1839 le16_to_cpu(new_de
->key_size
), ctx
, &diff
, &e
,
1852 * The root is also a leaf, so we'll insert the
1853 * new entry into it.
1855 err
= indx_insert_into_root(indx
, ni
, new_de
, fnd
->root_de
, ctx
,
1861 * Found a leaf buffer, so we'll insert the new entry into it.
1863 err
= indx_insert_into_buffer(indx
, ni
, root
, new_de
, ctx
,
1864 fnd
->level
- 1, fnd
);
1876 * indx_find_buffer - Locate a buffer from the tree.
1878 static struct indx_node
*indx_find_buffer(struct ntfs_index
*indx
,
1879 struct ntfs_inode
*ni
,
1880 const struct INDEX_ROOT
*root
,
1881 __le64 vbn
, struct indx_node
*n
)
1884 const struct NTFS_DE
*e
;
1885 struct indx_node
*r
;
1886 const struct INDEX_HDR
*hdr
= n
? &n
->index
->ihdr
: &root
->ihdr
;
1888 /* Step 1: Scan one level. */
1889 for (e
= hdr_first_de(hdr
);; e
= hdr_next_de(hdr
, e
)) {
1891 return ERR_PTR(-EINVAL
);
1893 if (de_has_vcn(e
) && vbn
== de_get_vbn_le(e
))
1900 /* Step2: Do recursion. */
1901 e
= Add2Ptr(hdr
, le32_to_cpu(hdr
->de_off
));
1903 if (de_has_vcn_ex(e
)) {
1904 err
= indx_read(indx
, ni
, de_get_vbn(e
), &n
);
1906 return ERR_PTR(err
);
1908 r
= indx_find_buffer(indx
, ni
, root
, vbn
, n
);
1916 e
= Add2Ptr(e
, le16_to_cpu(e
->size
));
1923 * indx_shrink - Deallocate unused tail indexes.
1925 static int indx_shrink(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1932 struct ATTR_LIST_ENTRY
*le
= NULL
;
1933 const struct INDEX_NAMES
*in
= &s_index_names
[indx
->type
];
1935 b
= ni_find_attr(ni
, NULL
, &le
, ATTR_BITMAP
, in
->name
, in
->name_len
,
1943 const unsigned long *bm
= resident_data(b
);
1945 nbits
= (size_t)le32_to_cpu(b
->res
.data_size
) * 8;
1950 pos
= find_next_bit(bm
, nbits
, bit
);
1954 size_t used
= MINUS_ONE_T
;
1956 nbits
= le64_to_cpu(b
->nres
.data_size
) * 8;
1961 err
= scan_nres_bitmap(ni
, b
, indx
, bit
, &scan_for_used
, &used
);
1965 if (used
!= MINUS_ONE_T
)
1969 new_data
= (u64
)bit
<< indx
->index_bits
;
1971 err
= attr_set_size(ni
, ATTR_ALLOC
, in
->name
, in
->name_len
,
1972 &indx
->alloc_run
, new_data
, &new_data
, false, NULL
);
1976 bpb
= bitmap_size(bit
);
1977 if (bpb
* 8 == nbits
)
1980 err
= attr_set_size(ni
, ATTR_BITMAP
, in
->name
, in
->name_len
,
1981 &indx
->bitmap_run
, bpb
, &bpb
, false, NULL
);
1986 static int indx_free_children(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
1987 const struct NTFS_DE
*e
, bool trim
)
1990 struct indx_node
*n
= NULL
;
1991 struct INDEX_HDR
*hdr
;
1992 CLST vbn
= de_get_vbn(e
);
1995 err
= indx_read(indx
, ni
, vbn
, &n
);
1999 hdr
= &n
->index
->ihdr
;
2000 /* First, recurse into the children, if any. */
2001 if (hdr_has_subnode(hdr
)) {
2002 for (e
= hdr_first_de(hdr
); e
; e
= hdr_next_de(hdr
, e
)) {
2003 indx_free_children(indx
, ni
, e
, false);
2011 i
= vbn
>> indx
->idx2vbn_bits
;
2013 * We've gotten rid of the children; add this buffer to the free list.
2015 indx_mark_free(indx
, ni
, i
);
2021 * If there are no used indexes after current free index
2022 * then we can truncate allocation and bitmap.
2023 * Use bitmap to estimate the case.
2025 indx_shrink(indx
, ni
, i
+ 1);
2030 * indx_get_entry_to_replace
2032 * Find a replacement entry for a deleted entry.
2033 * Always returns a node entry:
2034 * NTFS_IE_HAS_SUBNODES is set the flags and the size includes the sub_vcn.
2036 static int indx_get_entry_to_replace(struct ntfs_index
*indx
,
2037 struct ntfs_inode
*ni
,
2038 const struct NTFS_DE
*de_next
,
2039 struct NTFS_DE
**de_to_replace
,
2040 struct ntfs_fnd
*fnd
)
2045 struct NTFS_DE
*e
, *te
, *re
;
2046 struct indx_node
*n
;
2047 struct INDEX_BUFFER
*ib
;
2049 *de_to_replace
= NULL
;
2051 /* Find first leaf entry down from de_next. */
2052 vbn
= de_get_vbn(de_next
);
2055 err
= indx_read(indx
, ni
, vbn
, &n
);
2059 e
= hdr_first_de(&n
->index
->ihdr
);
2060 fnd_push(fnd
, n
, e
);
2062 if (!de_is_last(e
)) {
2064 * This buffer is non-empty, so its first entry
2065 * could be used as the replacement entry.
2067 level
= fnd
->level
- 1;
2073 /* This buffer is a node. Continue to go down. */
2074 vbn
= de_get_vbn(e
);
2080 n
= fnd
->nodes
[level
];
2081 te
= hdr_first_de(&n
->index
->ihdr
);
2082 /* Copy the candidate entry into the replacement entry buffer. */
2083 re
= kmalloc(le16_to_cpu(te
->size
) + sizeof(u64
), GFP_NOFS
);
2089 *de_to_replace
= re
;
2090 memcpy(re
, te
, le16_to_cpu(te
->size
));
2092 if (!de_has_vcn(re
)) {
2094 * The replacement entry we found doesn't have a sub_vcn.
2095 * increase its size to hold one.
2097 le16_add_cpu(&re
->size
, sizeof(u64
));
2098 re
->flags
|= NTFS_IE_HAS_SUBNODES
;
2101 * The replacement entry we found was a node entry, which
2102 * means that all its child buffers are empty. Return them
2105 indx_free_children(indx
, ni
, te
, true);
2109 * Expunge the replacement entry from its former location,
2110 * and then write that buffer.
2113 e
= hdr_delete_de(&ib
->ihdr
, te
);
2116 indx_write(indx
, ni
, n
, 0);
2118 /* Check to see if this action created an empty leaf. */
2119 if (ib_is_leaf(ib
) && ib_is_empty(ib
))
2128 * indx_delete_entry - Delete an entry from the index.
2130 int indx_delete_entry(struct ntfs_index
*indx
, struct ntfs_inode
*ni
,
2131 const void *key
, u32 key_len
, const void *ctx
)
2134 struct INDEX_ROOT
*root
;
2135 struct INDEX_HDR
*hdr
;
2136 struct ntfs_fnd
*fnd
, *fnd2
;
2137 struct INDEX_BUFFER
*ib
;
2138 struct NTFS_DE
*e
, *re
, *next
, *prev
, *me
;
2139 struct indx_node
*n
, *n2d
= NULL
;
2142 struct ATTRIB
*attr
;
2143 struct mft_inode
*mi
;
2144 u32 e_size
, root_size
, new_root_size
;
2146 const struct INDEX_NAMES
*in
;
2160 root
= indx_get_root(indx
, ni
, &attr
, &mi
);
2166 /* Locate the entry to remove. */
2167 err
= indx_find(indx
, ni
, root
, key
, key_len
, ctx
, &diff
, &e
, fnd
);
2179 n
= fnd
->nodes
[level
- 1];
2180 e
= fnd
->de
[level
- 1];
2189 e_size
= le16_to_cpu(e
->size
);
2191 if (!de_has_vcn_ex(e
)) {
2192 /* The entry to delete is a leaf, so we can just rip it out. */
2193 hdr_delete_de(hdr
, e
);
2196 hdr
->total
= hdr
->used
;
2198 /* Shrink resident root attribute. */
2199 mi_resize_attr(mi
, attr
, 0 - e_size
);
2203 indx_write(indx
, ni
, n
, 0);
2206 * Check to see if removing that entry made
2209 if (ib_is_leaf(ib
) && ib_is_empty(ib
)) {
2211 fnd_push(fnd2
, n
, e
);
2215 * The entry we wish to delete is a node buffer, so we
2216 * have to find a replacement for it.
2218 next
= de_get_next(e
);
2220 err
= indx_get_entry_to_replace(indx
, ni
, next
, &re
, fnd2
);
2225 de_set_vbn_le(re
, de_get_vbn_le(e
));
2226 hdr_delete_de(hdr
, e
);
2228 err
= level
? indx_insert_into_buffer(indx
, ni
, root
,
2232 : indx_insert_into_root(indx
, ni
, re
, e
,
2240 * There is no replacement for the current entry.
2241 * This means that the subtree rooted at its node
2242 * is empty, and can be deleted, which turn means
2243 * that the node can just inherit the deleted
2246 indx_free_children(indx
, ni
, next
, true);
2248 de_set_vbn_le(next
, de_get_vbn_le(e
));
2249 hdr_delete_de(hdr
, e
);
2251 indx_write(indx
, ni
, n
, 0);
2253 hdr
->total
= hdr
->used
;
2255 /* Shrink resident root attribute. */
2256 mi_resize_attr(mi
, attr
, 0 - e_size
);
2261 /* Delete a branch of tree. */
2262 if (!fnd2
|| !fnd2
->level
)
2265 /* Reinit root 'cause it can be changed. */
2266 root
= indx_get_root(indx
, ni
, &attr
, &mi
);
2273 sub_vbn
= fnd2
->nodes
[0]->index
->vbn
;
2277 hdr
= level
? &fnd
->nodes
[level
- 1]->index
->ihdr
: &root
->ihdr
;
2279 /* Scan current level. */
2280 for (e
= hdr_first_de(hdr
);; e
= hdr_next_de(hdr
, e
)) {
2286 if (de_has_vcn(e
) && sub_vbn
== de_get_vbn_le(e
))
2289 if (de_is_last(e
)) {
2296 /* Do slow search from root. */
2297 struct indx_node
*in
;
2301 in
= indx_find_buffer(indx
, ni
, root
, sub_vbn
, NULL
);
2308 fnd_push(fnd
, in
, NULL
);
2311 /* Merge fnd2 -> fnd. */
2312 for (level
= 0; level
< fnd2
->level
; level
++) {
2313 fnd_push(fnd
, fnd2
->nodes
[level
], fnd2
->de
[level
]);
2314 fnd2
->nodes
[level
] = NULL
;
2319 for (level
= fnd
->level
; level
; level
--) {
2320 struct indx_node
*in
= fnd
->nodes
[level
- 1];
2323 if (ib_is_empty(ib
)) {
2336 e
= hdr_first_de(hdr
);
2342 if (hdr
!= &root
->ihdr
|| !de_is_last(e
)) {
2344 while (!de_is_last(e
)) {
2345 if (de_has_vcn(e
) && sub_vbn
== de_get_vbn_le(e
))
2348 e
= hdr_next_de(hdr
, e
);
2355 if (sub_vbn
!= de_get_vbn_le(e
)) {
2357 * Didn't find the parent entry, although this buffer
2358 * is the parent trail. Something is corrupt.
2364 if (de_is_last(e
)) {
2366 * Since we can't remove the end entry, we'll remove
2367 * its predecessor instead. This means we have to
2368 * transfer the predecessor's sub_vcn to the end entry.
2369 * Note: This index block is not empty, so the
2370 * predecessor must exist.
2377 if (de_has_vcn(prev
)) {
2378 de_set_vbn_le(e
, de_get_vbn_le(prev
));
2379 } else if (de_has_vcn(e
)) {
2380 le16_sub_cpu(&e
->size
, sizeof(u64
));
2381 e
->flags
&= ~NTFS_IE_HAS_SUBNODES
;
2382 le32_sub_cpu(&hdr
->used
, sizeof(u64
));
2388 * Copy the current entry into a temporary buffer (stripping
2389 * off its down-pointer, if any) and delete it from the current
2390 * buffer or root, as appropriate.
2392 e_size
= le16_to_cpu(e
->size
);
2393 me
= kmemdup(e
, e_size
, GFP_NOFS
);
2399 if (de_has_vcn(me
)) {
2400 me
->flags
&= ~NTFS_IE_HAS_SUBNODES
;
2401 le16_sub_cpu(&me
->size
, sizeof(u64
));
2404 hdr_delete_de(hdr
, e
);
2406 if (hdr
== &root
->ihdr
) {
2408 hdr
->total
= hdr
->used
;
2410 /* Shrink resident root attribute. */
2411 mi_resize_attr(mi
, attr
, 0 - e_size
);
2413 indx_write(indx
, ni
, n2d
, 0);
2417 /* Mark unused buffers as free. */
2419 for (; level
< fnd
->level
; level
++) {
2420 ib
= fnd
->nodes
[level
]->index
;
2421 if (ib_is_empty(ib
)) {
2422 size_t k
= le64_to_cpu(ib
->vbn
) >>
2425 indx_mark_free(indx
, ni
, k
);
2432 /*fnd->root_de = NULL;*/
2435 * Re-insert the entry into the tree.
2436 * Find the spot the tree where we want to insert the new entry.
2438 err
= indx_insert_entry(indx
, ni
, me
, ctx
, fnd
, 0);
2444 indx_shrink(indx
, ni
, trim_bit
);
2447 * This tree needs to be collapsed down to an empty root.
2448 * Recreate the index root as an empty leaf and free all
2449 * the bits the index allocation bitmap.
2454 in
= &s_index_names
[indx
->type
];
2456 err
= attr_set_size(ni
, ATTR_ALLOC
, in
->name
, in
->name_len
,
2457 &indx
->alloc_run
, 0, NULL
, false, NULL
);
2458 err
= ni_remove_attr(ni
, ATTR_ALLOC
, in
->name
, in
->name_len
,
2460 run_close(&indx
->alloc_run
);
2462 err
= attr_set_size(ni
, ATTR_BITMAP
, in
->name
, in
->name_len
,
2463 &indx
->bitmap_run
, 0, NULL
, false, NULL
);
2464 err
= ni_remove_attr(ni
, ATTR_BITMAP
, in
->name
, in
->name_len
,
2466 run_close(&indx
->bitmap_run
);
2468 root
= indx_get_root(indx
, ni
, &attr
, &mi
);
2474 root_size
= le32_to_cpu(attr
->res
.data_size
);
2476 sizeof(struct INDEX_ROOT
) + sizeof(struct NTFS_DE
);
2478 if (new_root_size
!= root_size
&&
2479 !mi_resize_attr(mi
, attr
, new_root_size
- root_size
)) {
2484 /* Fill first entry. */
2485 e
= (struct NTFS_DE
*)(root
+ 1);
2489 e
->size
= cpu_to_le16(sizeof(struct NTFS_DE
));
2490 e
->flags
= NTFS_IE_LAST
; // 0x02
2496 hdr
->used
= hdr
->total
= cpu_to_le32(
2497 new_root_size
- offsetof(struct INDEX_ROOT
, ihdr
));
2510 * Update duplicated information in directory entry
2511 * 'dup' - info from MFT record
2513 int indx_update_dup(struct ntfs_inode
*ni
, struct ntfs_sb_info
*sbi
,
2514 const struct ATTR_FILE_NAME
*fname
,
2515 const struct NTFS_DUP_INFO
*dup
, int sync
)
2518 struct NTFS_DE
*e
= NULL
;
2519 struct ATTR_FILE_NAME
*e_fname
;
2520 struct ntfs_fnd
*fnd
;
2521 struct INDEX_ROOT
*root
;
2522 struct mft_inode
*mi
;
2523 struct ntfs_index
*indx
= &ni
->dir
;
2529 root
= indx_get_root(indx
, ni
, NULL
, &mi
);
2535 /* Find entry in directory. */
2536 err
= indx_find(indx
, ni
, root
, fname
, fname_full_size(fname
), sbi
,
2551 e_fname
= (struct ATTR_FILE_NAME
*)(e
+ 1);
2553 if (!memcmp(&e_fname
->dup
, dup
, sizeof(*dup
))) {
2555 * Nothing to update in index! Try to avoid this call.
2560 memcpy(&e_fname
->dup
, dup
, sizeof(*dup
));
2563 /* Directory entry in index. */
2564 err
= indx_write(indx
, ni
, fnd
->nodes
[fnd
->level
- 1], sync
);
2566 /* Directory entry in directory MFT record. */
2569 err
= mi_write(mi
, 1);
2571 mark_inode_dirty(&ni
->vfs_inode
);