3  * index.c - NTFS kernel index handling.  Part of the Linux-NTFS project.
13 #include "index.h"
17  * ntfs_index_ctx_get - allocate and initialize a new index context
18  * @idx_ni:	ntfs index inode with which to initialize the context
20  * Allocate a new index context, initialize it with @idx_ni and return it.
23  * Locking:  Caller must hold i_mutex on the index inode.
36  * ntfs_index_ctx_put - release an index context
37  * @ictx:	index context to free
39  * Release the index context @ictx, releasing all associated resources.
41  * Locking:  Caller must hold i_mutex on the index inode.
65  * ntfs_index_lookup - find a key in an index and return its index entry
66  * @key:	[IN] key for which to search in the index
68  * @ictx:	[IN/OUT] context describing the index and the returned entry
73  * Look for the @key in the index specified by the index lookup context @ictx.
74  * ntfs_index_lookup() walks the contents of the index looking for the @key.
76  * If the @key is found in the index, 0 is returned and @ictx is setup to
77  * describe the index entry containing the matching @key.  @ictx->entry is the
78  * index entry and @ictx->data and @ictx->data_len are the index entry data and
81  * If the @key is not found in the index, -ENOENT is returned and @ictx is
82  * setup to describe the index entry whose key collates immediately after the
83  * search @key, i.e. this is the position in the index at which an index entry
92  * If the index entry was modified, call flush_dcache_index_entry_page()
97  * Locking:  - Caller must hold i_mutex on the index inode.
98  *	     - Each page cache page in the index allocation mapping must be
131 			idx_ni->itype.index.collation_rule)) {  in ntfs_index_lookup()
132 		ntfs_error(sb, "Index uses unsupported collation rule 0x%x.  "  in ntfs_index_lookup()
134 				idx_ni->itype.index.collation_rule));  in ntfs_index_lookup()
137 	/* Get hold of the mft record for the index inode. */  in ntfs_index_lookup()
149 	/* Find the index root attribute in the mft record. */  in ntfs_index_lookup()
154 			ntfs_error(sb, "Index root attribute missing in inode "  in ntfs_index_lookup()
160 	/* Get to the index root value (it has been verified in read_inode). */  in ntfs_index_lookup()
163 	index_end = (u8*)&ir->index + le32_to_cpu(ir->index.index_length);  in ntfs_index_lookup()
164 	/* The first index entry. */  in ntfs_index_lookup()
165 	ie = (INDEX_ENTRY*)((u8*)&ir->index +  in ntfs_index_lookup()
166 			le32_to_cpu(ir->index.entries_offset));  in ntfs_index_lookup()
213 		rc = ntfs_collate(vol, idx_ni->itype.index.collation_rule, key,  in ntfs_index_lookup()
217 		 * is definitely no such key in this index but we might need to  in ntfs_index_lookup()
231 	 * We have finished with this index without success.  Check for the  in ntfs_index_lookup()
240 	/* Consistency check: Verify that an index allocation exists. */  in ntfs_index_lookup()
242 		ntfs_error(sb, "No index allocation attribute but index entry "  in ntfs_index_lookup()
251 	 * We are done with the index root and the mft record.  Release them,  in ntfs_index_lookup()
260 	 * Convert vcn to index into the index allocation attribute in units  in ntfs_index_lookup()
265 			idx_ni->itype.index.vcn_size_bits >> PAGE_SHIFT);  in ntfs_index_lookup()
267 		ntfs_error(sb, "Failed to map index page, error %ld.",  in ntfs_index_lookup()
275 	/* Get to the index allocation block. */  in ntfs_index_lookup()
277 			idx_ni->itype.index.vcn_size_bits) & ~PAGE_MASK));  in ntfs_index_lookup()
286 		ntfs_error(sb, "Index record with vcn 0x%llx is corrupt.  "  in ntfs_index_lookup()
292 		ntfs_error(sb, "Actual VCN (0x%llx) of index buffer is "  in ntfs_index_lookup()
300 	if (le32_to_cpu(ia->index.allocated_size) + 0x18 !=  in ntfs_index_lookup()
301 			idx_ni->itype.index.block_size) {  in ntfs_index_lookup()
302 		ntfs_error(sb, "Index buffer (VCN 0x%llx) of inode 0x%lx has "  in ntfs_index_lookup()
303 				"a size (%u) differing from the index "  in ntfs_index_lookup()
307 				le32_to_cpu(ia->index.allocated_size) + 0x18,  in ntfs_index_lookup()
308 				idx_ni->itype.index.block_size);  in ntfs_index_lookup()
311 	index_end = (u8*)ia + idx_ni->itype.index.block_size;  in ntfs_index_lookup()
313 		ntfs_error(sb, "Index buffer (VCN 0x%llx) of inode 0x%lx "  in ntfs_index_lookup()
320 	index_end = (u8*)&ia->index + le32_to_cpu(ia->index.index_length);  in ntfs_index_lookup()
321 	if (index_end > (u8*)ia + idx_ni->itype.index.block_size) {  in ntfs_index_lookup()
322 		ntfs_error(sb, "Size of index buffer (VCN 0x%llx) of inode "  in ntfs_index_lookup()
327 	/* The first index entry. */  in ntfs_index_lookup()
328 	ie = (INDEX_ENTRY*)((u8*)&ia->index +  in ntfs_index_lookup()
329 			le32_to_cpu(ia->index.entries_offset));  in ntfs_index_lookup()
331 	 * Iterate similar to above big loop but applied to index buffer, thus  in ntfs_index_lookup()
340 			ntfs_error(sb, "Index entry out of bounds in inode "  in ntfs_index_lookup()
357 			ntfs_error(sb, "Index entry out of bounds in inode "  in ntfs_index_lookup()
376 		rc = ntfs_collate(vol, idx_ni->itype.index.collation_rule, key,  in ntfs_index_lookup()
380 		 * is definitely no such key in this index but we might need to  in ntfs_index_lookup()
394 	 * We have finished with this index buffer without success.  Check for  in ntfs_index_lookup()
402 	if ((ia->index.flags & NODE_MASK) == LEAF_NODE) {  in ntfs_index_lookup()
403 		ntfs_error(sb, "Index entry with child node found in a leaf "  in ntfs_index_lookup()
438 	ntfs_error(sb, "Corrupt index.  Aborting lookup.");  in ntfs_index_lookup()