?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Correct PPTP server firewall rules chain.
[tomato/davidwu.git] / release / src / router / ntfs-3g / libntfs-3g / index.c
blobd498dde4b6b4e554ebe76108ee3cf117a7115969
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