1/* 2 * ntfs_index.h - Defines for index handling in the NTFS kernel driver. 3 * 4 * Copyright (c) 2006-2008 Anton Altaparmakov. All Rights Reserved. 5 * Portions Copyright (c) 2006-2008 Apple Inc. All Rights Reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright notice, 11 * this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright notice, 13 * this list of conditions and the following disclaimer in the documentation 14 * and/or other materials provided with the distribution. 15 * 3. Neither the name of Apple Inc. ("Apple") nor the names of its 16 * contributors may be used to endorse or promote products derived from this 17 * software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 20 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 22 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 23 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 26 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 * 30 * ALTERNATIVELY, provided that this notice and licensing terms are retained in 31 * full, this file may be redistributed and/or modified under the terms of the 32 * GNU General Public License (GPL) Version 2, in which case the provisions of 33 * that version of the GPL will apply to you instead of the license terms 34 * above. You can obtain a copy of the GPL Version 2 at 35 * http://developer.apple.com/opensource/licenses/gpl-2.txt. 36 */ 37 38#ifndef _OSX_NTFS_INDEX_H 39#define _OSX_NTFS_INDEX_H 40 41#include <sys/errno.h> 42 43#include <libkern/OSMalloc.h> 44 45#include <kern/debug.h> 46 47/* Foward declaration. */ 48typedef struct _ntfs_index_context ntfs_index_context; 49 50#include "ntfs_attr.h" 51#include "ntfs_inode.h" 52#include "ntfs_layout.h" 53#include "ntfs_types.h" 54 55/** 56 * @up: pointer to index context located directly above in the tree 57 * @down: pointer to index context located directly below in the tree 58 * @idx_ni: inode containing the @entry described by this context 59 * @base_ni: base inode 60 * @entry: if @is_locked this is the index entry (points into @ir or @ia) 61 * @is_root: 1 if @entry is in @ir and 0 if it is in @ia 62 * @ir: index root if @is_root and @is_locked and NULL otherwise 63 * @actx: attribute search context if @is_root and @is_locked or NULL 64 * @ia: index block if @is_root is 0 and @is_locked or NULL 65 * @upl_ofs: byte offset into the index allocation at which @upl begins 66 * @upl: page list if @is_root is 0 and @is_locked or NULL 67 * @pl: array of pages containing the page itself if @is_root is 0 68 * @addr: mapped address of the page data if @is_root is 0 and @is_locked 69 * 70 * @up and @down are pointers used to chain the various index contexts together 71 * into a path through the B+tree index. This path is used to describe the 72 * index nodes traversed during a lookup. 73 * 74 * @up points to the index context that is immediately above in the tree or if 75 * this is the top of the tree then @up is the bottom of the tree. 76 * 77 * @down points to the index context that is immediately below in the tree or 78 * if this is the bottom of the tree then @down is the top of the tree. 79 * 80 * If this index context is the only node then @up == @down == this index 81 * context. 82 * 83 * @idx_ni is the index inode this context belongs to and @base_ni is the base 84 * inode to which @idx_ni belongs. 85 * 86 * @entry is the index entry described by this context. It is only valid when 87 * @is_locked is true. 88 * 89 * If @is_rootis 1, @entry is in the index root attribute @ir described by the 90 * attribute search context @actx and the base inode @base_ni. @ia, @upl, @pl, 91 * and @addr do not exist in this case as they are in a union with @ir and 92 * @actx. 93 * 94 * If @is_root is 0, @entry is in the index allocation attribute and @ia, 95 * @upl_ofs, @upl, @pl, and @addr point to the index allocation block and the 96 * mapped, locked page it is in, respectively. @ir and @actx do not exist in 97 * this case. Note @upl_ofs is the byte offset inside the index allocation 98 * attribute at which the page list @upl begins. This is used when an index 99 * context is relocked/remapped to determine if it now is at a different 100 * virtual memory address and thus all pointers in the index context need to be 101 * updated for the new page address @addr. 102 * 103 * To obtain a context call ntfs_index_ctx_get(). 104 * 105 * We use this context to allow ntfs_index_lookup() to return the found index 106 * @entry without having to allocate a buffer and copy the @entry and/or its 107 * data into it. 108 * 109 * When finished with the @entry and its data, call ntfs_index_ctx_put() to 110 * free the context and other associated resources. 111 * 112 * If the index entry was modified, call ntfs_index_entry_mark_dirty() before 113 * the call to ntfs_index_ctx_put() to ensure that the changes are written to 114 * disk. 115 */ 116struct _ntfs_index_context { 117 ntfs_index_context *up; /* Pointer to the index context that is 118 immediately above in the tree. */ 119 ntfs_index_context *down; /* Pointer to the index context that is 120 immediately below in the tree. */ 121 ntfs_inode *idx_ni; /* Index inode. */ 122 ntfs_inode *base_ni; /* Base inode of the index inode 123 @idx_ni. */ 124 union { 125 /* Use @ie if @is_match is 1 and @follow_ie if it is 0. */ 126 INDEX_ENTRY *entry; /* Index entry matched by 127 lookup. */ 128 INDEX_ENTRY *follow_entry; /* Index entry whose sub-node 129 needs to be descended into 130 if present or index entry in 131 front of which to insert the 132 new entry. */ 133 }; 134 unsigned entry_nr; /* Index of the @entry in the @entries 135 array. */ 136 struct { 137 unsigned is_dirty:1; /* If 1 the page has been modified. */ 138 unsigned is_root:1; /* If 1 the node is the index root. */ 139 unsigned is_locked:1; /* If 1 the node is locked. */ 140 unsigned is_match:1; /* If 1 @ie matches the looked up 141 entry. */ 142 unsigned promote_inserted:1; /* If 0 insert the @insert_entry 143 index entry in front of @entry. */ 144 unsigned split_node:1; /* If 1 the node needs to be split. */ 145 unsigned right_is_locked:1; /* If 1 the right node, i.e. 146 @right_page is locked. */ 147 unsigned insert_to_add:1; /* If 1 the entry to be inserted is 148 the entry to be added, i.e. the 149 entry with which the function was 150 invoked. */ 151 unsigned bmp_is_locked:1; /* If 1 the index bitmap inode is 152 locked for writing. This is set in 153 ntfs_index_block_alloc() to cope 154 with the need for recursion into 155 itself. */ 156 }; 157 union { 158 /* Use @ir if @is_root is 1 and @ia if it is 0. */ 159 INDEX_ROOT *ir; /* The index root attribute value. */ 160 struct { 161 INDEX_ALLOCATION *ia; /* The index allocation block. */ 162 VCN vcn; /* The vcn of this index block. */ 163 }; 164 }; 165 INDEX_HEADER *index; /* The index header of the node. */ 166 union { 167 /* 168 * If @is_root is 1 then use @actx if @is_locked is also 1. 169 * If @is_locked is 0, then @actx is NULL. In the unlocked 170 * case we have to revalidate the pointers after mapping the 171 * mft record and looking up the index root attribute as it is 172 * possible that some attribute resizing operation caused the 173 * index root to be moved to a different mft record or within 174 * the same mft record and it is also possible that the VM 175 * paged out the page and then loaded it into a different place 176 * in memory. 177 * 178 * If @is_root is 0 then use @upl_ofs, @upl, @pl, and @addr. 179 */ 180 ntfs_attr_search_ctx *actx; 181 struct { 182 s64 upl_ofs; 183 upl_t upl; 184 upl_page_info_array_t pl; 185 u8 *addr; 186 }; 187 }; 188 unsigned bytes_free; /* Number of bytes free in this node. */ 189 INDEX_ENTRY **entries; /* Pointers to the index entries in the node. */ 190 unsigned nr_entries; /* Current number of entries in @entries. */ 191 unsigned max_entries; /* Maximum number of entries in @entries. */ 192 /* 193 * These fields are used when splitting nodes when inserting new index 194 * entries. 195 */ 196 /* 197 * If @promote_inserted is 0 then @insert_entry_nr, @insert_entry_size, 198 * and @insert_ictx describe the index entry of a child index node to 199 * be inserted into this index block in front of the index entry 200 * @entry. 201 * 202 * If @insert_to_add is 1 then the entry that is to be inserted into 203 * this node is the entry being added to the index with the current 204 * call to ntfs_index_entry_add(), i.e. it does not come from a child 205 * node. In that case @insert_ictx and @insert_entry_nr are not valid. 206 * 207 * If @promote_inserted is 1 then nothing needs to be inserted into 208 * this node, i.e. the node just needs to be split. This happens when 209 * the index entry to be inserted is the median entry and it is being 210 * promoted to our parent node. 211 */ 212 ntfs_index_context *insert_ictx; 213 unsigned insert_entry_nr; 214 u32 insert_entry_size; 215 /* 216 * If @split_node is 1 then @promote_entry_nr and @promote_inserted 217 * describe the index entry being promoted and thus describe the 218 * position in the index at which the node is to be split. 219 * 220 * If @cur_ictx->promote_inserted is 1 we have to keep the entry 221 * @cur_ictx->promote_entry_nr and move it together with all following 222 * entries to the right-hand node. And if @cur_ictx->promote_inserted 223 * is 0 we have to remove the entry @cur_ictx->promote_entry_nr and 224 * move all following entries to the right-hand node. 225 * 226 * @right_vcn, @right_ia, @right_upl_ofs, @right_upl, @right_pl, and 227 * @right_addr in turn describe the allocated index block to be used as 228 * the destination for the index entries that are split away from the 229 * right-hand side of the median of the index block as described above. 230 */ 231 unsigned promote_entry_nr; 232 VCN right_vcn; 233 INDEX_ALLOCATION *right_ia; 234 s64 right_upl_ofs; 235 upl_t right_upl; 236 upl_page_info_array_t right_pl; 237 u8 *right_addr; 238}; 239 240/** 241 * ntfs_index_ctx_alloc - allocate an index context 242 * 243 * Allocate an index context and return it. 244 */ 245static inline ntfs_index_context *ntfs_index_ctx_alloc(void) 246{ 247 return OSMalloc(sizeof(ntfs_index_context), ntfs_malloc_tag); 248} 249 250/** 251 * ntfs_index_ctx_init - initialize an index context 252 * @ictx: index context to initialize 253 * @idx_ni: ntfs index inode with which to initialize the context 254 * 255 * Initialize the index context @ictx with @idx_ni and its base inode and set 256 * its @up and @down pointers to point to itself. 257 * 258 * Locking: Caller must hold @idx_ni->lock on the index inode. 259 */ 260static inline void ntfs_index_ctx_init(ntfs_index_context *ictx, 261 ntfs_inode *idx_ni) 262{ 263 *ictx = (ntfs_index_context) { 264 .up = ictx, 265 .down = ictx, 266 .idx_ni = idx_ni, 267 .base_ni = NInoAttr(idx_ni) ? idx_ni->base_ni : idx_ni, 268 }; 269} 270 271__private_extern__ ntfs_index_context *ntfs_index_ctx_get(ntfs_inode *idx_ni); 272 273__private_extern__ void ntfs_index_ctx_put_reuse_single( 274 ntfs_index_context *ictx); 275 276__private_extern__ void ntfs_index_ctx_put_reuse(ntfs_index_context *ictx); 277 278/** 279 * ntfs_index_ctx_reinit - re-initialize an index context 280 * @ictx: index context to re-initialize 281 * @idx_ni: ntfs index inode with which to initialize the context 282 * 283 * Re-initialize the index context @ictx with @idx_ni and its base inode. 284 * 285 * To do this the existing index context is first put for reuse and then 286 * initialized from scratch with the index inode @idx_ni. 287 * 288 * Locking: Caller must hold @idx_ni->lock on the index inode. 289 */ 290static inline void ntfs_index_ctx_reinit(ntfs_index_context *ictx, 291 ntfs_inode *idx_ni) 292{ 293 ntfs_index_ctx_put_reuse(ictx); 294 ntfs_index_ctx_init(ictx, idx_ni); 295} 296 297/** 298 * ntfs_index_ctx_disconnect - disconnect an index context from its tree path 299 * @ictx: index context to disconnect 300 * 301 * Disconnect the index context @ictx from its tree path. This function leaves 302 * @ictx in an invalid state. We only use it when we are about to throw away 303 * @ictx thus do not care what state it is left in. 304 * 305 * Locking: Caller must hold @ictx->idx_ni->lock on the index inode. 306 */ 307static inline void ntfs_index_ctx_disconnect(ntfs_index_context *ictx) 308{ 309 ictx->up->down = ictx->down; 310 ictx->down->up = ictx->up; 311} 312 313/** 314 * ntfs_index_ctx_free - free an index context 315 * @ictx: index context to free 316 * 317 * Free the index context @ictx. 318 */ 319static inline void ntfs_index_ctx_free(ntfs_index_context *ictx) 320{ 321 OSFree(ictx, sizeof(*ictx), ntfs_malloc_tag); 322} 323 324/** 325 * ntfs_index_ctx_put_single - release a single index context 326 * @ictx: index context to free 327 * 328 * Release the index context @ictx, disconnecting it from its tree path and 329 * releasing all associated resources. 330 * 331 * Locking: Caller must hold @ictx->idx_ni->lock on the index inode. 332 */ 333static inline void ntfs_index_ctx_put_single(ntfs_index_context *ictx) 334{ 335 /* Disconnect the current index context from the tree. */ 336 ntfs_index_ctx_disconnect(ictx); 337 /* Release all resources held by the current index context. */ 338 ntfs_index_ctx_put_reuse_single(ictx); 339 /* Deallocate the current index context. */ 340 ntfs_index_ctx_free(ictx); 341} 342 343/** 344 * ntfs_index_ctx_put - release an index context 345 * @ictx: index context to free 346 * 347 * Release the index context @ictx, releasing all associated resources. 348 * 349 * Locking: Caller must hold @ictx->idx_ni->lock on the index inode. 350 */ 351static inline void ntfs_index_ctx_put(ntfs_index_context *ictx) 352{ 353 ntfs_index_ctx_put_reuse(ictx); 354 ntfs_index_ctx_free(ictx); 355} 356 357__private_extern__ void ntfs_index_ctx_unlock(ntfs_index_context *ictx); 358 359__private_extern__ errno_t ntfs_index_ctx_relock(ntfs_index_context *ictx); 360 361__private_extern__ errno_t ntfs_index_lookup(const void *key, 362 const int key_len, ntfs_index_context **ictx); 363 364__private_extern__ errno_t ntfs_index_lookup_by_position(const s64 pos, 365 const int key_len, ntfs_index_context **index_ctx); 366 367__private_extern__ errno_t ntfs_index_lookup_next( 368 ntfs_index_context **index_ctx); 369 370__private_extern__ void ntfs_index_entry_mark_dirty(ntfs_index_context *ictx); 371 372__private_extern__ errno_t ntfs_index_move_root_to_allocation_block( 373 ntfs_index_context *ictx); 374 375__private_extern__ int ntfs_index_entry_delete(ntfs_index_context *ictx); 376 377__private_extern__ errno_t ntfs_index_entry_add_or_node_split( 378 ntfs_index_context *ictx, const BOOL split_only, 379 u32 entry_size, const void *key, const u32 key_len, 380 const void *data, const u32 data_len); 381 382/** 383 * ntfs_index_entry_add - add a key to an index 384 * @ictx: index context specifying the position at which to add 385 * @key: key to add to the directory or view index 386 * @key_len: size of key @key in bytes 387 * @data: data to associate with the key @key if a view index 388 * @data_len: size of data @data in bytes if a view index 389 * 390 * If @ictx belongs to a directory index, insert the filename attribute @key of 391 * length @key_len bytes in the directory index at the position specified by 392 * the index context @ictx and point the inserted index entry at the mft 393 * reference *@data which is the mft reference of the inode to which the 394 * filename @fn belongs. @data_len must be zero in this case. 395 * 396 * If @ictx belongs to a view index, insert the key @key of length @key_len 397 * bytes in the view index at the position specified by the index context @ictx 398 * and associate the data @data of size @data_len bytes with the key @key. 399 * 400 * Return 0 on success and errno on error. On error the index context is no 401 * longer usable and must be released or reinitialized. 402 * 403 * Note that we do not update the array of index entry pointers nor the number 404 * of entries in the array because on success it means that the index entry has 405 * been added and the function is done, i.e. the array of index entry pointers 406 * will not be used any more and on error the index context becomes invalid so 407 * there is no need to update any of the pointers. 408 * 409 * Locking: - Caller must hold @ictx->idx_ni->lock on the index inode for 410 * writing. 411 * - The index context @ictx must be locked. 412 */ 413static inline errno_t ntfs_index_entry_add(ntfs_index_context *ictx, 414 const void *key, const u32 key_len, 415 const void *data, const u32 data_len) 416{ 417 return ntfs_index_entry_add_or_node_split(ictx, FALSE, 0, key, key_len, 418 data, data_len); 419} 420 421#endif /* _OSX_NTFS_INDEX_H */ 422