xref: /haiku/src/add-ons/kernel/file_systems/ntfs/libntfs/index.c (revision 820dca4df6c7bf955c46e8f6521b9408f50b2900)
1 /**
2  * index.c - NTFS index handling.  Originated from the Linux-NTFS project.
3  *
4  * Copyright (c) 2004-2005 Anton Altaparmakov
5  * Copyright (c) 2004-2005 Richard Russon
6  * Copyright (c) 2005-2006 Yura Pakhuchiy
7  * Copyright (c) 2005-2008 Szabolcs Szakacsits
8  * Copyright (c) 2007 Jean-Pierre Andre
9  *
10  * This program/include file is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License as published
12  * by the Free Software Foundation; either version 2 of the License, or
13  * (at your option) any later version.
14  *
15  * This program/include file is distributed in the hope that it will be
16  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
17  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program (in the main directory of the NTFS-3G
22  * distribution in the file COPYING); if not, write to the Free Software
23  * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
24  */
25 
26 #ifdef HAVE_CONFIG_H
27 #include "config.h"
28 #endif
29 
30 #ifdef HAVE_STDLIB_H
31 #include <stdlib.h>
32 #endif
33 #ifdef HAVE_STRING_H
34 #include <string.h>
35 #endif
36 #ifdef HAVE_ERRNO_H
37 #include <errno.h>
38 #endif
39 
40 #include "attrib.h"
41 #include "debug.h"
42 #include "index.h"
43 #include "collate.h"
44 #include "mst.h"
45 #include "dir.h"
46 #include "logging.h"
47 #include "bitmap.h"
48 #include "reparse.h"
49 #include "misc.h"
50 
51 /**
52  * ntfs_index_entry_mark_dirty - mark an index entry dirty
53  * @ictx:	ntfs index context describing the index entry
54  *
55  * Mark the index entry described by the index entry context @ictx dirty.
56  *
57  * If the index entry is in the index root attribute, simply mark the inode
58  * containing the index root attribute dirty.  This ensures the mftrecord, and
59  * hence the index root attribute, will be written out to disk later.
60  *
61  * If the index entry is in an index block belonging to the index allocation
62  * attribute, set ib_dirty to TRUE, thus index block will be updated during
63  * ntfs_index_ctx_put.
64  */
65 void ntfs_index_entry_mark_dirty(ntfs_index_context *ictx)
66 {
67 	if (ictx->is_in_root)
68 		ntfs_inode_mark_dirty(ictx->actx->ntfs_ino);
69 	else
70 		ictx->ib_dirty = TRUE;
71 }
72 
73 static s64 ntfs_ib_vcn_to_pos(ntfs_index_context *icx, VCN vcn)
74 {
75 	return vcn << icx->vcn_size_bits;
76 }
77 
78 static VCN ntfs_ib_pos_to_vcn(ntfs_index_context *icx, s64 pos)
79 {
80 	return pos >> icx->vcn_size_bits;
81 }
82 
83 static int ntfs_ib_write(ntfs_index_context *icx, INDEX_BLOCK *ib)
84 {
85 	s64 ret, vcn = sle64_to_cpu(ib->index_block_vcn);
86 
87 	ntfs_log_trace("vcn: %lld\n", (long long)vcn);
88 
89 	ret = ntfs_attr_mst_pwrite(icx->ia_na, ntfs_ib_vcn_to_pos(icx, vcn),
90 				   1, icx->block_size, ib);
91 	if (ret != 1) {
92 		ntfs_log_perror("Failed to write index block %lld, inode %llu",
93 			(long long)vcn, (unsigned long long)icx->ni->mft_no);
94 		return STATUS_ERROR;
95 	}
96 
97 	return STATUS_OK;
98 }
99 
100 static int ntfs_icx_ib_write(ntfs_index_context *icx)
101 {
102 		if (ntfs_ib_write(icx, icx->ib))
103 			return STATUS_ERROR;
104 
105 		icx->ib_dirty = FALSE;
106 
107 		return STATUS_OK;
108 }
109 
110 /**
111  * ntfs_index_ctx_get - allocate and initialize a new index context
112  * @ni:		ntfs inode with which to initialize the context
113  * @name:	name of the which context describes
114  * @name_len:	length of the index name
115  *
116  * Allocate a new index context, initialize it with @ni and return it.
117  * Return NULL if allocation failed.
118  */
119 ntfs_index_context *ntfs_index_ctx_get(ntfs_inode *ni,
120 				       ntfschar *name, u32 name_len)
121 {
122 	ntfs_index_context *icx;
123 
124 	ntfs_log_trace("Entering\n");
125 
126 	if (!ni) {
127 		errno = EINVAL;
128 		return NULL;
129 	}
130 	if (ni->nr_extents == -1)
131 		ni = ni->base_ni;
132 	icx = ntfs_calloc(sizeof(ntfs_index_context));
133 	if (icx)
134 		*icx = (ntfs_index_context) {
135 			.ni = ni,
136 			.name = name,
137 			.name_len = name_len,
138 		};
139 	return icx;
140 }
141 
142 static void ntfs_index_ctx_free(ntfs_index_context *icx)
143 {
144 	ntfs_log_trace("Entering\n");
145 
146 	if (!icx->entry)
147 		return;
148 
149 	if (icx->actx)
150 		ntfs_attr_put_search_ctx(icx->actx);
151 
152 	if (!icx->is_in_root) {
153 		if (icx->ib_dirty) {
154 			/* FIXME: Error handling!!! */
155 			ntfs_ib_write(icx, icx->ib);
156 		}
157 		free(icx->ib);
158 	}
159 
160 	ntfs_attr_close(icx->ia_na);
161 }
162 
163 /**
164  * ntfs_index_ctx_put - release an index context
165  * @icx:	index context to free
166  *
167  * Release the index context @icx, releasing all associated resources.
168  */
169 void ntfs_index_ctx_put(ntfs_index_context *icx)
170 {
171 	ntfs_index_ctx_free(icx);
172 	free(icx);
173 }
174 
175 /**
176  * ntfs_index_ctx_reinit - reinitialize an index context
177  * @icx:	index context to reinitialize
178  *
179  * Reinitialize the index context @icx so it can be used for ntfs_index_lookup.
180  */
181 void ntfs_index_ctx_reinit(ntfs_index_context *icx)
182 {
183 	ntfs_log_trace("Entering\n");
184 
185 	ntfs_index_ctx_free(icx);
186 
187 	*icx = (ntfs_index_context) {
188 		.ni = icx->ni,
189 		.name = icx->name,
190 		.name_len = icx->name_len,
191 	};
192 }
193 
194 static VCN *ntfs_ie_get_vcn_addr(INDEX_ENTRY *ie)
195 {
196 	return (VCN *)((u8 *)ie + le16_to_cpu(ie->length) - sizeof(VCN));
197 }
198 
199 /**
200  *  Get the subnode vcn to which the index entry refers.
201  */
202 VCN ntfs_ie_get_vcn(INDEX_ENTRY *ie)
203 {
204 	return sle64_to_cpup(ntfs_ie_get_vcn_addr(ie));
205 }
206 
207 static INDEX_ENTRY *ntfs_ie_get_first(INDEX_HEADER *ih)
208 {
209 	return (INDEX_ENTRY *)((u8 *)ih + le32_to_cpu(ih->entries_offset));
210 }
211 
212 static INDEX_ENTRY *ntfs_ie_get_next(INDEX_ENTRY *ie)
213 {
214 	return (INDEX_ENTRY *)((char *)ie + le16_to_cpu(ie->length));
215 }
216 
217 static u8 *ntfs_ie_get_end(INDEX_HEADER *ih)
218 {
219 	/* FIXME: check if it isn't overflowing the index block size */
220 	return (u8 *)ih + le32_to_cpu(ih->index_length);
221 }
222 
223 static int ntfs_ie_end(INDEX_ENTRY *ie)
224 {
225 	return ie->ie_flags & INDEX_ENTRY_END || !ie->length;
226 }
227 
228 /**
229  *  Find the last entry in the index block
230  */
231 static INDEX_ENTRY *ntfs_ie_get_last(INDEX_ENTRY *ie, char *ies_end)
232 {
233 	ntfs_log_trace("Entering\n");
234 
235 	while ((char *)ie < ies_end && !ntfs_ie_end(ie))
236 		ie = ntfs_ie_get_next(ie);
237 
238 	return ie;
239 }
240 
241 static INDEX_ENTRY *ntfs_ie_get_by_pos(INDEX_HEADER *ih, int pos)
242 {
243 	INDEX_ENTRY *ie;
244 
245 	ntfs_log_trace("pos: %d\n", pos);
246 
247 	ie = ntfs_ie_get_first(ih);
248 
249 	while (pos-- > 0)
250 		ie = ntfs_ie_get_next(ie);
251 
252 	return ie;
253 }
254 
255 static INDEX_ENTRY *ntfs_ie_prev(INDEX_HEADER *ih, INDEX_ENTRY *ie)
256 {
257 	INDEX_ENTRY *ie_prev = NULL;
258 	INDEX_ENTRY *tmp;
259 
260 	ntfs_log_trace("Entering\n");
261 
262 	tmp = ntfs_ie_get_first(ih);
263 
264 	while (tmp != ie) {
265 		ie_prev = tmp;
266 		tmp = ntfs_ie_get_next(tmp);
267 	}
268 
269 	return ie_prev;
270 }
271 
272 char *ntfs_ie_filename_get(INDEX_ENTRY *ie)
273 {
274 	FILE_NAME_ATTR *fn;
275 
276 	fn = (FILE_NAME_ATTR *)&ie->key;
277 	return ntfs_attr_name_get(fn->file_name, fn->file_name_length);
278 }
279 
280 void ntfs_ie_filename_dump(INDEX_ENTRY *ie)
281 {
282 	char *s;
283 
284 	s = ntfs_ie_filename_get(ie);
285 	ntfs_log_debug("'%s' ", s);
286 	ntfs_attr_name_free(&s);
287 }
288 
289 void ntfs_ih_filename_dump(INDEX_HEADER *ih)
290 {
291 	INDEX_ENTRY *ie;
292 
293 	ntfs_log_trace("Entering\n");
294 
295 	ie = ntfs_ie_get_first(ih);
296 	while (!ntfs_ie_end(ie)) {
297 		ntfs_ie_filename_dump(ie);
298 		ie = ntfs_ie_get_next(ie);
299 	}
300 }
301 
302 static int ntfs_ih_numof_entries(INDEX_HEADER *ih)
303 {
304 	int n;
305 	INDEX_ENTRY *ie;
306 	u8 *end;
307 
308 	ntfs_log_trace("Entering\n");
309 
310 	end = ntfs_ie_get_end(ih);
311 	ie = ntfs_ie_get_first(ih);
312 	for (n = 0; !ntfs_ie_end(ie) && (u8 *)ie < end; n++)
313 		ie = ntfs_ie_get_next(ie);
314 	return n;
315 }
316 
317 static int ntfs_ih_one_entry(INDEX_HEADER *ih)
318 {
319 	return (ntfs_ih_numof_entries(ih) == 1);
320 }
321 
322 static int ntfs_ih_zero_entry(INDEX_HEADER *ih)
323 {
324 	return (ntfs_ih_numof_entries(ih) == 0);
325 }
326 
327 static void ntfs_ie_delete(INDEX_HEADER *ih, INDEX_ENTRY *ie)
328 {
329 	u32 new_size;
330 
331 	ntfs_log_trace("Entering\n");
332 
333 	new_size = le32_to_cpu(ih->index_length) - le16_to_cpu(ie->length);
334 	ih->index_length = cpu_to_le32(new_size);
335 	memmove(ie, (u8 *)ie + le16_to_cpu(ie->length),
336 		new_size - ((u8 *)ie - (u8 *)ih));
337 }
338 
339 static void ntfs_ie_set_vcn(INDEX_ENTRY *ie, VCN vcn)
340 {
341 	*ntfs_ie_get_vcn_addr(ie) = cpu_to_le64(vcn);
342 }
343 
344 /**
345  *  Insert @ie index entry at @pos entry. Used @ih values should be ok already.
346  */
347 static void ntfs_ie_insert(INDEX_HEADER *ih, INDEX_ENTRY *ie, INDEX_ENTRY *pos)
348 {
349 	int ie_size = le16_to_cpu(ie->length);
350 
351 	ntfs_log_trace("Entering\n");
352 
353 	ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) + ie_size);
354 	memmove((u8 *)pos + ie_size, pos,
355 		le32_to_cpu(ih->index_length) - ((u8 *)pos - (u8 *)ih) - ie_size);
356 	memcpy(pos, ie, ie_size);
357 }
358 
359 static INDEX_ENTRY *ntfs_ie_dup(INDEX_ENTRY *ie)
360 {
361 	INDEX_ENTRY *dup;
362 
363 	ntfs_log_trace("Entering\n");
364 
365 	dup = ntfs_malloc(le16_to_cpu(ie->length));
366 	if (dup)
367 		memcpy(dup, ie, le16_to_cpu(ie->length));
368 
369 	return dup;
370 }
371 
372 static INDEX_ENTRY *ntfs_ie_dup_novcn(INDEX_ENTRY *ie)
373 {
374 	INDEX_ENTRY *dup;
375 	int size = le16_to_cpu(ie->length);
376 
377 	ntfs_log_trace("Entering\n");
378 
379 	if (ie->ie_flags & INDEX_ENTRY_NODE)
380 		size -= sizeof(VCN);
381 
382 	dup = ntfs_malloc(size);
383 	if (dup) {
384 		memcpy(dup, ie, size);
385 		dup->ie_flags &= ~INDEX_ENTRY_NODE;
386 		dup->length = cpu_to_le16(size);
387 	}
388 	return dup;
389 }
390 
391 static int ntfs_ia_check(ntfs_index_context *icx, INDEX_BLOCK *ib, VCN vcn)
392 {
393 	u32 ib_size = (unsigned)le32_to_cpu(ib->index.allocated_size) + 0x18;
394 
395 	ntfs_log_trace("Entering\n");
396 
397 	if (!ntfs_is_indx_record(ib->magic)) {
398 
399 		ntfs_log_error("Corrupt index block signature: vcn %lld inode "
400 			       "%llu\n", (long long)vcn,
401 			       (unsigned long long)icx->ni->mft_no);
402 		return -1;
403 	}
404 
405 	if (sle64_to_cpu(ib->index_block_vcn) != vcn) {
406 
407 		ntfs_log_error("Corrupt index block: VCN (%lld) is different "
408 			       "from expected VCN (%lld) in inode %llu\n",
409 			       (long long)sle64_to_cpu(ib->index_block_vcn),
410 			       (long long)vcn,
411 			       (unsigned long long)icx->ni->mft_no);
412 		return -1;
413 	}
414 
415 	if (ib_size != icx->block_size) {
416 
417 		ntfs_log_error("Corrupt index block : VCN (%lld) of inode %llu "
418 			       "has a size (%u) differing from the index "
419 			       "specified size (%u)\n", (long long)vcn,
420 			       (unsigned long long)icx->ni->mft_no, ib_size,
421 			       icx->block_size);
422 		return -1;
423 	}
424 	return 0;
425 }
426 
427 static INDEX_ROOT *ntfs_ir_lookup(ntfs_inode *ni, ntfschar *name,
428 				  u32 name_len, ntfs_attr_search_ctx **ctx)
429 {
430 	ATTR_RECORD *a;
431 	INDEX_ROOT *ir = NULL;
432 
433 	ntfs_log_trace("Entering\n");
434 
435 	*ctx = ntfs_attr_get_search_ctx(ni, NULL);
436 	if (!*ctx)
437 		return NULL;
438 
439 	if (ntfs_attr_lookup(AT_INDEX_ROOT, name, name_len, CASE_SENSITIVE,
440 			     0, NULL, 0, *ctx)) {
441 		ntfs_log_perror("Failed to lookup $INDEX_ROOT");
442 		goto err_out;
443 	}
444 
445 	a = (*ctx)->attr;
446 	if (a->non_resident) {
447 		errno = EINVAL;
448 		ntfs_log_perror("Non-resident $INDEX_ROOT detected");
449 		goto err_out;
450 	}
451 
452 	ir = (INDEX_ROOT *)((char *)a + le16_to_cpu(a->value_offset));
453 err_out:
454 	if (!ir) {
455 		ntfs_attr_put_search_ctx(*ctx);
456 		*ctx = NULL;
457 	}
458 	return ir;
459 }
460 
461 static INDEX_ROOT *ntfs_ir_lookup2(ntfs_inode *ni, ntfschar *name, u32 len)
462 {
463 	ntfs_attr_search_ctx *ctx;
464 	INDEX_ROOT *ir;
465 
466 	ir = ntfs_ir_lookup(ni, name, len, &ctx);
467 	if (ir)
468 		ntfs_attr_put_search_ctx(ctx);
469 	return ir;
470 }
471 
472 /**
473  * Find a key in the index block.
474  *
475  * Return values:
476  *   STATUS_OK with errno set to ESUCCESS if we know for sure that the
477  *             entry exists and @ie_out points to this entry.
478  *   STATUS_NOT_FOUND with errno set to ENOENT if we know for sure the
479  *                    entry doesn't exist and @ie_out is the insertion point.
480  *   STATUS_KEEP_SEARCHING if we can't answer the above question and
481  *                         @vcn will contain the node index block.
482  *   STATUS_ERROR with errno set if on unexpected error during lookup.
483  */
484 static int ntfs_ie_lookup(const void *key, const int key_len,
485 			  ntfs_index_context *icx, INDEX_HEADER *ih,
486 			  VCN *vcn, INDEX_ENTRY **ie_out)
487 {
488 	INDEX_ENTRY *ie;
489 	u8 *index_end;
490 	int rc, item = 0;
491 
492 	ntfs_log_trace("Entering\n");
493 
494 	index_end = ntfs_ie_get_end(ih);
495 
496 	/*
497 	 * Loop until we exceed valid memory (corruption case) or until we
498 	 * reach the last entry.
499 	 */
500 	for (ie = ntfs_ie_get_first(ih); ; ie = ntfs_ie_get_next(ie)) {
501 		/* Bounds checks. */
502 		if ((u8 *)ie + sizeof(INDEX_ENTRY_HEADER) > index_end ||
503 		    (u8 *)ie + le16_to_cpu(ie->length) > index_end) {
504 			errno = ERANGE;
505 			ntfs_log_error("Index entry out of bounds in inode "
506 				       "%llu.\n",
507 				       (unsigned long long)icx->ni->mft_no);
508 			return STATUS_ERROR;
509 		}
510 		/*
511 		 * The last entry cannot contain a key.  It can however contain
512 		 * a pointer to a child node in the B+tree so we just break out.
513 		 */
514 		if (ntfs_ie_end(ie))
515 			break;
516 		/*
517 		 * Not a perfect match, need to do full blown collation so we
518 		 * know which way in the B+tree we have to go.
519 		 */
520 		if (!icx->collate) {
521 			ntfs_log_error("Collation function not defined\n");
522 			errno = EOPNOTSUPP;
523 			return STATUS_ERROR;
524 		}
525 		rc = icx->collate(icx->ni->vol, key, key_len,
526 					&ie->key, le16_to_cpu(ie->key_length));
527 		if (rc == NTFS_COLLATION_ERROR) {
528 			ntfs_log_error("Collation error. Perhaps a filename "
529 				       "contains invalid characters?\n");
530 			errno = ERANGE;
531 			return STATUS_ERROR;
532 		}
533 		/*
534 		 * If @key collates before the key of the current entry, there
535 		 * is definitely no such key in this index but we might need to
536 		 * descend into the B+tree so we just break out of the loop.
537 		 */
538 		if (rc == -1)
539 			break;
540 
541 		if (!rc) {
542 			*ie_out = ie;
543 			errno = 0;
544 			icx->parent_pos[icx->pindex] = item;
545 			return STATUS_OK;
546 		}
547 
548 		item++;
549 	}
550 	/*
551 	 * We have finished with this index block without success. Check for the
552 	 * presence of a child node and if not present return with errno ENOENT,
553 	 * otherwise we will keep searching in another index block.
554 	 */
555 	if (!(ie->ie_flags & INDEX_ENTRY_NODE)) {
556 		ntfs_log_debug("Index entry wasn't found.\n");
557 		*ie_out = ie;
558 		errno = ENOENT;
559 		return STATUS_NOT_FOUND;
560 	}
561 
562 	/* Get the starting vcn of the index_block holding the child node. */
563 	*vcn = ntfs_ie_get_vcn(ie);
564 	if (*vcn < 0) {
565 		errno = EINVAL;
566 		ntfs_log_perror("Negative vcn in inode %llu",
567 			       	(unsigned long long)icx->ni->mft_no);
568 		return STATUS_ERROR;
569 	}
570 
571 	ntfs_log_trace("Parent entry number %d\n", item);
572 	icx->parent_pos[icx->pindex] = item;
573 
574 	return STATUS_KEEP_SEARCHING;
575 }
576 
577 static ntfs_attr *ntfs_ia_open(ntfs_index_context *icx, ntfs_inode *ni)
578 {
579 	ntfs_attr *na;
580 
581 	na = ntfs_attr_open(ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len);
582 	if (!na) {
583 		ntfs_log_perror("Failed to open index allocation of inode "
584 				"%llu", (unsigned long long)ni->mft_no);
585 		return NULL;
586 	}
587 
588 	return na;
589 }
590 
591 static int ntfs_ib_read(ntfs_index_context *icx, VCN vcn, INDEX_BLOCK *dst)
592 {
593 	s64 pos, ret;
594 
595 	ntfs_log_trace("vcn: %lld\n", (long long)vcn);
596 
597 	pos = ntfs_ib_vcn_to_pos(icx, vcn);
598 
599 	ret = ntfs_attr_mst_pread(icx->ia_na, pos, 1, icx->block_size, (u8 *)dst);
600 	if (ret != 1) {
601 		if (ret == -1)
602 			ntfs_log_perror("Failed to read index block");
603 		else
604 			ntfs_log_error("Failed to read full index block at "
605 				       "%lld\n", (long long)pos);
606 		return -1;
607 	}
608 
609 	if (ntfs_ia_check(icx, dst, vcn))
610 		return -1;
611 
612 	return 0;
613 }
614 
615 static int ntfs_icx_parent_inc(ntfs_index_context *icx)
616 {
617 	icx->pindex++;
618 	if (icx->pindex >= MAX_PARENT_VCN) {
619 		errno = EOPNOTSUPP;
620 		ntfs_log_perror("Index is over %d level deep", MAX_PARENT_VCN);
621 		return STATUS_ERROR;
622 	}
623 	return STATUS_OK;
624 }
625 
626 static int ntfs_icx_parent_dec(ntfs_index_context *icx)
627 {
628 	icx->pindex--;
629 	if (icx->pindex < 0) {
630 		errno = EINVAL;
631 		ntfs_log_perror("Corrupt index pointer (%d)", icx->pindex);
632 		return STATUS_ERROR;
633 	}
634 	return STATUS_OK;
635 }
636 
637 /**
638  * ntfs_index_lookup - find a key in an index and return its index entry
639  * @key:	[IN] key for which to search in the index
640  * @key_len:	[IN] length of @key in bytes
641  * @icx:	[IN/OUT] context describing the index and the returned entry
642  *
643  * Before calling ntfs_index_lookup(), @icx must have been obtained from a
644  * call to ntfs_index_ctx_get().
645  *
646  * Look for the @key in the index specified by the index lookup context @icx.
647  * ntfs_index_lookup() walks the contents of the index looking for the @key.
648  *
649  * If the @key is found in the index, 0 is returned and @icx is setup to
650  * describe the index entry containing the matching @key.  @icx->entry is the
651  * index entry and @icx->data and @icx->data_len are the index entry data and
652  * its length in bytes, respectively.
653  *
654  * If the @key is not found in the index, -1 is returned, errno = ENOENT and
655  * @icx is setup to describe the index entry whose key collates immediately
656  * after the search @key, i.e. this is the position in the index at which
657  * an index entry with a key of @key would need to be inserted.
658  *
659  * If an error occurs return -1, set errno to error code and @icx is left
660  * untouched.
661  *
662  * When finished with the entry and its data, call ntfs_index_ctx_put() to free
663  * the context and other associated resources.
664  *
665  * If the index entry was modified, call ntfs_index_entry_mark_dirty() before
666  * the call to ntfs_index_ctx_put() to ensure that the changes are written
667  * to disk.
668  */
669 int ntfs_index_lookup(const void *key, const int key_len, ntfs_index_context *icx)
670 {
671 	VCN old_vcn, vcn;
672 	ntfs_inode *ni = icx->ni;
673 	INDEX_ROOT *ir;
674 	INDEX_ENTRY *ie;
675 	INDEX_BLOCK *ib = NULL;
676 	int ret, err = 0;
677 
678 	ntfs_log_trace("Entering\n");
679 
680 	if (!key || key_len <= 0) {
681 		errno = EINVAL;
682 		ntfs_log_perror("key: %p  key_len: %d", key, key_len);
683 		return -1;
684 	}
685 
686 	ir = ntfs_ir_lookup(ni, icx->name, icx->name_len, &icx->actx);
687 	if (!ir) {
688 		if (errno == ENOENT)
689 			errno = EIO;
690 		return -1;
691 	}
692 
693 	icx->block_size = le32_to_cpu(ir->index_block_size);
694 	if (icx->block_size < NTFS_BLOCK_SIZE) {
695 		errno = EINVAL;
696 		ntfs_log_perror("Index block size (%d) is smaller than the "
697 				"sector size (%d)", icx->block_size, NTFS_BLOCK_SIZE);
698 		goto err_out;
699 	}
700 
701 	if (ni->vol->cluster_size <= icx->block_size)
702 		icx->vcn_size_bits = ni->vol->cluster_size_bits;
703 	else
704 		icx->vcn_size_bits = NTFS_BLOCK_SIZE_BITS;
705 			/* get the appropriate collation function */
706 	icx->collate = ntfs_get_collate_function(ir->collation_rule);
707 	if (!icx->collate) {
708 		err = errno = EOPNOTSUPP;
709 		ntfs_log_perror("Unknown collation rule 0x%x",
710 				(unsigned)le32_to_cpu(ir->collation_rule));
711 		goto err_out;
712 	}
713 
714 	old_vcn = VCN_INDEX_ROOT_PARENT;
715 	/*
716 	 * FIXME: check for both ir and ib that the first index entry is
717 	 * within the index block.
718 	 */
719 	ret = ntfs_ie_lookup(key, key_len, icx, &ir->index, &vcn, &ie);
720 	if (ret == STATUS_ERROR) {
721 		err = errno;
722 		goto err_out;
723 	}
724 
725 	icx->ir = ir;
726 
727 	if (ret != STATUS_KEEP_SEARCHING) {
728 		/* STATUS_OK or STATUS_NOT_FOUND */
729 		err = errno;
730 		icx->is_in_root = TRUE;
731 		icx->parent_vcn[icx->pindex] = old_vcn;
732 		goto done;
733 	}
734 
735 	/* Child node present, descend into it. */
736 
737 	icx->ia_na = ntfs_ia_open(icx, ni);
738 	if (!icx->ia_na)
739 		goto err_out;
740 
741 	ib = ntfs_malloc(icx->block_size);
742 	if (!ib) {
743 		err = errno;
744 		goto err_out;
745 	}
746 
747 descend_into_child_node:
748 
749 	icx->parent_vcn[icx->pindex] = old_vcn;
750 	if (ntfs_icx_parent_inc(icx)) {
751 		err = errno;
752 		goto err_out;
753 	}
754 	old_vcn = vcn;
755 
756 	ntfs_log_debug("Descend into node with VCN %lld\n", (long long)vcn);
757 
758 	if (ntfs_ib_read(icx, vcn, ib))
759 		goto err_out;
760 
761 	ret = ntfs_ie_lookup(key, key_len, icx, &ib->index, &vcn, &ie);
762 	if (ret != STATUS_KEEP_SEARCHING) {
763 		err = errno;
764 		if (ret == STATUS_ERROR)
765 			goto err_out;
766 
767 		/* STATUS_OK or STATUS_NOT_FOUND */
768 		icx->is_in_root = FALSE;
769 		icx->ib = ib;
770 		icx->parent_vcn[icx->pindex] = vcn;
771 		goto done;
772 	}
773 
774 	if ((ib->index.ih_flags & NODE_MASK) == LEAF_NODE) {
775 		ntfs_log_error("Index entry with child node found in a leaf "
776 			       "node in inode 0x%llx.\n",
777 			       (unsigned long long)ni->mft_no);
778 		goto err_out;
779 	}
780 
781 	goto descend_into_child_node;
782 err_out:
783 	free(ib);
784 	if (!err)
785 		err = EIO;
786 	errno = err;
787 	return -1;
788 done:
789 	icx->entry = ie;
790 	icx->data = (u8 *)ie + offsetof(INDEX_ENTRY, key);
791 	icx->data_len = le16_to_cpu(ie->key_length);
792 	ntfs_log_trace("Done.\n");
793 	if (err) {
794 		errno = err;
795 		return -1;
796 	}
797 	return 0;
798 
799 }
800 
801 static INDEX_BLOCK *ntfs_ib_alloc(VCN ib_vcn, u32 ib_size,
802 				  INDEX_HEADER_FLAGS node_type)
803 {
804 	INDEX_BLOCK *ib;
805 	int ih_size = sizeof(INDEX_HEADER);
806 
807 	ntfs_log_trace("ib_vcn: %lld ib_size: %u\n", (long long)ib_vcn, ib_size);
808 
809 	ib = ntfs_calloc(ib_size);
810 	if (!ib)
811 		return NULL;
812 
813 	ib->magic = magic_INDX;
814 	ib->usa_ofs = cpu_to_le16(sizeof(INDEX_BLOCK));
815 	ib->usa_count = cpu_to_le16(ib_size / NTFS_BLOCK_SIZE + 1);
816 	/* Set USN to 1 */
817 	*(u16 *)((char *)ib + le16_to_cpu(ib->usa_ofs)) = cpu_to_le16(1);
818 	ib->lsn = cpu_to_le64(0);
819 
820 	ib->index_block_vcn = cpu_to_sle64(ib_vcn);
821 
822 	ib->index.entries_offset = cpu_to_le32((ih_size +
823 			le16_to_cpu(ib->usa_count) * 2 + 7) & ~7);
824 	ib->index.index_length = 0;
825 	ib->index.allocated_size = cpu_to_le32(ib_size -
826 					       (sizeof(INDEX_BLOCK) - ih_size));
827 	ib->index.ih_flags = node_type;
828 
829 	return ib;
830 }
831 
832 /**
833  *  Find the median by going through all the entries
834  */
835 static INDEX_ENTRY *ntfs_ie_get_median(INDEX_HEADER *ih)
836 {
837 	INDEX_ENTRY *ie, *ie_start;
838 	u8 *ie_end;
839 	int i = 0, median;
840 
841 	ntfs_log_trace("Entering\n");
842 
843 	ie = ie_start = ntfs_ie_get_first(ih);
844 	ie_end   = (u8 *)ntfs_ie_get_end(ih);
845 
846 	while ((u8 *)ie < ie_end && !ntfs_ie_end(ie)) {
847 		ie = ntfs_ie_get_next(ie);
848 		i++;
849 	}
850 	/*
851 	 * NOTE: this could be also the entry at the half of the index block.
852 	 */
853 	median = i / 2 - 1;
854 
855 	ntfs_log_trace("Entries: %d  median: %d\n", i, median);
856 
857 	for (i = 0, ie = ie_start; i <= median; i++)
858 		ie = ntfs_ie_get_next(ie);
859 
860 	return ie;
861 }
862 
863 static s64 ntfs_ibm_vcn_to_pos(ntfs_index_context *icx, VCN vcn)
864 {
865 	return ntfs_ib_vcn_to_pos(icx, vcn) / icx->block_size;
866 }
867 
868 static s64 ntfs_ibm_pos_to_vcn(ntfs_index_context *icx, s64 pos)
869 {
870 	return ntfs_ib_pos_to_vcn(icx, pos * icx->block_size);
871 }
872 
873 static int ntfs_ibm_add(ntfs_index_context *icx)
874 {
875 	u8 bmp[8];
876 
877 	ntfs_log_trace("Entering\n");
878 
879 	if (ntfs_attr_exist(icx->ni, AT_BITMAP, icx->name, icx->name_len))
880 		return STATUS_OK;
881 	/*
882 	 * AT_BITMAP must be at least 8 bytes.
883 	 */
884 	memset(bmp, 0, sizeof(bmp));
885 	if (ntfs_attr_add(icx->ni, AT_BITMAP, icx->name, icx->name_len,
886 			  bmp, sizeof(bmp))) {
887 		ntfs_log_perror("Failed to add AT_BITMAP");
888 		return STATUS_ERROR;
889 	}
890 
891 	return STATUS_OK;
892 }
893 
894 static int ntfs_ibm_modify(ntfs_index_context *icx, VCN vcn, int set)
895 {
896 	u8 byte;
897 	s64 pos = ntfs_ibm_vcn_to_pos(icx, vcn);
898 	u32 bpos = pos / 8;
899 	u32 bit = 1 << (pos % 8);
900 	ntfs_attr *na;
901 	int ret = STATUS_ERROR;
902 
903 	ntfs_log_trace("%s vcn: %lld\n", set ? "set" : "clear", (long long)vcn);
904 
905 	na = ntfs_attr_open(icx->ni, AT_BITMAP,  icx->name, icx->name_len);
906 	if (!na) {
907 		ntfs_log_perror("Failed to open $BITMAP attribute");
908 		return -1;
909 	}
910 
911 	if (set) {
912 		if (na->data_size < bpos + 1) {
913 			if (ntfs_attr_truncate(na, (na->data_size + 8) & ~7)) {
914 				ntfs_log_perror("Failed to truncate AT_BITMAP");
915 				goto err_na;
916 			}
917 		}
918 	}
919 
920 	if (ntfs_attr_pread(na, bpos, 1, &byte) != 1) {
921 		ntfs_log_perror("Failed to read $BITMAP");
922 		goto err_na;
923 	}
924 
925 	if (set)
926 		byte |= bit;
927 	else
928 		byte &= ~bit;
929 
930 	if (ntfs_attr_pwrite(na, bpos, 1, &byte) != 1) {
931 		ntfs_log_perror("Failed to write $Bitmap");
932 		goto err_na;
933 	}
934 
935 	ret = STATUS_OK;
936 err_na:
937 	ntfs_attr_close(na);
938 	return ret;
939 }
940 
941 
942 static int ntfs_ibm_set(ntfs_index_context *icx, VCN vcn)
943 {
944 	return ntfs_ibm_modify(icx, vcn, 1);
945 }
946 
947 static int ntfs_ibm_clear(ntfs_index_context *icx, VCN vcn)
948 {
949 	return ntfs_ibm_modify(icx, vcn, 0);
950 }
951 
952 static VCN ntfs_ibm_get_free(ntfs_index_context *icx)
953 {
954 	u8 *bm;
955 	int bit;
956 	s64 vcn, byte, size;
957 
958 	ntfs_log_trace("Entering\n");
959 
960 	bm = ntfs_attr_readall(icx->ni, AT_BITMAP,  icx->name, icx->name_len,
961 			       &size);
962 	if (!bm)
963 		return (VCN)-1;
964 
965 	for (byte = 0; byte < size; byte++) {
966 
967 		if (bm[byte] == 255)
968 			continue;
969 
970 		for (bit = 0; bit < 8; bit++) {
971 			if (!(bm[byte] & (1 << bit))) {
972 				vcn = ntfs_ibm_pos_to_vcn(icx, byte * 8 + bit);
973 				goto out;
974 			}
975 		}
976 	}
977 
978 	vcn = ntfs_ibm_pos_to_vcn(icx, size * 8);
979 out:
980 	ntfs_log_trace("allocated vcn: %lld\n", (long long)vcn);
981 
982 	if (ntfs_ibm_set(icx, vcn))
983 		vcn = (VCN)-1;
984 
985 	free(bm);
986 	return vcn;
987 }
988 
989 static INDEX_BLOCK *ntfs_ir_to_ib(INDEX_ROOT *ir, VCN ib_vcn)
990 {
991 	INDEX_BLOCK *ib;
992 	INDEX_ENTRY *ie_last;
993 	char *ies_start, *ies_end;
994 	int i;
995 
996 	ntfs_log_trace("Entering\n");
997 
998 	ib = ntfs_ib_alloc(ib_vcn, le32_to_cpu(ir->index_block_size), LEAF_NODE);
999 	if (!ib)
1000 		return NULL;
1001 
1002 	ies_start = (char *)ntfs_ie_get_first(&ir->index);
1003 	ies_end   = (char *)ntfs_ie_get_end(&ir->index);
1004 	ie_last   = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
1005 	/*
1006 	 * Copy all entries, including the termination entry
1007 	 * as well, which can never have any data.
1008 	 */
1009 	i = (char *)ie_last - ies_start + le16_to_cpu(ie_last->length);
1010 	memcpy(ntfs_ie_get_first(&ib->index), ies_start, i);
1011 
1012 	ib->index.ih_flags = ir->index.ih_flags;
1013 	ib->index.index_length = cpu_to_le32(i +
1014 			le32_to_cpu(ib->index.entries_offset));
1015 	return ib;
1016 }
1017 
1018 static void ntfs_ir_nill(INDEX_ROOT *ir)
1019 {
1020 	INDEX_ENTRY *ie_last;
1021 	char *ies_start, *ies_end;
1022 
1023 	ntfs_log_trace("Entering\n");
1024 	/*
1025 	 * TODO: This function could be much simpler.
1026 	 */
1027 	ies_start = (char *)ntfs_ie_get_first(&ir->index);
1028 	ies_end   = (char *)ntfs_ie_get_end(&ir->index);
1029 	ie_last   = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
1030 	/*
1031 	 * Move the index root termination entry forward
1032 	 */
1033 	if ((char *)ie_last > ies_start) {
1034 		memmove(ies_start, (char *)ie_last, le16_to_cpu(ie_last->length));
1035 		ie_last = (INDEX_ENTRY *)ies_start;
1036 	}
1037 }
1038 
1039 static int ntfs_ib_copy_tail(ntfs_index_context *icx, INDEX_BLOCK *src,
1040 			     INDEX_ENTRY *median, VCN new_vcn)
1041 {
1042 	u8 *ies_end;
1043 	INDEX_ENTRY *ie_head;		/* first entry after the median */
1044 	int tail_size, ret;
1045 	INDEX_BLOCK *dst;
1046 
1047 	ntfs_log_trace("Entering\n");
1048 
1049 	dst = ntfs_ib_alloc(new_vcn, icx->block_size,
1050 			    src->index.ih_flags & NODE_MASK);
1051 	if (!dst)
1052 		return STATUS_ERROR;
1053 
1054 	ie_head = ntfs_ie_get_next(median);
1055 
1056 	ies_end = (u8 *)ntfs_ie_get_end(&src->index);
1057 	tail_size = ies_end - (u8 *)ie_head;
1058 	memcpy(ntfs_ie_get_first(&dst->index), ie_head, tail_size);
1059 
1060 	dst->index.index_length = cpu_to_le32(tail_size +
1061 					      le32_to_cpu(dst->index.entries_offset));
1062 	ret = ntfs_ib_write(icx, dst);
1063 
1064 	free(dst);
1065 	return ret;
1066 }
1067 
1068 static int ntfs_ib_cut_tail(ntfs_index_context *icx, INDEX_BLOCK *ib,
1069 			    INDEX_ENTRY *ie)
1070 {
1071 	char *ies_start, *ies_end;
1072 	INDEX_ENTRY *ie_last;
1073 
1074 	ntfs_log_trace("Entering\n");
1075 
1076 	ies_start = (char *)ntfs_ie_get_first(&ib->index);
1077 	ies_end   = (char *)ntfs_ie_get_end(&ib->index);
1078 
1079 	ie_last   = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
1080 	if (ie_last->ie_flags & INDEX_ENTRY_NODE)
1081 		ntfs_ie_set_vcn(ie_last, ntfs_ie_get_vcn(ie));
1082 
1083 	memcpy(ie, ie_last, le16_to_cpu(ie_last->length));
1084 
1085 	ib->index.index_length = cpu_to_le32(((char *)ie - ies_start) +
1086 		le16_to_cpu(ie->length) + le32_to_cpu(ib->index.entries_offset));
1087 
1088 	if (ntfs_ib_write(icx, ib))
1089 		return STATUS_ERROR;
1090 
1091 	return STATUS_OK;
1092 }
1093 
1094 static int ntfs_ia_add(ntfs_index_context *icx)
1095 {
1096 	ntfs_log_trace("Entering\n");
1097 
1098 	if (ntfs_ibm_add(icx))
1099 		return -1;
1100 
1101 	if (!ntfs_attr_exist(icx->ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len)) {
1102 
1103 		if (ntfs_attr_add(icx->ni, AT_INDEX_ALLOCATION, icx->name,
1104 				  icx->name_len, NULL, 0)) {
1105 			ntfs_log_perror("Failed to add AT_INDEX_ALLOCATION");
1106 			return -1;
1107 		}
1108 	}
1109 
1110 	icx->ia_na = ntfs_ia_open(icx, icx->ni);
1111 	if (!icx->ia_na)
1112 		return -1;
1113 
1114 	return 0;
1115 }
1116 
1117 static int ntfs_ir_reparent(ntfs_index_context *icx)
1118 {
1119 	ntfs_attr_search_ctx *ctx = NULL;
1120 	INDEX_ROOT *ir;
1121 	INDEX_ENTRY *ie;
1122 	INDEX_BLOCK *ib = NULL;
1123 	VCN new_ib_vcn;
1124 	int ix_root_size;
1125 	int ret = STATUS_ERROR;
1126 
1127 	ntfs_log_trace("Entering\n");
1128 
1129 	ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1130 	if (!ir)
1131 		goto out;
1132 
1133 	if ((ir->index.ih_flags & NODE_MASK) == SMALL_INDEX)
1134 		if (ntfs_ia_add(icx))
1135 			goto out;
1136 
1137 	new_ib_vcn = ntfs_ibm_get_free(icx);
1138 	if (new_ib_vcn == -1)
1139 		goto out;
1140 
1141 	ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1142 	if (!ir)
1143 		goto clear_bmp;
1144 
1145 	ib = ntfs_ir_to_ib(ir, new_ib_vcn);
1146 	if (ib == NULL) {
1147 		ntfs_log_perror("Failed to move index root to index block");
1148 		goto clear_bmp;
1149 	}
1150 
1151 	if (ntfs_ib_write(icx, ib))
1152 		goto clear_bmp;
1153 
1154 retry :
1155 	ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len, &ctx);
1156 	if (!ir)
1157 		goto clear_bmp;
1158 
1159 	ntfs_ir_nill(ir);
1160 
1161 	ie = ntfs_ie_get_first(&ir->index);
1162 	ie->ie_flags |= INDEX_ENTRY_NODE;
1163 	ie->length = cpu_to_le16(sizeof(INDEX_ENTRY_HEADER) + sizeof(VCN));
1164 
1165 	ir->index.ih_flags = LARGE_INDEX;
1166 	ir->index.index_length = cpu_to_le32(le32_to_cpu(ir->index.entries_offset)
1167 					     + le16_to_cpu(ie->length));
1168 	ir->index.allocated_size = ir->index.index_length;
1169 	ix_root_size = sizeof(INDEX_ROOT) - sizeof(INDEX_HEADER)
1170 			+ le32_to_cpu(ir->index.allocated_size);
1171 	if (ntfs_resident_attr_value_resize(ctx->mrec, ctx->attr,
1172 					ix_root_size)) {
1173 			/*
1174 			 * When there is no space to build a non-resident
1175 			 * index, we may have to move the root to an extent
1176 			 */
1177 		if ((errno == ENOSPC)
1178 		    && !ctx->al_entry
1179 		    && !ntfs_inode_add_attrlist(icx->ni)) {
1180 			ntfs_attr_put_search_ctx(ctx);
1181 			ctx = (ntfs_attr_search_ctx*)NULL;
1182 			ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len,
1183 							&ctx);
1184 			if (ir
1185 			    && !ntfs_attr_record_move_away(ctx, ix_root_size
1186 				    - le32_to_cpu(ctx->attr->value_length))) {
1187 				ntfs_attr_put_search_ctx(ctx);
1188 				ctx = (ntfs_attr_search_ctx*)NULL;
1189 				goto retry;
1190 			}
1191 		}
1192 		/* FIXME: revert index root */
1193 		goto clear_bmp;
1194 	}
1195 	/*
1196 	 *  FIXME: do it earlier if we have enough space in IR (should always),
1197 	 *  so in error case we wouldn't lose the IB.
1198 	 */
1199 	ntfs_ie_set_vcn(ie, new_ib_vcn);
1200 
1201 	ret = STATUS_OK;
1202 err_out:
1203 	free(ib);
1204 	ntfs_attr_put_search_ctx(ctx);
1205 out:
1206 	return ret;
1207 clear_bmp:
1208 	ntfs_ibm_clear(icx, new_ib_vcn);
1209 	goto err_out;
1210 }
1211 
1212 /**
1213  * ntfs_ir_truncate - Truncate index root attribute
1214  *
1215  * Returns STATUS_OK, STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT or STATUS_ERROR.
1216  */
1217 static int ntfs_ir_truncate(ntfs_index_context *icx, int data_size)
1218 {
1219 	ntfs_attr *na;
1220 	int ret;
1221 
1222 	ntfs_log_trace("Entering\n");
1223 
1224 	na = ntfs_attr_open(icx->ni, AT_INDEX_ROOT, icx->name, icx->name_len);
1225 	if (!na) {
1226 		ntfs_log_perror("Failed to open INDEX_ROOT");
1227 		return STATUS_ERROR;
1228 	}
1229 	/*
1230 	 *  INDEX_ROOT must be resident and its entries can be moved to
1231 	 *  INDEX_BLOCK, so ENOSPC isn't a real error.
1232 	 */
1233 	ret = ntfs_attr_truncate(na, data_size + offsetof(INDEX_ROOT, index));
1234 	if (ret == STATUS_OK) {
1235 
1236 		icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1237 		if (!icx->ir)
1238 			return STATUS_ERROR;
1239 
1240 		icx->ir->index.allocated_size = cpu_to_le32(data_size);
1241 
1242 	} else if (ret == STATUS_ERROR)
1243 		ntfs_log_perror("Failed to truncate INDEX_ROOT");
1244 
1245 	ntfs_attr_close(na);
1246 	return ret;
1247 }
1248 
1249 /**
1250  * ntfs_ir_make_space - Make more space for the index root attribute
1251  *
1252  * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
1253  * On error return STATUS_ERROR.
1254  */
1255 static int ntfs_ir_make_space(ntfs_index_context *icx, int data_size)
1256 {
1257 	int ret;
1258 
1259 	ntfs_log_trace("Entering\n");
1260 
1261 	ret = ntfs_ir_truncate(icx, data_size);
1262 	if (ret == STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT) {
1263 
1264 		ret = ntfs_ir_reparent(icx);
1265 		if (ret == STATUS_OK)
1266 			ret = STATUS_KEEP_SEARCHING;
1267 		else
1268 			ntfs_log_perror("Failed to nodify INDEX_ROOT");
1269 	}
1270 
1271 	return ret;
1272 }
1273 
1274 /*
1275  * NOTE: 'ie' must be a copy of a real index entry.
1276  */
1277 static int ntfs_ie_add_vcn(INDEX_ENTRY **ie)
1278 {
1279 	INDEX_ENTRY *p, *old = *ie;
1280 
1281 	old->length = cpu_to_le16(le16_to_cpu(old->length) + sizeof(VCN));
1282 	p = realloc(old, le16_to_cpu(old->length));
1283 	if (!p)
1284 		return STATUS_ERROR;
1285 
1286 	p->ie_flags |= INDEX_ENTRY_NODE;
1287 	*ie = p;
1288 
1289 	return STATUS_OK;
1290 }
1291 
1292 static int ntfs_ih_insert(INDEX_HEADER *ih, INDEX_ENTRY *orig_ie, VCN new_vcn,
1293 			  int pos)
1294 {
1295 	INDEX_ENTRY *ie_node, *ie;
1296 	int ret = STATUS_ERROR;
1297 	VCN old_vcn;
1298 
1299 	ntfs_log_trace("Entering\n");
1300 
1301 	ie = ntfs_ie_dup(orig_ie);
1302 	if (!ie)
1303 		return STATUS_ERROR;
1304 
1305 	if (!(ie->ie_flags & INDEX_ENTRY_NODE))
1306 		if (ntfs_ie_add_vcn(&ie))
1307 			goto out;
1308 
1309 	ie_node = ntfs_ie_get_by_pos(ih, pos);
1310 	old_vcn = ntfs_ie_get_vcn(ie_node);
1311 	ntfs_ie_set_vcn(ie_node, new_vcn);
1312 
1313 	ntfs_ie_insert(ih, ie, ie_node);
1314 	ntfs_ie_set_vcn(ie_node, old_vcn);
1315 	ret = STATUS_OK;
1316 out:
1317 	free(ie);
1318 
1319 	return ret;
1320 }
1321 
1322 static VCN ntfs_icx_parent_vcn(ntfs_index_context *icx)
1323 {
1324 	return icx->parent_vcn[icx->pindex];
1325 }
1326 
1327 static VCN ntfs_icx_parent_pos(ntfs_index_context *icx)
1328 {
1329 	return icx->parent_pos[icx->pindex];
1330 }
1331 
1332 
1333 static int ntfs_ir_insert_median(ntfs_index_context *icx, INDEX_ENTRY *median,
1334 				 VCN new_vcn)
1335 {
1336 	u32 new_size;
1337 	int ret;
1338 
1339 	ntfs_log_trace("Entering\n");
1340 
1341 	icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1342 	if (!icx->ir)
1343 		return STATUS_ERROR;
1344 
1345 	new_size = le32_to_cpu(icx->ir->index.index_length) +
1346 			le16_to_cpu(median->length);
1347 	if (!(median->ie_flags & INDEX_ENTRY_NODE))
1348 		new_size += sizeof(VCN);
1349 
1350 	ret = ntfs_ir_make_space(icx, new_size);
1351 	if (ret != STATUS_OK)
1352 		return ret;
1353 
1354 	icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1355 	if (!icx->ir)
1356 		return STATUS_ERROR;
1357 
1358 	return ntfs_ih_insert(&icx->ir->index, median, new_vcn,
1359 			      ntfs_icx_parent_pos(icx));
1360 }
1361 
1362 static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib);
1363 
1364 /**
1365  * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
1366  * On error return STATUS_ERROR.
1367  */
1368 static int ntfs_ib_insert(ntfs_index_context *icx, INDEX_ENTRY *ie, VCN new_vcn)
1369 {
1370 	INDEX_BLOCK *ib;
1371 	u32 idx_size, allocated_size;
1372 	int err = STATUS_ERROR;
1373 	VCN old_vcn;
1374 
1375 	ntfs_log_trace("Entering\n");
1376 
1377 	ib = ntfs_malloc(icx->block_size);
1378 	if (!ib)
1379 		return -1;
1380 
1381 	old_vcn = ntfs_icx_parent_vcn(icx);
1382 
1383 	if (ntfs_ib_read(icx, old_vcn, ib))
1384 		goto err_out;
1385 
1386 	idx_size       = le32_to_cpu(ib->index.index_length);
1387 	allocated_size = le32_to_cpu(ib->index.allocated_size);
1388 	/* FIXME: sizeof(VCN) should be included only if ie has no VCN */
1389 	if (idx_size + le16_to_cpu(ie->length) + sizeof(VCN) > allocated_size) {
1390 		err = ntfs_ib_split(icx, ib);
1391 		if (err == STATUS_OK)
1392 			err = STATUS_KEEP_SEARCHING;
1393 		goto err_out;
1394 	}
1395 
1396 	if (ntfs_ih_insert(&ib->index, ie, new_vcn, ntfs_icx_parent_pos(icx)))
1397 		goto err_out;
1398 
1399 	if (ntfs_ib_write(icx, ib))
1400 		goto err_out;
1401 
1402 	err = STATUS_OK;
1403 err_out:
1404 	free(ib);
1405 	return err;
1406 }
1407 
1408 /**
1409  * ntfs_ib_split - Split an index block
1410  *
1411  * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
1412  * On error return is STATUS_ERROR.
1413  */
1414 static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib)
1415 {
1416 	INDEX_ENTRY *median;
1417 	VCN new_vcn;
1418 	int ret;
1419 
1420 	ntfs_log_trace("Entering\n");
1421 
1422 	if (ntfs_icx_parent_dec(icx))
1423 		return STATUS_ERROR;
1424 
1425 	median  = ntfs_ie_get_median(&ib->index);
1426 	new_vcn = ntfs_ibm_get_free(icx);
1427 	if (new_vcn == -1)
1428 		return STATUS_ERROR;
1429 
1430 	if (ntfs_ib_copy_tail(icx, ib, median, new_vcn)) {
1431 		ntfs_ibm_clear(icx, new_vcn);
1432 		return STATUS_ERROR;
1433 	}
1434 
1435 	if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
1436 		ret = ntfs_ir_insert_median(icx, median, new_vcn);
1437 	else
1438 		ret = ntfs_ib_insert(icx, median, new_vcn);
1439 
1440 	if (ret != STATUS_OK) {
1441 		ntfs_ibm_clear(icx, new_vcn);
1442 		return ret;
1443 	}
1444 
1445 	ret = ntfs_ib_cut_tail(icx, ib, median);
1446 
1447 	return ret;
1448 }
1449 
1450 /* JPA static */
1451 int ntfs_ie_add(ntfs_index_context *icx, INDEX_ENTRY *ie)
1452 {
1453 	INDEX_HEADER *ih;
1454 	int allocated_size, new_size;
1455 	int ret = STATUS_ERROR;
1456 
1457 #ifdef DEBUG
1458 /* removed by JPA to make function usable for security indexes
1459 	char *fn;
1460 	fn = ntfs_ie_filename_get(ie);
1461 	ntfs_log_trace("file: '%s'\n", fn);
1462 	ntfs_attr_name_free(&fn);
1463 */
1464 #endif
1465 
1466 	while (1) {
1467 
1468 		if (!ntfs_index_lookup(&ie->key, le16_to_cpu(ie->key_length), icx)) {
1469 			errno = EEXIST;
1470 			ntfs_log_perror("Index already have such entry");
1471 			goto err_out;
1472 		}
1473 		if (errno != ENOENT) {
1474 			ntfs_log_perror("Failed to find place for new entry");
1475 			goto err_out;
1476 		}
1477 
1478 		if (icx->is_in_root)
1479 			ih = &icx->ir->index;
1480 		else
1481 			ih = &icx->ib->index;
1482 
1483 		allocated_size = le32_to_cpu(ih->allocated_size);
1484 		new_size = le32_to_cpu(ih->index_length) + le16_to_cpu(ie->length);
1485 
1486 		if (new_size <= allocated_size)
1487 			break;
1488 
1489 		ntfs_log_trace("index block sizes: allocated: %d  needed: %d\n",
1490 			       allocated_size, new_size);
1491 
1492 		if (icx->is_in_root) {
1493 			if (ntfs_ir_make_space(icx, new_size) == STATUS_ERROR)
1494 				goto err_out;
1495 		} else {
1496 			if (ntfs_ib_split(icx, icx->ib) == STATUS_ERROR)
1497 				goto err_out;
1498 		}
1499 
1500 		ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1501 		ntfs_index_ctx_reinit(icx);
1502 	}
1503 
1504 	ntfs_ie_insert(ih, ie, icx->entry);
1505 	ntfs_index_entry_mark_dirty(icx);
1506 
1507 	ret = STATUS_OK;
1508 err_out:
1509 	ntfs_log_trace("%s\n", ret ? "Failed" : "Done");
1510 	return ret;
1511 }
1512 
1513 /**
1514  * ntfs_index_add_filename - add filename to directory index
1515  * @ni:		ntfs inode describing directory to which index add filename
1516  * @fn:		FILE_NAME attribute to add
1517  * @mref:	reference of the inode which @fn describes
1518  *
1519  * Return 0 on success or -1 on error with errno set to the error code.
1520  */
1521 int ntfs_index_add_filename(ntfs_inode *ni, FILE_NAME_ATTR *fn, MFT_REF mref)
1522 {
1523 	INDEX_ENTRY *ie;
1524 	ntfs_index_context *icx;
1525 	int fn_size, ie_size, err, ret = -1;
1526 
1527 	ntfs_log_trace("Entering\n");
1528 
1529 	if (!ni || !fn) {
1530 		ntfs_log_error("Invalid arguments.\n");
1531 		errno = EINVAL;
1532 		return -1;
1533 	}
1534 
1535 	fn_size = (fn->file_name_length * sizeof(ntfschar)) +
1536 			sizeof(FILE_NAME_ATTR);
1537 	ie_size = (sizeof(INDEX_ENTRY_HEADER) + fn_size + 7) & ~7;
1538 
1539 	ie = ntfs_calloc(ie_size);
1540 	if (!ie)
1541 		return -1;
1542 
1543 	ie->indexed_file = cpu_to_le64(mref);
1544 	ie->length 	 = cpu_to_le16(ie_size);
1545 	ie->key_length 	 = cpu_to_le16(fn_size);
1546 	memcpy(&ie->key, fn, fn_size);
1547 
1548 	icx = ntfs_index_ctx_get(ni, NTFS_INDEX_I30, 4);
1549 	if (!icx)
1550 		goto out;
1551 
1552 	ret = ntfs_ie_add(icx, ie);
1553 	err = errno;
1554 	ntfs_index_ctx_put(icx);
1555 	errno = err;
1556 out:
1557 	free(ie);
1558 	return ret;
1559 }
1560 
1561 static int ntfs_ih_takeout(ntfs_index_context *icx, INDEX_HEADER *ih,
1562 			   INDEX_ENTRY *ie, INDEX_BLOCK *ib)
1563 {
1564 	INDEX_ENTRY *ie_roam;
1565 	int ret = STATUS_ERROR;
1566 
1567 	ntfs_log_trace("Entering\n");
1568 
1569 	ie_roam = ntfs_ie_dup_novcn(ie);
1570 	if (!ie_roam)
1571 		return STATUS_ERROR;
1572 
1573 	ntfs_ie_delete(ih, ie);
1574 
1575 	if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
1576 		ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1577 	else
1578 		if (ntfs_ib_write(icx, ib))
1579 			goto out;
1580 
1581 	ntfs_index_ctx_reinit(icx);
1582 
1583 	ret = ntfs_ie_add(icx, ie_roam);
1584 out:
1585 	free(ie_roam);
1586 	return ret;
1587 }
1588 
1589 /**
1590  *  Used if an empty index block to be deleted has END entry as the parent
1591  *  in the INDEX_ROOT which is the only one there.
1592  */
1593 static void ntfs_ir_leafify(ntfs_index_context *icx, INDEX_HEADER *ih)
1594 {
1595 	INDEX_ENTRY *ie;
1596 
1597 	ntfs_log_trace("Entering\n");
1598 
1599 	ie = ntfs_ie_get_first(ih);
1600 	ie->ie_flags &= ~INDEX_ENTRY_NODE;
1601 	ie->length = cpu_to_le16(le16_to_cpu(ie->length) - sizeof(VCN));
1602 
1603 	ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) - sizeof(VCN));
1604 	ih->ih_flags &= ~LARGE_INDEX;
1605 
1606 	/* Not fatal error */
1607 	ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
1608 }
1609 
1610 /**
1611  *  Used if an empty index block to be deleted has END entry as the parent
1612  *  in the INDEX_ROOT which is not the only one there.
1613  */
1614 static int ntfs_ih_reparent_end(ntfs_index_context *icx, INDEX_HEADER *ih,
1615 				INDEX_BLOCK *ib)
1616 {
1617 	INDEX_ENTRY *ie, *ie_prev;
1618 
1619 	ntfs_log_trace("Entering\n");
1620 
1621 	ie = ntfs_ie_get_by_pos(ih, ntfs_icx_parent_pos(icx));
1622 	ie_prev = ntfs_ie_prev(ih, ie);
1623 
1624 	ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(ie_prev));
1625 
1626 	return ntfs_ih_takeout(icx, ih, ie_prev, ib);
1627 }
1628 
1629 static int ntfs_index_rm_leaf(ntfs_index_context *icx)
1630 {
1631 	INDEX_BLOCK *ib = NULL;
1632 	INDEX_HEADER *parent_ih;
1633 	INDEX_ENTRY *ie;
1634 	int ret = STATUS_ERROR;
1635 
1636 	ntfs_log_trace("pindex: %d\n", icx->pindex);
1637 
1638 	if (ntfs_icx_parent_dec(icx))
1639 		return STATUS_ERROR;
1640 
1641 	if (ntfs_ibm_clear(icx, icx->parent_vcn[icx->pindex + 1]))
1642 		return STATUS_ERROR;
1643 
1644 	if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
1645 		parent_ih = &icx->ir->index;
1646 	else {
1647 		ib = ntfs_malloc(icx->block_size);
1648 		if (!ib)
1649 			return STATUS_ERROR;
1650 
1651 		if (ntfs_ib_read(icx, ntfs_icx_parent_vcn(icx), ib))
1652 			goto out;
1653 
1654 		parent_ih = &ib->index;
1655 	}
1656 
1657 	ie = ntfs_ie_get_by_pos(parent_ih, ntfs_icx_parent_pos(icx));
1658 	if (!ntfs_ie_end(ie)) {
1659 		ret = ntfs_ih_takeout(icx, parent_ih, ie, ib);
1660 		goto out;
1661 	}
1662 
1663 	if (ntfs_ih_zero_entry(parent_ih)) {
1664 
1665 		if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) {
1666 			ntfs_ir_leafify(icx, parent_ih);
1667 			goto ok;
1668 		}
1669 
1670 		ret = ntfs_index_rm_leaf(icx);
1671 		goto out;
1672 	}
1673 
1674 	if (ntfs_ih_reparent_end(icx, parent_ih, ib))
1675 		goto out;
1676 ok:
1677 	ret = STATUS_OK;
1678 out:
1679 	free(ib);
1680 	return ret;
1681 }
1682 
1683 static int ntfs_index_rm_node(ntfs_index_context *icx)
1684 {
1685 	int entry_pos, pindex;
1686 	VCN vcn;
1687 	INDEX_BLOCK *ib = NULL;
1688 	INDEX_ENTRY *ie_succ, *ie, *entry = icx->entry;
1689 	INDEX_HEADER *ih;
1690 	u32 new_size;
1691 	int delta, ret = STATUS_ERROR;
1692 
1693 	ntfs_log_trace("Entering\n");
1694 
1695 	if (!icx->ia_na) {
1696 		icx->ia_na = ntfs_ia_open(icx, icx->ni);
1697 		if (!icx->ia_na)
1698 			return STATUS_ERROR;
1699 	}
1700 
1701 	ib = ntfs_malloc(icx->block_size);
1702 	if (!ib)
1703 		return STATUS_ERROR;
1704 
1705 	ie_succ = ntfs_ie_get_next(icx->entry);
1706 	entry_pos = icx->parent_pos[icx->pindex]++;
1707 	pindex = icx->pindex;
1708 descend:
1709 	vcn = ntfs_ie_get_vcn(ie_succ);
1710 	if (ntfs_ib_read(icx, vcn, ib))
1711 		goto out;
1712 
1713 	ie_succ = ntfs_ie_get_first(&ib->index);
1714 
1715 	if (ntfs_icx_parent_inc(icx))
1716 		goto out;
1717 
1718 	icx->parent_vcn[icx->pindex] = vcn;
1719 	icx->parent_pos[icx->pindex] = 0;
1720 
1721 	if ((ib->index.ih_flags & NODE_MASK) == INDEX_NODE)
1722 		goto descend;
1723 
1724 	if (ntfs_ih_zero_entry(&ib->index)) {
1725 		errno = EIO;
1726 		ntfs_log_perror("Empty index block");
1727 		goto out;
1728 	}
1729 
1730 	ie = ntfs_ie_dup(ie_succ);
1731 	if (!ie)
1732 		goto out;
1733 
1734 	if (ntfs_ie_add_vcn(&ie))
1735 		goto out2;
1736 
1737 	ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(icx->entry));
1738 
1739 	if (icx->is_in_root)
1740 		ih = &icx->ir->index;
1741 	else
1742 		ih = &icx->ib->index;
1743 
1744 	delta = le16_to_cpu(ie->length) - le16_to_cpu(icx->entry->length);
1745 	new_size = le32_to_cpu(ih->index_length) + delta;
1746 	if (delta > 0) {
1747 		if (icx->is_in_root) {
1748 			ret = ntfs_ir_make_space(icx, new_size);
1749 			if (ret != STATUS_OK)
1750 				goto out2;
1751 
1752 			ih = &icx->ir->index;
1753 			entry = ntfs_ie_get_by_pos(ih, entry_pos);
1754 
1755 		} else if (new_size > le32_to_cpu(ih->allocated_size)) {
1756 			icx->pindex = pindex;
1757 			ret = ntfs_ib_split(icx, icx->ib);
1758 			if (ret == STATUS_OK)
1759 				ret = STATUS_KEEP_SEARCHING;
1760 			goto out2;
1761 		}
1762 	}
1763 
1764 	ntfs_ie_delete(ih, entry);
1765 	ntfs_ie_insert(ih, ie, entry);
1766 
1767 	if (icx->is_in_root) {
1768 		if (ntfs_ir_truncate(icx, new_size))
1769 			goto out2;
1770 	} else
1771 		if (ntfs_icx_ib_write(icx))
1772 			goto out2;
1773 
1774 	ntfs_ie_delete(&ib->index, ie_succ);
1775 
1776 	if (ntfs_ih_zero_entry(&ib->index)) {
1777 		if (ntfs_index_rm_leaf(icx))
1778 			goto out2;
1779 	} else
1780 		if (ntfs_ib_write(icx, ib))
1781 			goto out2;
1782 
1783 	ret = STATUS_OK;
1784 out2:
1785 	free(ie);
1786 out:
1787 	free(ib);
1788 	return ret;
1789 }
1790 
1791 /**
1792  * ntfs_index_rm - remove entry from the index
1793  * @icx:	index context describing entry to delete
1794  *
1795  * Delete entry described by @icx from the index. Index context is always
1796  * reinitialized after use of this function, so it can be used for index
1797  * lookup once again.
1798  *
1799  * Return 0 on success or -1 on error with errno set to the error code.
1800  */
1801 /*static JPA*/
1802 int ntfs_index_rm(ntfs_index_context *icx)
1803 {
1804 	INDEX_HEADER *ih;
1805 	int err, ret = STATUS_OK;
1806 
1807 	ntfs_log_trace("Entering\n");
1808 
1809 	if (!icx || (!icx->ib && !icx->ir) || ntfs_ie_end(icx->entry)) {
1810 		ntfs_log_error("Invalid arguments.\n");
1811 		errno = EINVAL;
1812 		goto err_out;
1813 	}
1814 	if (icx->is_in_root)
1815 		ih = &icx->ir->index;
1816 	else
1817 		ih = &icx->ib->index;
1818 
1819 	if (icx->entry->ie_flags & INDEX_ENTRY_NODE) {
1820 
1821 		ret = ntfs_index_rm_node(icx);
1822 
1823 	} else if (icx->is_in_root || !ntfs_ih_one_entry(ih)) {
1824 
1825 		ntfs_ie_delete(ih, icx->entry);
1826 
1827 		if (icx->is_in_root) {
1828 			err = ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
1829 			if (err != STATUS_OK)
1830 				goto err_out;
1831 		} else
1832 			if (ntfs_icx_ib_write(icx))
1833 				goto err_out;
1834 	} else {
1835 		if (ntfs_index_rm_leaf(icx))
1836 			goto err_out;
1837 	}
1838 out:
1839 	return ret;
1840 err_out:
1841 	ret = STATUS_ERROR;
1842 	goto out;
1843 }
1844 
1845 int ntfs_index_remove(ntfs_inode *dir_ni, ntfs_inode *ni,
1846 		const void *key, const int keylen)
1847 {
1848 	int ret = STATUS_ERROR;
1849 	ntfs_index_context *icx;
1850 
1851 	icx = ntfs_index_ctx_get(dir_ni, NTFS_INDEX_I30, 4);
1852 	if (!icx)
1853 		return -1;
1854 
1855 	while (1) {
1856 
1857 		if (ntfs_index_lookup(key, keylen, icx))
1858 			goto err_out;
1859 
1860 		if ((((FILE_NAME_ATTR *)icx->data)->file_attributes &
1861 				FILE_ATTR_REPARSE_POINT)
1862 		   && !ntfs_possible_symlink(ni)) {
1863 			errno = EOPNOTSUPP;
1864 			goto err_out;
1865 		}
1866 
1867 		ret = ntfs_index_rm(icx);
1868 		if (ret == STATUS_ERROR)
1869 			goto err_out;
1870 		else if (ret == STATUS_OK)
1871 			break;
1872 
1873 		ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1874 		ntfs_index_ctx_reinit(icx);
1875 	}
1876 
1877 	ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1878 out:
1879 	ntfs_index_ctx_put(icx);
1880 	return ret;
1881 err_out:
1882 	ret = STATUS_ERROR;
1883 	ntfs_log_perror("Delete failed");
1884 	goto out;
1885 }
1886 
1887 /**
1888  * ntfs_index_root_get - read the index root of an attribute
1889  * @ni:		open ntfs inode in which the ntfs attribute resides
1890  * @attr:	attribute for which we want its index root
1891  *
1892  * This function will read the related index root an ntfs attribute.
1893  *
1894  * On success a buffer is allocated with the content of the index root
1895  * and which needs to be freed when it's not needed anymore.
1896  *
1897  * On error NULL is returned with errno set to the error code.
1898  */
1899 INDEX_ROOT *ntfs_index_root_get(ntfs_inode *ni, ATTR_RECORD *attr)
1900 {
1901 	ntfs_attr_search_ctx *ctx;
1902 	ntfschar *name;
1903 	INDEX_ROOT *root = NULL;
1904 
1905 	name = (ntfschar *)((u8 *)attr + le16_to_cpu(attr->name_offset));
1906 
1907 	if (!ntfs_ir_lookup(ni, name, attr->name_length, &ctx))
1908 		return NULL;
1909 
1910 	root = ntfs_malloc(sizeof(INDEX_ROOT));
1911 	if (!root)
1912 		goto out;
1913 
1914 	*root = *((INDEX_ROOT *)((u8 *)ctx->attr +
1915 				le16_to_cpu(ctx->attr->value_offset)));
1916 out:
1917 	ntfs_attr_put_search_ctx(ctx);
1918 	return root;
1919 }
1920 
1921 
1922 /*
1923  *		Walk down the index tree (leaf bound)
1924  *	until there are no subnode in the first index entry
1925  *	returns the entry at the bottom left in subnode
1926  */
1927 
1928 static INDEX_ENTRY *ntfs_index_walk_down(INDEX_ENTRY *ie,
1929 			ntfs_index_context *ictx)
1930 {
1931 	INDEX_ENTRY *entry;
1932 	s64 vcn;
1933 
1934 	entry = ie;
1935 	do {
1936 		vcn = ntfs_ie_get_vcn(entry);
1937 		if (ictx->is_in_root) {
1938 
1939 			/* down from level zero */
1940 
1941 			ictx->ir = (INDEX_ROOT*)NULL;
1942 			ictx->ib = (INDEX_BLOCK*)ntfs_malloc(ictx->block_size);
1943 			ictx->pindex = 1;
1944 			ictx->is_in_root = FALSE;
1945 		} else {
1946 
1947 			/* down from non-zero level */
1948 
1949 			ictx->pindex++;
1950 		}
1951 		ictx->parent_pos[ictx->pindex] = 0;
1952 		ictx->parent_vcn[ictx->pindex] = vcn;
1953 		if (!ntfs_ib_read(ictx,vcn,ictx->ib)) {
1954 			ictx->entry = ntfs_ie_get_first(&ictx->ib->index);
1955 			entry = ictx->entry;
1956 		} else
1957 			entry = (INDEX_ENTRY*)NULL;
1958 	} while (entry && (entry->ie_flags & INDEX_ENTRY_NODE));
1959 	return (entry);
1960 }
1961 
1962 /*
1963  *		Walk up the index tree (root bound)
1964  *	until there is a valid data entry in parent
1965  *	returns the parent entry or NULL if no more parent
1966  */
1967 
1968 static INDEX_ENTRY *ntfs_index_walk_up(INDEX_ENTRY *ie,
1969 			ntfs_index_context *ictx)
1970 {
1971 	INDEX_ENTRY *entry;
1972 	s64 vcn;
1973 
1974 	entry = ie;
1975 	if (ictx->pindex > 0) {
1976 		do {
1977 			ictx->pindex--;
1978 			if (!ictx->pindex) {
1979 
1980 					/* we have reached the root */
1981 
1982 				free(ictx->ib);
1983 				ictx->ib = (INDEX_BLOCK*)NULL;
1984 				ictx->is_in_root = TRUE;
1985 				/* a new search context is to be allocated */
1986 				if (ictx->actx)
1987 					free(ictx->actx);
1988 				ictx->ir = ntfs_ir_lookup(ictx->ni,
1989 					ictx->name, ictx->name_len,
1990 					&ictx->actx);
1991 				if (ictx->ir)
1992 					entry = ntfs_ie_get_by_pos(
1993 						&ictx->ir->index,
1994 						ictx->parent_pos[ictx->pindex]);
1995 				else
1996 					entry = (INDEX_ENTRY*)NULL;
1997 			} else {
1998 					/* up into non-root node */
1999 				vcn = ictx->parent_vcn[ictx->pindex];
2000 				if (!ntfs_ib_read(ictx,vcn,ictx->ib)) {
2001 					entry = ntfs_ie_get_by_pos(
2002 						&ictx->ib->index,
2003 						ictx->parent_pos[ictx->pindex]);
2004 				} else
2005 					entry = (INDEX_ENTRY*)NULL;
2006 			}
2007 		ictx->entry = entry;
2008 		} while (entry && (ictx->pindex > 0)
2009 			 && (entry->ie_flags & INDEX_ENTRY_END));
2010 	} else
2011 		entry = (INDEX_ENTRY*)NULL;
2012 	return (entry);
2013 }
2014 
2015 /*
2016  *		Get next entry in an index according to collating sequence.
2017  *	Must be initialized through a ntfs_index_lookup()
2018  *
2019  *	Returns next entry or NULL if none
2020  *
2021  *	Sample layout :
2022  *
2023  *                 +---+---+---+---+---+---+---+---+    n ptrs to subnodes
2024  *                 |   |   | 10| 25| 33|   |   |   |    n-1 keys in between
2025  *                 +---+---+---+---+---+---+---+---+    no key in last entry
2026  *                              | A | A
2027  *                              | | | +-------------------------------+
2028  *   +--------------------------+ | +-----+                           |
2029  *   |                            +--+    |                           |
2030  *   V                               |    V                           |
2031  * +---+---+---+---+---+---+---+---+ |  +---+---+---+---+---+---+---+---+
2032  * | 11| 12| 13| 14| 15| 16| 17|   | |  | 26| 27| 28| 29| 30| 31| 32|   |
2033  * +---+---+---+---+---+---+---+---+ |  +---+---+---+---+---+---+---+---+
2034  *                               |   |
2035  *       +-----------------------+   |
2036  *       |                           |
2037  *     +---+---+---+---+---+---+---+---+
2038  *     | 18| 19| 20| 21| 22| 23| 24|   |
2039  *     +---+---+---+---+---+---+---+---+
2040  */
2041 
2042 INDEX_ENTRY *ntfs_index_next(INDEX_ENTRY *ie, ntfs_index_context *ictx)
2043 {
2044 	INDEX_ENTRY *next;
2045 	int flags;
2046 
2047 			/*
2048                          * lookup() may have returned an invalid node
2049 			 * when searching for a partial key
2050 			 * if this happens, walk up
2051 			 */
2052 
2053 	if (ie->ie_flags & INDEX_ENTRY_END)
2054 		next = ntfs_index_walk_up(ie, ictx);
2055 	else {
2056 			/*
2057 			 * get next entry in same node
2058                          * there is always one after any entry with data
2059 			 */
2060 
2061 		next = (INDEX_ENTRY*)((char*)ie + le16_to_cpu(ie->length));
2062 		++ictx->parent_pos[ictx->pindex];
2063 		flags = next->ie_flags;
2064 
2065 			/* walk down if it has a subnode */
2066 
2067 		if (flags & INDEX_ENTRY_NODE) {
2068 			next = ntfs_index_walk_down(next,ictx);
2069 		} else {
2070 
2071 				/* walk up it has no subnode, nor data */
2072 
2073 			if (flags & INDEX_ENTRY_END) {
2074 				next = ntfs_index_walk_up(next, ictx);
2075 			}
2076 		}
2077 	}
2078 		/* return NULL if stuck at end of a block */
2079 
2080 	if (next && (next->ie_flags & INDEX_ENTRY_END))
2081 		next = (INDEX_ENTRY*)NULL;
2082 	return (next);
2083 }
2084 
2085 
2086