?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Fixed a constant string concatenation
[ntfs-3g.git] / libntfs-3g / index.c
blob006a6ecd11b5b7105711c9c15dcb33fa50de04f2
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-2020 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->bad_index && !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 leVCN *ntfs_ie_get_vcn_addr(INDEX_ENTRY *ie)
195 {
196 return (leVCN *)((u8 *)ie + le16_to_cpu(ie->length) - sizeof(leVCN));
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_sle64(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_lookup;
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 icx->bad_index = TRUE; /* Force icx->* to be freed */
784 err_lookup:
785 free(ib);
786 if (!err)
787 err = EIO;
788 errno = err;
789 return -1;
790 done:
791 icx->entry = ie;
792 icx->data = (u8 *)ie + offsetof(INDEX_ENTRY, key);
793 icx->data_len = le16_to_cpu(ie->key_length);
794 ntfs_log_trace("Done.\n");
795 if (err) {
796 errno = err;
797 return -1;
798 }
799 return 0;
800
801 }
802
803 static INDEX_BLOCK *ntfs_ib_alloc(VCN ib_vcn, u32 ib_size,
804 INDEX_HEADER_FLAGS node_type)
805 {
806 INDEX_BLOCK *ib;
807 int ih_size = sizeof(INDEX_HEADER);
808
809 ntfs_log_trace("ib_vcn: %lld ib_size: %u\n", (long long)ib_vcn, ib_size);
810
811 ib = ntfs_calloc(ib_size);
812 if (!ib)
813 return NULL;
814
815 ib->magic = magic_INDX;
816 ib->usa_ofs = const_cpu_to_le16(sizeof(INDEX_BLOCK));
817 ib->usa_count = cpu_to_le16(ib_size / NTFS_BLOCK_SIZE + 1);
818 /* Set USN to 1 */
819 *(le16 *)((char *)ib + le16_to_cpu(ib->usa_ofs)) = const_cpu_to_le16(1);
820 ib->lsn = const_cpu_to_sle64(0);
821
822 ib->index_block_vcn = cpu_to_sle64(ib_vcn);
823
824 ib->index.entries_offset = cpu_to_le32((ih_size +
825 le16_to_cpu(ib->usa_count) * 2 + 7) & ~7);
826 ib->index.index_length = const_cpu_to_le32(0);
827 ib->index.allocated_size = cpu_to_le32(ib_size -
828 (sizeof(INDEX_BLOCK) - ih_size));
829 ib->index.ih_flags = node_type;
830
831 return ib;
832 }
833
834 /**
835 * Find the median by going through all the entries
836 */
837 static INDEX_ENTRY *ntfs_ie_get_median(INDEX_HEADER *ih)
838 {
839 INDEX_ENTRY *ie, *ie_start;
840 u8 *ie_end;
841 int i = 0, median;
842
843 ntfs_log_trace("Entering\n");
844
845 ie = ie_start = ntfs_ie_get_first(ih);
846 ie_end = (u8 *)ntfs_ie_get_end(ih);
847
848 while ((u8 *)ie < ie_end && !ntfs_ie_end(ie)) {
849 ie = ntfs_ie_get_next(ie);
850 i++;
851 }
852 /*
853 * NOTE: this could be also the entry at the half of the index block.
854 */
855 median = i / 2 - 1;
856
857 ntfs_log_trace("Entries: %d median: %d\n", i, median);
858
859 for (i = 0, ie = ie_start; i <= median; i++)
860 ie = ntfs_ie_get_next(ie);
861
862 return ie;
863 }
864
865 static s64 ntfs_ibm_vcn_to_pos(ntfs_index_context *icx, VCN vcn)
866 {
867 return ntfs_ib_vcn_to_pos(icx, vcn) / icx->block_size;
868 }
869
870 static s64 ntfs_ibm_pos_to_vcn(ntfs_index_context *icx, s64 pos)
871 {
872 return ntfs_ib_pos_to_vcn(icx, pos * icx->block_size);
873 }
874
875 static int ntfs_ibm_add(ntfs_index_context *icx)
876 {
877 u8 bmp[8];
878
879 ntfs_log_trace("Entering\n");
880
881 if (ntfs_attr_exist(icx->ni, AT_BITMAP, icx->name, icx->name_len))
882 return STATUS_OK;
883 /*
884 * AT_BITMAP must be at least 8 bytes.
885 */
886 memset(bmp, 0, sizeof(bmp));
887 if (ntfs_attr_add(icx->ni, AT_BITMAP, icx->name, icx->name_len,
888 bmp, sizeof(bmp))) {
889 ntfs_log_perror("Failed to add AT_BITMAP");
890 return STATUS_ERROR;
891 }
892
893 return STATUS_OK;
894 }
895
896 static int ntfs_ibm_modify(ntfs_index_context *icx, VCN vcn, int set)
897 {
898 u8 byte;
899 s64 pos = ntfs_ibm_vcn_to_pos(icx, vcn);
900 u32 bpos = pos / 8;
901 u32 bit = 1 << (pos % 8);
902 ntfs_attr *na;
903 int ret = STATUS_ERROR;
904
905 ntfs_log_trace("%s vcn: %lld\n", set ? "set" : "clear", (long long)vcn);
906
907 na = ntfs_attr_open(icx->ni, AT_BITMAP, icx->name, icx->name_len);
908 if (!na) {
909 ntfs_log_perror("Failed to open $BITMAP attribute");
910 return -1;
911 }
912
913 if (set) {
914 if (na->data_size < bpos + 1) {
915 if (ntfs_attr_truncate(na, (na->data_size + 8) & ~7)) {
916 ntfs_log_perror("Failed to truncate AT_BITMAP");
917 goto err_na;
918 }
919 }
920 }
921
922 if (ntfs_attr_pread(na, bpos, 1, &byte) != 1) {
923 ntfs_log_perror("Failed to read $BITMAP");
924 goto err_na;
925 }
926
927 if (set)
928 byte |= bit;
929 else
930 byte &= ~bit;
931
932 if (ntfs_attr_pwrite(na, bpos, 1, &byte) != 1) {
933 ntfs_log_perror("Failed to write $Bitmap");
934 goto err_na;
935 }
936
937 ret = STATUS_OK;
938 err_na:
939 ntfs_attr_close(na);
940 return ret;
941 }
942
943
944 static int ntfs_ibm_set(ntfs_index_context *icx, VCN vcn)
945 {
946 return ntfs_ibm_modify(icx, vcn, 1);
947 }
948
949 static int ntfs_ibm_clear(ntfs_index_context *icx, VCN vcn)
950 {
951 return ntfs_ibm_modify(icx, vcn, 0);
952 }
953
954 static VCN ntfs_ibm_get_free(ntfs_index_context *icx)
955 {
956 u8 *bm;
957 int bit;
958 s64 vcn, byte, size;
959
960 ntfs_log_trace("Entering\n");
961
962 bm = ntfs_attr_readall(icx->ni, AT_BITMAP, icx->name, icx->name_len,
963 &size);
964 if (!bm)
965 return (VCN)-1;
966
967 for (byte = 0; byte < size; byte++) {
968
969 if (bm[byte] == 255)
970 continue;
971
972 for (bit = 0; bit < 8; bit++) {
973 if (!(bm[byte] & (1 << bit))) {
974 vcn = ntfs_ibm_pos_to_vcn(icx, byte * 8 + bit);
975 goto out;
976 }
977 }
978 }
979
980 vcn = ntfs_ibm_pos_to_vcn(icx, size * 8);
981 out:
982 ntfs_log_trace("allocated vcn: %lld\n", (long long)vcn);
983
984 if (ntfs_ibm_set(icx, vcn))
985 vcn = (VCN)-1;
986
987 free(bm);
988 return vcn;
989 }
990
991 static INDEX_BLOCK *ntfs_ir_to_ib(INDEX_ROOT *ir, VCN ib_vcn)
992 {
993 INDEX_BLOCK *ib;
994 INDEX_ENTRY *ie_last;
995 char *ies_start, *ies_end;
996 int i;
997
998 ntfs_log_trace("Entering\n");
999
1000 ib = ntfs_ib_alloc(ib_vcn, le32_to_cpu(ir->index_block_size), LEAF_NODE);
1001 if (!ib)
1002 return NULL;
1003
1004 ies_start = (char *)ntfs_ie_get_first(&ir->index);
1005 ies_end = (char *)ntfs_ie_get_end(&ir->index);
1006 ie_last = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
1007 /*
1008 * Copy all entries, including the termination entry
1009 * as well, which can never have any data.
1010 */
1011 i = (char *)ie_last - ies_start + le16_to_cpu(ie_last->length);
1012 memcpy(ntfs_ie_get_first(&ib->index), ies_start, i);
1013
1014 ib->index.ih_flags = ir->index.ih_flags;
1015 ib->index.index_length = cpu_to_le32(i +
1016 le32_to_cpu(ib->index.entries_offset));
1017 return ib;
1018 }
1019
1020 static void ntfs_ir_nill(INDEX_ROOT *ir)
1021 {
1022 INDEX_ENTRY *ie_last;
1023 char *ies_start, *ies_end;
1024
1025 ntfs_log_trace("Entering\n");
1026 /*
1027 * TODO: This function could be much simpler.
1028 */
1029 ies_start = (char *)ntfs_ie_get_first(&ir->index);
1030 ies_end = (char *)ntfs_ie_get_end(&ir->index);
1031 ie_last = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
1032 /*
1033 * Move the index root termination entry forward
1034 */
1035 if ((char *)ie_last > ies_start) {
1036 memmove(ies_start, (char *)ie_last, le16_to_cpu(ie_last->length));
1037 ie_last = (INDEX_ENTRY *)ies_start;
1038 }
1039 }
1040
1041 static int ntfs_ib_copy_tail(ntfs_index_context *icx, INDEX_BLOCK *src,
1042 INDEX_ENTRY *median, VCN new_vcn)
1043 {
1044 u8 *ies_end;
1045 INDEX_ENTRY *ie_head; /* first entry after the median */
1046 int tail_size, ret;
1047 INDEX_BLOCK *dst;
1048
1049 ntfs_log_trace("Entering\n");
1050
1051 dst = ntfs_ib_alloc(new_vcn, icx->block_size,
1052 src->index.ih_flags & NODE_MASK);
1053 if (!dst)
1054 return STATUS_ERROR;
1055
1056 ie_head = ntfs_ie_get_next(median);
1057
1058 ies_end = (u8 *)ntfs_ie_get_end(&src->index);
1059 tail_size = ies_end - (u8 *)ie_head;
1060 memcpy(ntfs_ie_get_first(&dst->index), ie_head, tail_size);
1061
1062 dst->index.index_length = cpu_to_le32(tail_size +
1063 le32_to_cpu(dst->index.entries_offset));
1064 ret = ntfs_ib_write(icx, dst);
1065
1066 free(dst);
1067 return ret;
1068 }
1069
1070 static int ntfs_ib_cut_tail(ntfs_index_context *icx, INDEX_BLOCK *ib,
1071 INDEX_ENTRY *ie)
1072 {
1073 char *ies_start, *ies_end;
1074 INDEX_ENTRY *ie_last;
1075
1076 ntfs_log_trace("Entering\n");
1077
1078 ies_start = (char *)ntfs_ie_get_first(&ib->index);
1079 ies_end = (char *)ntfs_ie_get_end(&ib->index);
1080
1081 ie_last = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
1082 if (ie_last->ie_flags & INDEX_ENTRY_NODE)
1083 ntfs_ie_set_vcn(ie_last, ntfs_ie_get_vcn(ie));
1084
1085 memcpy(ie, ie_last, le16_to_cpu(ie_last->length));
1086
1087 ib->index.index_length = cpu_to_le32(((char *)ie - ies_start) +
1088 le16_to_cpu(ie->length) + le32_to_cpu(ib->index.entries_offset));
1089
1090 if (ntfs_ib_write(icx, ib))
1091 return STATUS_ERROR;
1092
1093 return STATUS_OK;
1094 }
1095
1096 static int ntfs_ia_add(ntfs_index_context *icx)
1097 {
1098 ntfs_log_trace("Entering\n");
1099
1100 if (ntfs_ibm_add(icx))
1101 return -1;
1102
1103 if (!ntfs_attr_exist(icx->ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len)) {
1104
1105 if (ntfs_attr_add(icx->ni, AT_INDEX_ALLOCATION, icx->name,
1106 icx->name_len, NULL, 0)) {
1107 ntfs_log_perror("Failed to add AT_INDEX_ALLOCATION");
1108 return -1;
1109 }
1110 }
1111
1112 icx->ia_na = ntfs_ia_open(icx, icx->ni);
1113 if (!icx->ia_na)
1114 return -1;
1115
1116 return 0;
1117 }
1118
1119 static int ntfs_ir_reparent(ntfs_index_context *icx)
1120 {
1121 ntfs_attr_search_ctx *ctx = NULL;
1122 INDEX_ROOT *ir;
1123 INDEX_ENTRY *ie;
1124 INDEX_BLOCK *ib = NULL;
1125 VCN new_ib_vcn;
1126 int ix_root_size;
1127 int ret = STATUS_ERROR;
1128
1129 ntfs_log_trace("Entering\n");
1130
1131 ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1132 if (!ir)
1133 goto out;
1134
1135 if ((ir->index.ih_flags & NODE_MASK) == SMALL_INDEX)
1136 if (ntfs_ia_add(icx))
1137 goto out;
1138
1139 new_ib_vcn = ntfs_ibm_get_free(icx);
1140 if (new_ib_vcn == -1)
1141 goto out;
1142
1143 ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1144 if (!ir)
1145 goto clear_bmp;
1146
1147 ib = ntfs_ir_to_ib(ir, new_ib_vcn);
1148 if (ib == NULL) {
1149 ntfs_log_perror("Failed to move index root to index block");
1150 goto clear_bmp;
1151 }
1152
1153 if (ntfs_ib_write(icx, ib))
1154 goto clear_bmp;
1155
1156 retry :
1157 ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len, &ctx);
1158 if (!ir)
1159 goto clear_bmp;
1160
1161 ntfs_ir_nill(ir);
1162
1163 ie = ntfs_ie_get_first(&ir->index);
1164 ie->ie_flags |= INDEX_ENTRY_NODE;
1165 ie->length = const_cpu_to_le16(sizeof(INDEX_ENTRY_HEADER) + sizeof(VCN));
1166
1167 ir->index.ih_flags = LARGE_INDEX;
1168 ir->index.index_length = cpu_to_le32(le32_to_cpu(ir->index.entries_offset)
1169 + le16_to_cpu(ie->length));
1170 ir->index.allocated_size = ir->index.index_length;
1171 ix_root_size = sizeof(INDEX_ROOT) - sizeof(INDEX_HEADER)
1172 + le32_to_cpu(ir->index.allocated_size);
1173 if (ntfs_resident_attr_value_resize(ctx->mrec, ctx->attr,
1174 ix_root_size)) {
1175 /*
1176 * When there is no space to build a non-resident
1177 * index, we may have to move the root to an extent
1178 */
1179 if ((errno == ENOSPC)
1180 && (ctx->al_entry || !ntfs_inode_add_attrlist(icx->ni))) {
1181 ntfs_attr_put_search_ctx(ctx);
1182 ctx = (ntfs_attr_search_ctx*)NULL;
1183 ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len,
1184 &ctx);
1185 if (ir
1186 && !ntfs_attr_record_move_away(ctx, ix_root_size
1187 - le32_to_cpu(ctx->attr->value_length))) {
1188 ntfs_attr_put_search_ctx(ctx);
1189 ctx = (ntfs_attr_search_ctx*)NULL;
1190 goto retry;
1191 }
1192 }
1193 /* FIXME: revert index root */
1194 goto clear_bmp;
1195 }
1196 /*
1197 * FIXME: do it earlier if we have enough space in IR (should always),
1198 * so in error case we wouldn't lose the IB.
1199 */
1200 ntfs_ie_set_vcn(ie, new_ib_vcn);
1201
1202 ret = STATUS_OK;
1203 err_out:
1204 free(ib);
1205 ntfs_attr_put_search_ctx(ctx);
1206 out:
1207 return ret;
1208 clear_bmp:
1209 ntfs_ibm_clear(icx, new_ib_vcn);
1210 goto err_out;
1211 }
1212
1213 /**
1214 * ntfs_ir_truncate - Truncate index root attribute
1215 *
1216 * Returns STATUS_OK, STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT or STATUS_ERROR.
1217 */
1218 static int ntfs_ir_truncate(ntfs_index_context *icx, int data_size)
1219 {
1220 ntfs_attr *na;
1221 int ret;
1222
1223 ntfs_log_trace("Entering\n");
1224
1225 na = ntfs_attr_open(icx->ni, AT_INDEX_ROOT, icx->name, icx->name_len);
1226 if (!na) {
1227 ntfs_log_perror("Failed to open INDEX_ROOT");
1228 return STATUS_ERROR;
1229 }
1230 /*
1231 * INDEX_ROOT must be resident and its entries can be moved to
1232 * INDEX_BLOCK, so ENOSPC isn't a real error.
1233 */
1234 ret = ntfs_attr_truncate(na, data_size + offsetof(INDEX_ROOT, index));
1235 if (ret == STATUS_OK) {
1236
1237 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1238 if (!icx->ir)
1239 return STATUS_ERROR;
1240
1241 icx->ir->index.allocated_size = cpu_to_le32(data_size);
1242
1243 } else if (ret == STATUS_ERROR)
1244 ntfs_log_perror("Failed to truncate INDEX_ROOT");
1245
1246 ntfs_attr_close(na);
1247 return ret;
1248 }
1249
1250 /**
1251 * ntfs_ir_make_space - Make more space for the index root attribute
1252 *
1253 * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
1254 * On error return STATUS_ERROR.
1255 */
1256 static int ntfs_ir_make_space(ntfs_index_context *icx, int data_size)
1257 {
1258 int ret;
1259
1260 ntfs_log_trace("Entering\n");
1261
1262 ret = ntfs_ir_truncate(icx, data_size);
1263 if (ret == STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT) {
1264
1265 ret = ntfs_ir_reparent(icx);
1266 if (ret == STATUS_OK)
1267 ret = STATUS_KEEP_SEARCHING;
1268 else
1269 ntfs_log_perror("Failed to nodify INDEX_ROOT");
1270 }
1271
1272 return ret;
1273 }
1274
1275 /*
1276 * NOTE: 'ie' must be a copy of a real index entry.
1277 */
1278 static int ntfs_ie_add_vcn(INDEX_ENTRY **ie)
1279 {
1280 INDEX_ENTRY *p, *old = *ie;
1281
1282 old->length = cpu_to_le16(le16_to_cpu(old->length) + sizeof(VCN));
1283 p = realloc(old, le16_to_cpu(old->length));
1284 if (!p)
1285 return STATUS_ERROR;
1286
1287 p->ie_flags |= INDEX_ENTRY_NODE;
1288 *ie = p;
1289
1290 return STATUS_OK;
1291 }
1292
1293 static int ntfs_ih_insert(INDEX_HEADER *ih, INDEX_ENTRY *orig_ie, VCN new_vcn,
1294 int pos)
1295 {
1296 INDEX_ENTRY *ie_node, *ie;
1297 int ret = STATUS_ERROR;
1298 VCN old_vcn;
1299
1300 ntfs_log_trace("Entering\n");
1301
1302 ie = ntfs_ie_dup(orig_ie);
1303 if (!ie)
1304 return STATUS_ERROR;
1305
1306 if (!(ie->ie_flags & INDEX_ENTRY_NODE))
1307 if (ntfs_ie_add_vcn(&ie))
1308 goto out;
1309
1310 ie_node = ntfs_ie_get_by_pos(ih, pos);
1311 old_vcn = ntfs_ie_get_vcn(ie_node);
1312 ntfs_ie_set_vcn(ie_node, new_vcn);
1313
1314 ntfs_ie_insert(ih, ie, ie_node);
1315 ntfs_ie_set_vcn(ie_node, old_vcn);
1316 ret = STATUS_OK;
1317 out:
1318 free(ie);
1319
1320 return ret;
1321 }
1322
1323 static VCN ntfs_icx_parent_vcn(ntfs_index_context *icx)
1324 {
1325 return icx->parent_vcn[icx->pindex];
1326 }
1327
1328 static VCN ntfs_icx_parent_pos(ntfs_index_context *icx)
1329 {
1330 return icx->parent_pos[icx->pindex];
1331 }
1332
1333
1334 static int ntfs_ir_insert_median(ntfs_index_context *icx, INDEX_ENTRY *median,
1335 VCN new_vcn)
1336 {
1337 u32 new_size;
1338 int ret;
1339
1340 ntfs_log_trace("Entering\n");
1341
1342 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1343 if (!icx->ir)
1344 return STATUS_ERROR;
1345
1346 new_size = le32_to_cpu(icx->ir->index.index_length) +
1347 le16_to_cpu(median->length);
1348 if (!(median->ie_flags & INDEX_ENTRY_NODE))
1349 new_size += sizeof(VCN);
1350
1351 ret = ntfs_ir_make_space(icx, new_size);
1352 if (ret != STATUS_OK)
1353 return ret;
1354
1355 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1356 if (!icx->ir)
1357 return STATUS_ERROR;
1358
1359 return ntfs_ih_insert(&icx->ir->index, median, new_vcn,
1360 ntfs_icx_parent_pos(icx));
1361 }
1362
1363 static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib);
1364
1365 /**
1366 * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
1367 * On error return STATUS_ERROR.
1368 */
1369 static int ntfs_ib_insert(ntfs_index_context *icx, INDEX_ENTRY *ie, VCN new_vcn)
1370 {
1371 INDEX_BLOCK *ib;
1372 u32 idx_size, allocated_size;
1373 int err = STATUS_ERROR;
1374 VCN old_vcn;
1375
1376 ntfs_log_trace("Entering\n");
1377
1378 ib = ntfs_malloc(icx->block_size);
1379 if (!ib)
1380 return -1;
1381
1382 old_vcn = ntfs_icx_parent_vcn(icx);
1383
1384 if (ntfs_ib_read(icx, old_vcn, ib))
1385 goto err_out;
1386
1387 idx_size = le32_to_cpu(ib->index.index_length);
1388 allocated_size = le32_to_cpu(ib->index.allocated_size);
1389 /* FIXME: sizeof(VCN) should be included only if ie has no VCN */
1390 if (idx_size + le16_to_cpu(ie->length) + sizeof(VCN) > allocated_size) {
1391 err = ntfs_ib_split(icx, ib);
1392 if (err == STATUS_OK)
1393 err = STATUS_KEEP_SEARCHING;
1394 goto err_out;
1395 }
1396
1397 if (ntfs_ih_insert(&ib->index, ie, new_vcn, ntfs_icx_parent_pos(icx)))
1398 goto err_out;
1399
1400 if (ntfs_ib_write(icx, ib))
1401 goto err_out;
1402
1403 err = STATUS_OK;
1404 err_out:
1405 free(ib);
1406 return err;
1407 }
1408
1409 /**
1410 * ntfs_ib_split - Split an index block
1411 *
1412 * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
1413 * On error return is STATUS_ERROR.
1414 */
1415 static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib)
1416 {
1417 INDEX_ENTRY *median;
1418 VCN new_vcn;
1419 int ret;
1420
1421 ntfs_log_trace("Entering\n");
1422
1423 if (ntfs_icx_parent_dec(icx))
1424 return STATUS_ERROR;
1425
1426 median = ntfs_ie_get_median(&ib->index);
1427 new_vcn = ntfs_ibm_get_free(icx);
1428 if (new_vcn == -1)
1429 return STATUS_ERROR;
1430
1431 if (ntfs_ib_copy_tail(icx, ib, median, new_vcn)) {
1432 ntfs_ibm_clear(icx, new_vcn);
1433 return STATUS_ERROR;
1434 }
1435
1436 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
1437 ret = ntfs_ir_insert_median(icx, median, new_vcn);
1438 else
1439 ret = ntfs_ib_insert(icx, median, new_vcn);
1440
1441 if (ret != STATUS_OK) {
1442 ntfs_ibm_clear(icx, new_vcn);
1443 return ret;
1444 }
1445
1446 ret = ntfs_ib_cut_tail(icx, ib, median);
1447
1448 return ret;
1449 }
1450
1451 /* JPA static */
1452 int ntfs_ie_add(ntfs_index_context *icx, INDEX_ENTRY *ie)
1453 {
1454 INDEX_HEADER *ih;
1455 int allocated_size, new_size;
1456 int ret = STATUS_ERROR;
1457
1458 #ifdef DEBUG
1459 /* removed by JPA to make function usable for security indexes
1460 char *fn;
1461 fn = ntfs_ie_filename_get(ie);
1462 ntfs_log_trace("file: '%s'\n", fn);
1463 ntfs_attr_name_free(&fn);
1464 */
1465 #endif
1466
1467 while (1) {
1468
1469 if (!ntfs_index_lookup(&ie->key, le16_to_cpu(ie->key_length), icx)) {
1470 errno = EEXIST;
1471 ntfs_log_perror("Index already have such entry");
1472 goto err_out;
1473 }
1474 if (errno != ENOENT) {
1475 ntfs_log_perror("Failed to find place for new entry");
1476 goto err_out;
1477 }
1478
1479 if (icx->is_in_root)
1480 ih = &icx->ir->index;
1481 else
1482 ih = &icx->ib->index;
1483
1484 allocated_size = le32_to_cpu(ih->allocated_size);
1485 new_size = le32_to_cpu(ih->index_length) + le16_to_cpu(ie->length);
1486
1487 if (new_size <= allocated_size)
1488 break;
1489
1490 ntfs_log_trace("index block sizes: allocated: %d needed: %d\n",
1491 allocated_size, new_size);
1492
1493 if (icx->is_in_root) {
1494 if (ntfs_ir_make_space(icx, new_size) == STATUS_ERROR)
1495 goto err_out;
1496 } else {
1497 if (ntfs_ib_split(icx, icx->ib) == STATUS_ERROR)
1498 goto err_out;
1499 }
1500
1501 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1502 ntfs_index_ctx_reinit(icx);
1503 }
1504
1505 ntfs_ie_insert(ih, ie, icx->entry);
1506 ntfs_index_entry_mark_dirty(icx);
1507
1508 ret = STATUS_OK;
1509 err_out:
1510 ntfs_log_trace("%s\n", ret ? "Failed" : "Done");
1511 return ret;
1512 }
1513
1514 /**
1515 * ntfs_index_add_filename - add filename to directory index
1516 * @ni: ntfs inode describing directory to which index add filename
1517 * @fn: FILE_NAME attribute to add
1518 * @mref: reference of the inode which @fn describes
1519 *
1520 * Return 0 on success or -1 on error with errno set to the error code.
1521 */
1522 int ntfs_index_add_filename(ntfs_inode *ni, FILE_NAME_ATTR *fn, MFT_REF mref)
1523 {
1524 INDEX_ENTRY *ie;
1525 ntfs_index_context *icx;
1526 int fn_size, ie_size, err, ret = -1;
1527
1528 ntfs_log_trace("Entering\n");
1529
1530 if (!ni || !fn) {
1531 ntfs_log_error("Invalid arguments.\n");
1532 errno = EINVAL;
1533 return -1;
1534 }
1535
1536 fn_size = (fn->file_name_length * sizeof(ntfschar)) +
1537 sizeof(FILE_NAME_ATTR);
1538 ie_size = (sizeof(INDEX_ENTRY_HEADER) + fn_size + 7) & ~7;
1539
1540 ie = ntfs_calloc(ie_size);
1541 if (!ie)
1542 return -1;
1543
1544 ie->indexed_file = cpu_to_le64(mref);
1545 ie->length = cpu_to_le16(ie_size);
1546 ie->key_length = cpu_to_le16(fn_size);
1547 memcpy(&ie->key, fn, fn_size);
1548
1549 icx = ntfs_index_ctx_get(ni, NTFS_INDEX_I30, 4);
1550 if (!icx)
1551 goto out;
1552
1553 ret = ntfs_ie_add(icx, ie);
1554 err = errno;
1555 ntfs_index_ctx_put(icx);
1556 errno = err;
1557 out:
1558 free(ie);
1559 return ret;
1560 }
1561
1562 static int ntfs_ih_takeout(ntfs_index_context *icx, INDEX_HEADER *ih,
1563 INDEX_ENTRY *ie, INDEX_BLOCK *ib)
1564 {
1565 INDEX_ENTRY *ie_roam;
1566 int freed_space;
1567 BOOL full;
1568 int ret = STATUS_ERROR;
1569
1570 ntfs_log_trace("Entering\n");
1571
1572 full = ih->index_length == ih->allocated_size;
1573 ie_roam = ntfs_ie_dup_novcn(ie);
1574 if (!ie_roam)
1575 return STATUS_ERROR;
1576
1577 ntfs_ie_delete(ih, ie);
1578
1579 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) {
1580 /*
1581 * Recover the space which may have been freed
1582 * while deleting an entry from root index
1583 */
1584 freed_space = le32_to_cpu(ih->allocated_size)
1585 - le32_to_cpu(ih->index_length);
1586 if (full && (freed_space > 0) && !(freed_space & 7)) {
1587 ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
1588 /* do nothing if truncation fails */
1589 }
1590 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1591 } else
1592 if (ntfs_ib_write(icx, ib))
1593 goto out;
1594
1595 ntfs_index_ctx_reinit(icx);
1596
1597 ret = ntfs_ie_add(icx, ie_roam);
1598 out:
1599 free(ie_roam);
1600 return ret;
1601 }
1602
1603 /**
1604 * Used if an empty index block to be deleted has END entry as the parent
1605 * in the INDEX_ROOT which is the only one there.
1606 */
1607 static void ntfs_ir_leafify(ntfs_index_context *icx, INDEX_HEADER *ih)
1608 {
1609 INDEX_ENTRY *ie;
1610
1611 ntfs_log_trace("Entering\n");
1612
1613 ie = ntfs_ie_get_first(ih);
1614 ie->ie_flags &= ~INDEX_ENTRY_NODE;
1615 ie->length = cpu_to_le16(le16_to_cpu(ie->length) - sizeof(VCN));
1616
1617 ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) - sizeof(VCN));
1618 ih->ih_flags &= ~LARGE_INDEX;
1619
1620 /* Not fatal error */
1621 ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
1622 }
1623
1624 /**
1625 * Used if an empty index block to be deleted has END entry as the parent
1626 * in the INDEX_ROOT which is not the only one there.
1627 */
1628 static int ntfs_ih_reparent_end(ntfs_index_context *icx, INDEX_HEADER *ih,
1629 INDEX_BLOCK *ib)
1630 {
1631 INDEX_ENTRY *ie, *ie_prev;
1632
1633 ntfs_log_trace("Entering\n");
1634
1635 ie = ntfs_ie_get_by_pos(ih, ntfs_icx_parent_pos(icx));
1636 ie_prev = ntfs_ie_prev(ih, ie);
1637
1638 ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(ie_prev));
1639
1640 return ntfs_ih_takeout(icx, ih, ie_prev, ib);
1641 }
1642
1643 static int ntfs_index_rm_leaf(ntfs_index_context *icx)
1644 {
1645 INDEX_BLOCK *ib = NULL;
1646 INDEX_HEADER *parent_ih;
1647 INDEX_ENTRY *ie;
1648 int ret = STATUS_ERROR;
1649
1650 ntfs_log_trace("pindex: %d\n", icx->pindex);
1651
1652 if (ntfs_icx_parent_dec(icx))
1653 return STATUS_ERROR;
1654
1655 if (ntfs_ibm_clear(icx, icx->parent_vcn[icx->pindex + 1]))
1656 return STATUS_ERROR;
1657
1658 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
1659 parent_ih = &icx->ir->index;
1660 else {
1661 ib = ntfs_malloc(icx->block_size);
1662 if (!ib)
1663 return STATUS_ERROR;
1664
1665 if (ntfs_ib_read(icx, ntfs_icx_parent_vcn(icx), ib))
1666 goto out;
1667
1668 parent_ih = &ib->index;
1669 }
1670
1671 ie = ntfs_ie_get_by_pos(parent_ih, ntfs_icx_parent_pos(icx));
1672 if (!ntfs_ie_end(ie)) {
1673 ret = ntfs_ih_takeout(icx, parent_ih, ie, ib);
1674 goto out;
1675 }
1676
1677 if (ntfs_ih_zero_entry(parent_ih)) {
1678
1679 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) {
1680 ntfs_ir_leafify(icx, parent_ih);
1681 goto ok;
1682 }
1683
1684 ret = ntfs_index_rm_leaf(icx);
1685 goto out;
1686 }
1687
1688 if (ntfs_ih_reparent_end(icx, parent_ih, ib))
1689 goto out;
1690 ok:
1691 ret = STATUS_OK;
1692 out:
1693 free(ib);
1694 return ret;
1695 }
1696
1697 static int ntfs_index_rm_node(ntfs_index_context *icx)
1698 {
1699 int entry_pos, pindex;
1700 VCN vcn;
1701 INDEX_BLOCK *ib = NULL;
1702 INDEX_ENTRY *ie_succ, *ie, *entry = icx->entry;
1703 INDEX_HEADER *ih;
1704 u32 new_size;
1705 int delta, ret = STATUS_ERROR;
1706
1707 ntfs_log_trace("Entering\n");
1708
1709 if (!icx->ia_na) {
1710 icx->ia_na = ntfs_ia_open(icx, icx->ni);
1711 if (!icx->ia_na)
1712 return STATUS_ERROR;
1713 }
1714
1715 ib = ntfs_malloc(icx->block_size);
1716 if (!ib)
1717 return STATUS_ERROR;
1718
1719 ie_succ = ntfs_ie_get_next(icx->entry);
1720 entry_pos = icx->parent_pos[icx->pindex]++;
1721 pindex = icx->pindex;
1722 descend:
1723 vcn = ntfs_ie_get_vcn(ie_succ);
1724 if (ntfs_ib_read(icx, vcn, ib))
1725 goto out;
1726
1727 ie_succ = ntfs_ie_get_first(&ib->index);
1728
1729 if (ntfs_icx_parent_inc(icx))
1730 goto out;
1731
1732 icx->parent_vcn[icx->pindex] = vcn;
1733 icx->parent_pos[icx->pindex] = 0;
1734
1735 if ((ib->index.ih_flags & NODE_MASK) == INDEX_NODE)
1736 goto descend;
1737
1738 if (ntfs_ih_zero_entry(&ib->index)) {
1739 errno = EIO;
1740 ntfs_log_perror("Empty index block");
1741 goto out;
1742 }
1743
1744 ie = ntfs_ie_dup(ie_succ);
1745 if (!ie)
1746 goto out;
1747
1748 if (ntfs_ie_add_vcn(&ie))
1749 goto out2;
1750
1751 ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(icx->entry));
1752
1753 if (icx->is_in_root)
1754 ih = &icx->ir->index;
1755 else
1756 ih = &icx->ib->index;
1757
1758 delta = le16_to_cpu(ie->length) - le16_to_cpu(icx->entry->length);
1759 new_size = le32_to_cpu(ih->index_length) + delta;
1760 if (delta > 0) {
1761 if (icx->is_in_root) {
1762 ret = ntfs_ir_make_space(icx, new_size);
1763 if (ret != STATUS_OK)
1764 goto out2;
1765
1766 ih = &icx->ir->index;
1767 entry = ntfs_ie_get_by_pos(ih, entry_pos);
1768
1769 } else if (new_size > le32_to_cpu(ih->allocated_size)) {
1770 icx->pindex = pindex;
1771 ret = ntfs_ib_split(icx, icx->ib);
1772 if (ret == STATUS_OK)
1773 ret = STATUS_KEEP_SEARCHING;
1774 goto out2;
1775 }
1776 }
1777
1778 ntfs_ie_delete(ih, entry);
1779 ntfs_ie_insert(ih, ie, entry);
1780
1781 if (icx->is_in_root) {
1782 if (ntfs_ir_truncate(icx, new_size))
1783 goto out2;
1784 } else
1785 if (ntfs_icx_ib_write(icx))
1786 goto out2;
1787
1788 ntfs_ie_delete(&ib->index, ie_succ);
1789
1790 if (ntfs_ih_zero_entry(&ib->index)) {
1791 if (ntfs_index_rm_leaf(icx))
1792 goto out2;
1793 } else
1794 if (ntfs_ib_write(icx, ib))
1795 goto out2;
1796
1797 ret = STATUS_OK;
1798 out2:
1799 free(ie);
1800 out:
1801 free(ib);
1802 return ret;
1803 }
1804
1805 /**
1806 * ntfs_index_rm - remove entry from the index
1807 * @icx: index context describing entry to delete
1808 *
1809 * Delete entry described by @icx from the index. Index context is always
1810 * reinitialized after use of this function, so it can be used for index
1811 * lookup once again.
1812 *
1813 * Return 0 on success or -1 on error with errno set to the error code.
1814 */
1815 /*static JPA*/
1816 int ntfs_index_rm(ntfs_index_context *icx)
1817 {
1818 INDEX_HEADER *ih;
1819 int err, ret = STATUS_OK;
1820
1821 ntfs_log_trace("Entering\n");
1822
1823 if (!icx || (!icx->ib && !icx->ir) || ntfs_ie_end(icx->entry)) {
1824 ntfs_log_error("Invalid arguments.\n");
1825 errno = EINVAL;
1826 goto err_out;
1827 }
1828 if (icx->is_in_root)
1829 ih = &icx->ir->index;
1830 else
1831 ih = &icx->ib->index;
1832
1833 if (icx->entry->ie_flags & INDEX_ENTRY_NODE) {
1834
1835 ret = ntfs_index_rm_node(icx);
1836
1837 } else if (icx->is_in_root || !ntfs_ih_one_entry(ih)) {
1838
1839 ntfs_ie_delete(ih, icx->entry);
1840
1841 if (icx->is_in_root) {
1842 err = ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
1843 if (err != STATUS_OK)
1844 goto err_out;
1845 } else
1846 if (ntfs_icx_ib_write(icx))
1847 goto err_out;
1848 } else {
1849 if (ntfs_index_rm_leaf(icx))
1850 goto err_out;
1851 }
1852 out:
1853 return ret;
1854 err_out:
1855 ret = STATUS_ERROR;
1856 goto out;
1857 }
1858
1859 int ntfs_index_remove(ntfs_inode *dir_ni,
1860 ntfs_inode *ni __attribute__((unused)),
1861 const void *key, const int keylen)
1862 {
1863 int ret = STATUS_ERROR;
1864 ntfs_index_context *icx;
1865
1866 icx = ntfs_index_ctx_get(dir_ni, NTFS_INDEX_I30, 4);
1867 if (!icx)
1868 return -1;
1869
1870 while (1) {
1871
1872 if (ntfs_index_lookup(key, keylen, icx))
1873 goto err_out;
1874
1875 ret = ntfs_index_rm(icx);
1876 if (ret == STATUS_ERROR)
1877 goto err_out;
1878 else if (ret == STATUS_OK)
1879 break;
1880
1881 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1882 ntfs_index_ctx_reinit(icx);
1883 }
1884
1885 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1886 out:
1887 ntfs_index_ctx_put(icx);
1888 return ret;
1889 err_out:
1890 ret = STATUS_ERROR;
1891 ntfs_log_perror("Delete failed");
1892 goto out;
1893 }
1894
1895 /**
1896 * ntfs_index_root_get - read the index root of an attribute
1897 * @ni: open ntfs inode in which the ntfs attribute resides
1898 * @attr: attribute for which we want its index root
1899 *
1900 * This function will read the related index root an ntfs attribute.
1901 *
1902 * On success a buffer is allocated with the content of the index root
1903 * and which needs to be freed when it's not needed anymore.
1904 *
1905 * On error NULL is returned with errno set to the error code.
1906 */
1907 INDEX_ROOT *ntfs_index_root_get(ntfs_inode *ni, ATTR_RECORD *attr)
1908 {
1909 ntfs_attr_search_ctx *ctx;
1910 ntfschar *name;
1911 INDEX_ROOT *root = NULL;
1912
1913 name = (ntfschar *)((u8 *)attr + le16_to_cpu(attr->name_offset));
1914
1915 if (!ntfs_ir_lookup(ni, name, attr->name_length, &ctx))
1916 return NULL;
1917
1918 root = ntfs_malloc(sizeof(INDEX_ROOT));
1919 if (!root)
1920 goto out;
1921
1922 *root = *((INDEX_ROOT *)((u8 *)ctx->attr +
1923 le16_to_cpu(ctx->attr->value_offset)));
1924 out:
1925 ntfs_attr_put_search_ctx(ctx);
1926 return root;
1927 }
1928
1929
1930 /*
1931 * Walk down the index tree (leaf bound)
1932 * until there are no subnode in the first index entry
1933 * returns the entry at the bottom left in subnode
1934 */
1935
1936 static INDEX_ENTRY *ntfs_index_walk_down(INDEX_ENTRY *ie,
1937 ntfs_index_context *ictx)
1938 {
1939 INDEX_ENTRY *entry;
1940 s64 vcn;
1941
1942 entry = ie;
1943 do {
1944 vcn = ntfs_ie_get_vcn(entry);
1945 if (ictx->is_in_root) {
1946
1947 /* down from level zero */
1948
1949 ictx->ir = (INDEX_ROOT*)NULL;
1950 ictx->ib = (INDEX_BLOCK*)ntfs_malloc(ictx->block_size);
1951 ictx->pindex = 1;
1952 ictx->is_in_root = FALSE;
1953 } else {
1954
1955 /* down from non-zero level */
1956
1957 ictx->pindex++;
1958 }
1959 ictx->parent_pos[ictx->pindex] = 0;
1960 ictx->parent_vcn[ictx->pindex] = vcn;
1961 if (!ntfs_ib_read(ictx,vcn,ictx->ib)) {
1962 ictx->entry = ntfs_ie_get_first(&ictx->ib->index);
1963 entry = ictx->entry;
1964 } else
1965 entry = (INDEX_ENTRY*)NULL;
1966 } while (entry && (entry->ie_flags & INDEX_ENTRY_NODE));
1967 return (entry);
1968 }
1969
1970 /*
1971 * Walk up the index tree (root bound)
1972 * until there is a valid data entry in parent
1973 * returns the parent entry or NULL if no more parent
1974 */
1975
1976 static INDEX_ENTRY *ntfs_index_walk_up(INDEX_ENTRY *ie,
1977 ntfs_index_context *ictx)
1978 {
1979 INDEX_ENTRY *entry;
1980 s64 vcn;
1981
1982 entry = ie;
1983 if (ictx->pindex > 0) {
1984 do {
1985 ictx->pindex--;
1986 if (!ictx->pindex) {
1987
1988 /* we have reached the root */
1989
1990 free(ictx->ib);
1991 ictx->ib = (INDEX_BLOCK*)NULL;
1992 ictx->is_in_root = TRUE;
1993 /* a new search context is to be allocated */
1994 if (ictx->actx)
1995 free(ictx->actx);
1996 ictx->ir = ntfs_ir_lookup(ictx->ni,
1997 ictx->name, ictx->name_len,
1998 &ictx->actx);
1999 if (ictx->ir)
2000 entry = ntfs_ie_get_by_pos(
2001 &ictx->ir->index,
2002 ictx->parent_pos[ictx->pindex]);
2003 else
2004 entry = (INDEX_ENTRY*)NULL;
2005 } else {
2006 /* up into non-root node */
2007 vcn = ictx->parent_vcn[ictx->pindex];
2008 if (!ntfs_ib_read(ictx,vcn,ictx->ib)) {
2009 entry = ntfs_ie_get_by_pos(
2010 &ictx->ib->index,
2011 ictx->parent_pos[ictx->pindex]);
2012 } else
2013 entry = (INDEX_ENTRY*)NULL;
2014 }
2015 ictx->entry = entry;
2016 } while (entry && (ictx->pindex > 0)
2017 && (entry->ie_flags & INDEX_ENTRY_END));
2018 } else
2019 entry = (INDEX_ENTRY*)NULL;
2020 return (entry);
2021 }
2022
2023 /*
2024 * Get next entry in an index according to collating sequence.
2025 * Must be initialized through a ntfs_index_lookup()
2026 *
2027 * Returns next entry or NULL if none
2028 *
2029 * Sample layout :
2030 *
2031 * +---+---+---+---+---+---+---+---+ n ptrs to subnodes
2032 * | | | 10| 25| 33| | | | n-1 keys in between
2033 * +---+---+---+---+---+---+---+---+ no key in last entry
2034 * | A | A
2035 * | | | +-------------------------------+
2036 * +--------------------------+ | +-----+ |
2037 * | +--+ | |
2038 * V | V |
2039 * +---+---+---+---+---+---+---+---+ | +---+---+---+---+---+---+---+---+
2040 * | 11| 12| 13| 14| 15| 16| 17| | | | 26| 27| 28| 29| 30| 31| 32| |
2041 * +---+---+---+---+---+---+---+---+ | +---+---+---+---+---+---+---+---+
2042 * | |
2043 * +-----------------------+ |
2044 * | |
2045 * +---+---+---+---+---+---+---+---+
2046 * | 18| 19| 20| 21| 22| 23| 24| |
2047 * +---+---+---+---+---+---+---+---+
2048 */
2049
2050 INDEX_ENTRY *ntfs_index_next(INDEX_ENTRY *ie, ntfs_index_context *ictx)
2051 {
2052 INDEX_ENTRY *next;
2053 le16 flags;
2054
2055 /*
2056 * lookup() may have returned an invalid node
2057 * when searching for a partial key
2058 * if this happens, walk up
2059 */
2060
2061 if (ie->ie_flags & INDEX_ENTRY_END)
2062 next = ntfs_index_walk_up(ie, ictx);
2063 else {
2064 /*
2065 * get next entry in same node
2066 * there is always one after any entry with data
2067 */
2068
2069 next = (INDEX_ENTRY*)((char*)ie + le16_to_cpu(ie->length));
2070 ++ictx->parent_pos[ictx->pindex];
2071 flags = next->ie_flags;
2072
2073 /* walk down if it has a subnode */
2074
2075 if (flags & INDEX_ENTRY_NODE) {
2076 next = ntfs_index_walk_down(next,ictx);
2077 } else {
2078
2079 /* walk up it has no subnode, nor data */
2080
2081 if (flags & INDEX_ENTRY_END) {
2082 next = ntfs_index_walk_up(next, ictx);
2083 }
2084 }
2085 }
2086 /* return NULL if stuck at end of a block */
2087
2088 if (next && (next->ie_flags & INDEX_ENTRY_END))
2089 next = (INDEX_ENTRY*)NULL;
2090 return (next);
2091 }
2092
2093
FUSE NTFS driver