summaryrefslogtreecommitdiff
path: root/libntfs-3g/index.c (plain)
blob: 7df0deec2008d4964f76b10611e827bd1b1b9b43
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 */
65void 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
73static s64 ntfs_ib_vcn_to_pos(ntfs_index_context *icx, VCN vcn)
74{
75 return vcn << icx->vcn_size_bits;
76}
77
78static VCN ntfs_ib_pos_to_vcn(ntfs_index_context *icx, s64 pos)
79{
80 return pos >> icx->vcn_size_bits;
81}
82
83static 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
100static 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 */
119ntfs_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
142static 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 */
169void 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 */
181void 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
194static 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 */
202VCN ntfs_ie_get_vcn(INDEX_ENTRY *ie)
203{
204 return sle64_to_cpup(ntfs_ie_get_vcn_addr(ie));
205}
206
207static INDEX_ENTRY *ntfs_ie_get_first(INDEX_HEADER *ih)
208{
209 return (INDEX_ENTRY *)((u8 *)ih + le32_to_cpu(ih->entries_offset));
210}
211
212static INDEX_ENTRY *ntfs_ie_get_next(INDEX_ENTRY *ie)
213{
214 return (INDEX_ENTRY *)((char *)ie + le16_to_cpu(ie->length));
215}
216
217static 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
223static 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 */
231static 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
241static 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
255static 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
272char *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
280void 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
289void 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
302static 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
317static int ntfs_ih_one_entry(INDEX_HEADER *ih)
318{
319 return (ntfs_ih_numof_entries(ih) == 1);
320}
321
322static int ntfs_ih_zero_entry(INDEX_HEADER *ih)
323{
324 return (ntfs_ih_numof_entries(ih) == 0);
325}
326
327static 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
339static 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 */
347static 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
359static 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
372static 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
391static 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
427static 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));
453err_out:
454 if (!ir) {
455 ntfs_attr_put_search_ctx(*ctx);
456 *ctx = NULL;
457 }
458 return ir;
459}
460
461static 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 */
484static 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
577static 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
591static 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
615static 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
626static 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 */
669int 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 = ni->vol->sector_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
747descend_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;
782err_out:
783 free(ib);
784 if (!err)
785 err = EIO;
786 errno = err;
787 return -1;
788done:
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
801static 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 */
835static 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
863static 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
868static 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
873static 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
894static 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;
936err_na:
937 ntfs_attr_close(na);
938 return ret;
939}
940
941
942static int ntfs_ibm_set(ntfs_index_context *icx, VCN vcn)
943{
944 return ntfs_ibm_modify(icx, vcn, 1);
945}
946
947static int ntfs_ibm_clear(ntfs_index_context *icx, VCN vcn)
948{
949 return ntfs_ibm_modify(icx, vcn, 0);
950}
951
952static 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);
979out:
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
989static 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
1018static 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
1039static 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
1068static 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
1094static 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
1117static 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 ret = STATUS_ERROR;
1125
1126 ntfs_log_trace("Entering\n");
1127
1128 ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1129 if (!ir)
1130 goto out;
1131
1132 if ((ir->index.ih_flags & NODE_MASK) == SMALL_INDEX)
1133 if (ntfs_ia_add(icx))
1134 goto out;
1135
1136 new_ib_vcn = ntfs_ibm_get_free(icx);
1137 if (new_ib_vcn == -1)
1138 goto out;
1139
1140 ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1141 if (!ir)
1142 goto clear_bmp;
1143
1144 ib = ntfs_ir_to_ib(ir, new_ib_vcn);
1145 if (ib == NULL) {
1146 ntfs_log_perror("Failed to move index root to index block");
1147 goto clear_bmp;
1148 }
1149
1150 if (ntfs_ib_write(icx, ib))
1151 goto clear_bmp;
1152
1153 ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len, &ctx);
1154 if (!ir)
1155 goto clear_bmp;
1156
1157 ntfs_ir_nill(ir);
1158
1159 ie = ntfs_ie_get_first(&ir->index);
1160 ie->ie_flags |= INDEX_ENTRY_NODE;
1161 ie->length = cpu_to_le16(sizeof(INDEX_ENTRY_HEADER) + sizeof(VCN));
1162
1163 ir->index.ih_flags = LARGE_INDEX;
1164 ir->index.index_length = cpu_to_le32(le32_to_cpu(ir->index.entries_offset)
1165 + le16_to_cpu(ie->length));
1166 ir->index.allocated_size = ir->index.index_length;
1167
1168 if (ntfs_resident_attr_value_resize(ctx->mrec, ctx->attr,
1169 sizeof(INDEX_ROOT) - sizeof(INDEX_HEADER) +
1170 le32_to_cpu(ir->index.allocated_size)))
1171 /* FIXME: revert index root */
1172 goto clear_bmp;
1173 /*
1174 * FIXME: do it earlier if we have enough space in IR (should always),
1175 * so in error case we wouldn't lose the IB.
1176 */
1177 ntfs_ie_set_vcn(ie, new_ib_vcn);
1178
1179 ret = STATUS_OK;
1180err_out:
1181 free(ib);
1182 ntfs_attr_put_search_ctx(ctx);
1183out:
1184 return ret;
1185clear_bmp:
1186 ntfs_ibm_clear(icx, new_ib_vcn);
1187 goto err_out;
1188}
1189
1190/**
1191 * ntfs_ir_truncate - Truncate index root attribute
1192 *
1193 * Returns STATUS_OK, STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT or STATUS_ERROR.
1194 */
1195static int ntfs_ir_truncate(ntfs_index_context *icx, int data_size)
1196{
1197 ntfs_attr *na;
1198 int ret;
1199
1200 ntfs_log_trace("Entering\n");
1201
1202 na = ntfs_attr_open(icx->ni, AT_INDEX_ROOT, icx->name, icx->name_len);
1203 if (!na) {
1204 ntfs_log_perror("Failed to open INDEX_ROOT");
1205 return STATUS_ERROR;
1206 }
1207 /*
1208 * INDEX_ROOT must be resident and its entries can be moved to
1209 * INDEX_BLOCK, so ENOSPC isn't a real error.
1210 */
1211 ret = ntfs_attr_truncate(na, data_size + offsetof(INDEX_ROOT, index));
1212 if (ret == STATUS_OK) {
1213
1214 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1215 if (!icx->ir)
1216 return STATUS_ERROR;
1217
1218 icx->ir->index.allocated_size = cpu_to_le32(data_size);
1219
1220 } else if (ret == STATUS_ERROR)
1221 ntfs_log_perror("Failed to truncate INDEX_ROOT");
1222
1223 ntfs_attr_close(na);
1224 return ret;
1225}
1226
1227/**
1228 * ntfs_ir_make_space - Make more space for the index root attribute
1229 *
1230 * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
1231 * On error return STATUS_ERROR.
1232 */
1233static int ntfs_ir_make_space(ntfs_index_context *icx, int data_size)
1234{
1235 int ret;
1236
1237 ntfs_log_trace("Entering\n");
1238
1239 ret = ntfs_ir_truncate(icx, data_size);
1240 if (ret == STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT) {
1241
1242 ret = ntfs_ir_reparent(icx);
1243 if (ret == STATUS_OK)
1244 ret = STATUS_KEEP_SEARCHING;
1245 else
1246 ntfs_log_perror("Failed to nodify INDEX_ROOT");
1247 }
1248
1249 return ret;
1250}
1251
1252/*
1253 * NOTE: 'ie' must be a copy of a real index entry.
1254 */
1255static int ntfs_ie_add_vcn(INDEX_ENTRY **ie)
1256{
1257 INDEX_ENTRY *p, *old = *ie;
1258
1259 old->length = cpu_to_le16(le16_to_cpu(old->length) + sizeof(VCN));
1260 p = realloc(old, le16_to_cpu(old->length));
1261 if (!p)
1262 return STATUS_ERROR;
1263
1264 p->ie_flags |= INDEX_ENTRY_NODE;
1265 *ie = p;
1266
1267 return STATUS_OK;
1268}
1269
1270static int ntfs_ih_insert(INDEX_HEADER *ih, INDEX_ENTRY *orig_ie, VCN new_vcn,
1271 int pos)
1272{
1273 INDEX_ENTRY *ie_node, *ie;
1274 int ret = STATUS_ERROR;
1275 VCN old_vcn;
1276
1277 ntfs_log_trace("Entering\n");
1278
1279 ie = ntfs_ie_dup(orig_ie);
1280 if (!ie)
1281 return STATUS_ERROR;
1282
1283 if (!(ie->ie_flags & INDEX_ENTRY_NODE))
1284 if (ntfs_ie_add_vcn(&ie))
1285 goto out;
1286
1287 ie_node = ntfs_ie_get_by_pos(ih, pos);
1288 old_vcn = ntfs_ie_get_vcn(ie_node);
1289 ntfs_ie_set_vcn(ie_node, new_vcn);
1290
1291 ntfs_ie_insert(ih, ie, ie_node);
1292 ntfs_ie_set_vcn(ie_node, old_vcn);
1293 ret = STATUS_OK;
1294out:
1295 free(ie);
1296
1297 return ret;
1298}
1299
1300static VCN ntfs_icx_parent_vcn(ntfs_index_context *icx)
1301{
1302 return icx->parent_vcn[icx->pindex];
1303}
1304
1305static VCN ntfs_icx_parent_pos(ntfs_index_context *icx)
1306{
1307 return icx->parent_pos[icx->pindex];
1308}
1309
1310
1311static int ntfs_ir_insert_median(ntfs_index_context *icx, INDEX_ENTRY *median,
1312 VCN new_vcn)
1313{
1314 u32 new_size;
1315 int ret;
1316
1317 ntfs_log_trace("Entering\n");
1318
1319 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1320 if (!icx->ir)
1321 return STATUS_ERROR;
1322
1323 new_size = le32_to_cpu(icx->ir->index.index_length) +
1324 le16_to_cpu(median->length);
1325 if (!(median->ie_flags & INDEX_ENTRY_NODE))
1326 new_size += sizeof(VCN);
1327
1328 ret = ntfs_ir_make_space(icx, new_size);
1329 if (ret != STATUS_OK)
1330 return ret;
1331
1332 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
1333 if (!icx->ir)
1334 return STATUS_ERROR;
1335
1336 return ntfs_ih_insert(&icx->ir->index, median, new_vcn,
1337 ntfs_icx_parent_pos(icx));
1338}
1339
1340static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib);
1341
1342/**
1343 * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
1344 * On error return STATUS_ERROR.
1345 */
1346static int ntfs_ib_insert(ntfs_index_context *icx, INDEX_ENTRY *ie, VCN new_vcn)
1347{
1348 INDEX_BLOCK *ib;
1349 u32 idx_size, allocated_size;
1350 int err = STATUS_ERROR;
1351 VCN old_vcn;
1352
1353 ntfs_log_trace("Entering\n");
1354
1355 ib = ntfs_malloc(icx->block_size);
1356 if (!ib)
1357 return -1;
1358
1359 old_vcn = ntfs_icx_parent_vcn(icx);
1360
1361 if (ntfs_ib_read(icx, old_vcn, ib))
1362 goto err_out;
1363
1364 idx_size = le32_to_cpu(ib->index.index_length);
1365 allocated_size = le32_to_cpu(ib->index.allocated_size);
1366 /* FIXME: sizeof(VCN) should be included only if ie has no VCN */
1367 if (idx_size + le16_to_cpu(ie->length) + sizeof(VCN) > allocated_size) {
1368 err = ntfs_ib_split(icx, ib);
1369 if (err == STATUS_OK)
1370 err = STATUS_KEEP_SEARCHING;
1371 goto err_out;
1372 }
1373
1374 if (ntfs_ih_insert(&ib->index, ie, new_vcn, ntfs_icx_parent_pos(icx)))
1375 goto err_out;
1376
1377 if (ntfs_ib_write(icx, ib))
1378 goto err_out;
1379
1380 err = STATUS_OK;
1381err_out:
1382 free(ib);
1383 return err;
1384}
1385
1386/**
1387 * ntfs_ib_split - Split an index block
1388 *
1389 * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
1390 * On error return is STATUS_ERROR.
1391 */
1392static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib)
1393{
1394 INDEX_ENTRY *median;
1395 VCN new_vcn;
1396 int ret;
1397
1398 ntfs_log_trace("Entering\n");
1399
1400 if (ntfs_icx_parent_dec(icx))
1401 return STATUS_ERROR;
1402
1403 median = ntfs_ie_get_median(&ib->index);
1404 new_vcn = ntfs_ibm_get_free(icx);
1405 if (new_vcn == -1)
1406 return STATUS_ERROR;
1407
1408 if (ntfs_ib_copy_tail(icx, ib, median, new_vcn)) {
1409 ntfs_ibm_clear(icx, new_vcn);
1410 return STATUS_ERROR;
1411 }
1412
1413 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
1414 ret = ntfs_ir_insert_median(icx, median, new_vcn);
1415 else
1416 ret = ntfs_ib_insert(icx, median, new_vcn);
1417
1418 if (ret != STATUS_OK) {
1419 ntfs_ibm_clear(icx, new_vcn);
1420 return ret;
1421 }
1422
1423 ret = ntfs_ib_cut_tail(icx, ib, median);
1424
1425 return ret;
1426}
1427
1428/* JPA static */
1429int ntfs_ie_add(ntfs_index_context *icx, INDEX_ENTRY *ie)
1430{
1431 INDEX_HEADER *ih;
1432 int allocated_size, new_size;
1433 int ret = STATUS_ERROR;
1434
1435#ifdef DEBUG
1436/* removed by JPA to make function usable for security indexes
1437 char *fn;
1438 fn = ntfs_ie_filename_get(ie);
1439 ntfs_log_trace("file: '%s'\n", fn);
1440 ntfs_attr_name_free(&fn);
1441*/
1442#endif
1443
1444 while (1) {
1445
1446 if (!ntfs_index_lookup(&ie->key, le16_to_cpu(ie->key_length), icx)) {
1447 errno = EEXIST;
1448 ntfs_log_perror("Index already have such entry");
1449 goto err_out;
1450 }
1451 if (errno != ENOENT) {
1452 ntfs_log_perror("Failed to find place for new entry");
1453 goto err_out;
1454 }
1455
1456 if (icx->is_in_root)
1457 ih = &icx->ir->index;
1458 else
1459 ih = &icx->ib->index;
1460
1461 allocated_size = le32_to_cpu(ih->allocated_size);
1462 new_size = le32_to_cpu(ih->index_length) + le16_to_cpu(ie->length);
1463
1464 if (new_size <= allocated_size)
1465 break;
1466
1467 ntfs_log_trace("index block sizes: allocated: %d needed: %d\n",
1468 allocated_size, new_size);
1469
1470 if (icx->is_in_root) {
1471 if (ntfs_ir_make_space(icx, new_size) == STATUS_ERROR)
1472 goto err_out;
1473 } else {
1474 if (ntfs_ib_split(icx, icx->ib) == STATUS_ERROR)
1475 goto err_out;
1476 }
1477
1478 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1479 ntfs_index_ctx_reinit(icx);
1480 }
1481
1482 ntfs_ie_insert(ih, ie, icx->entry);
1483 ntfs_index_entry_mark_dirty(icx);
1484
1485 ret = STATUS_OK;
1486err_out:
1487 ntfs_log_trace("%s\n", ret ? "Failed" : "Done");
1488 return ret;
1489}
1490
1491/**
1492 * ntfs_index_add_filename - add filename to directory index
1493 * @ni: ntfs inode describing directory to which index add filename
1494 * @fn: FILE_NAME attribute to add
1495 * @mref: reference of the inode which @fn describes
1496 *
1497 * Return 0 on success or -1 on error with errno set to the error code.
1498 */
1499int ntfs_index_add_filename(ntfs_inode *ni, FILE_NAME_ATTR *fn, MFT_REF mref)
1500{
1501 INDEX_ENTRY *ie;
1502 ntfs_index_context *icx;
1503 int fn_size, ie_size, err, ret = -1;
1504
1505 ntfs_log_trace("Entering\n");
1506
1507 if (!ni || !fn) {
1508 ntfs_log_error("Invalid arguments.\n");
1509 errno = EINVAL;
1510 return -1;
1511 }
1512
1513 fn_size = (fn->file_name_length * sizeof(ntfschar)) +
1514 sizeof(FILE_NAME_ATTR);
1515 ie_size = (sizeof(INDEX_ENTRY_HEADER) + fn_size + 7) & ~7;
1516
1517 ie = ntfs_calloc(ie_size);
1518 if (!ie)
1519 return -1;
1520
1521 ie->indexed_file = cpu_to_le64(mref);
1522 ie->length = cpu_to_le16(ie_size);
1523 ie->key_length = cpu_to_le16(fn_size);
1524 memcpy(&ie->key, fn, fn_size);
1525
1526 icx = ntfs_index_ctx_get(ni, NTFS_INDEX_I30, 4);
1527 if (!icx)
1528 goto out;
1529
1530 ret = ntfs_ie_add(icx, ie);
1531 err = errno;
1532 ntfs_index_ctx_put(icx);
1533 errno = err;
1534out:
1535 free(ie);
1536 return ret;
1537}
1538
1539static int ntfs_ih_takeout(ntfs_index_context *icx, INDEX_HEADER *ih,
1540 INDEX_ENTRY *ie, INDEX_BLOCK *ib)
1541{
1542 INDEX_ENTRY *ie_roam;
1543 int ret = STATUS_ERROR;
1544
1545 ntfs_log_trace("Entering\n");
1546
1547 ie_roam = ntfs_ie_dup_novcn(ie);
1548 if (!ie_roam)
1549 return STATUS_ERROR;
1550
1551 ntfs_ie_delete(ih, ie);
1552
1553 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
1554 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1555 else
1556 if (ntfs_ib_write(icx, ib))
1557 goto out;
1558
1559 ntfs_index_ctx_reinit(icx);
1560
1561 ret = ntfs_ie_add(icx, ie_roam);
1562out:
1563 free(ie_roam);
1564 return ret;
1565}
1566
1567/**
1568 * Used if an empty index block to be deleted has END entry as the parent
1569 * in the INDEX_ROOT which is the only one there.
1570 */
1571static void ntfs_ir_leafify(ntfs_index_context *icx, INDEX_HEADER *ih)
1572{
1573 INDEX_ENTRY *ie;
1574
1575 ntfs_log_trace("Entering\n");
1576
1577 ie = ntfs_ie_get_first(ih);
1578 ie->ie_flags &= ~INDEX_ENTRY_NODE;
1579 ie->length = cpu_to_le16(le16_to_cpu(ie->length) - sizeof(VCN));
1580
1581 ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) - sizeof(VCN));
1582 ih->ih_flags &= ~LARGE_INDEX;
1583
1584 /* Not fatal error */
1585 ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
1586}
1587
1588/**
1589 * Used if an empty index block to be deleted has END entry as the parent
1590 * in the INDEX_ROOT which is not the only one there.
1591 */
1592static int ntfs_ih_reparent_end(ntfs_index_context *icx, INDEX_HEADER *ih,
1593 INDEX_BLOCK *ib)
1594{
1595 INDEX_ENTRY *ie, *ie_prev;
1596
1597 ntfs_log_trace("Entering\n");
1598
1599 ie = ntfs_ie_get_by_pos(ih, ntfs_icx_parent_pos(icx));
1600 ie_prev = ntfs_ie_prev(ih, ie);
1601
1602 ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(ie_prev));
1603
1604 return ntfs_ih_takeout(icx, ih, ie_prev, ib);
1605}
1606
1607static int ntfs_index_rm_leaf(ntfs_index_context *icx)
1608{
1609 INDEX_BLOCK *ib = NULL;
1610 INDEX_HEADER *parent_ih;
1611 INDEX_ENTRY *ie;
1612 int ret = STATUS_ERROR;
1613
1614 ntfs_log_trace("pindex: %d\n", icx->pindex);
1615
1616 if (ntfs_icx_parent_dec(icx))
1617 return STATUS_ERROR;
1618
1619 if (ntfs_ibm_clear(icx, icx->parent_vcn[icx->pindex + 1]))
1620 return STATUS_ERROR;
1621
1622 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
1623 parent_ih = &icx->ir->index;
1624 else {
1625 ib = ntfs_malloc(icx->block_size);
1626 if (!ib)
1627 return STATUS_ERROR;
1628
1629 if (ntfs_ib_read(icx, ntfs_icx_parent_vcn(icx), ib))
1630 goto out;
1631
1632 parent_ih = &ib->index;
1633 }
1634
1635 ie = ntfs_ie_get_by_pos(parent_ih, ntfs_icx_parent_pos(icx));
1636 if (!ntfs_ie_end(ie)) {
1637 ret = ntfs_ih_takeout(icx, parent_ih, ie, ib);
1638 goto out;
1639 }
1640
1641 if (ntfs_ih_zero_entry(parent_ih)) {
1642
1643 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) {
1644 ntfs_ir_leafify(icx, parent_ih);
1645 goto ok;
1646 }
1647
1648 ret = ntfs_index_rm_leaf(icx);
1649 goto out;
1650 }
1651
1652 if (ntfs_ih_reparent_end(icx, parent_ih, ib))
1653 goto out;
1654ok:
1655 ret = STATUS_OK;
1656out:
1657 free(ib);
1658 return ret;
1659}
1660
1661static int ntfs_index_rm_node(ntfs_index_context *icx)
1662{
1663 int entry_pos, pindex;
1664 VCN vcn;
1665 INDEX_BLOCK *ib = NULL;
1666 INDEX_ENTRY *ie_succ, *ie, *entry = icx->entry;
1667 INDEX_HEADER *ih;
1668 u32 new_size;
1669 int delta, ret = STATUS_ERROR;
1670
1671 ntfs_log_trace("Entering\n");
1672
1673 if (!icx->ia_na) {
1674 icx->ia_na = ntfs_ia_open(icx, icx->ni);
1675 if (!icx->ia_na)
1676 return STATUS_ERROR;
1677 }
1678
1679 ib = ntfs_malloc(icx->block_size);
1680 if (!ib)
1681 return STATUS_ERROR;
1682
1683 ie_succ = ntfs_ie_get_next(icx->entry);
1684 entry_pos = icx->parent_pos[icx->pindex]++;
1685 pindex = icx->pindex;
1686descend:
1687 vcn = ntfs_ie_get_vcn(ie_succ);
1688 if (ntfs_ib_read(icx, vcn, ib))
1689 goto out;
1690
1691 ie_succ = ntfs_ie_get_first(&ib->index);
1692
1693 if (ntfs_icx_parent_inc(icx))
1694 goto out;
1695
1696 icx->parent_vcn[icx->pindex] = vcn;
1697 icx->parent_pos[icx->pindex] = 0;
1698
1699 if ((ib->index.ih_flags & NODE_MASK) == INDEX_NODE)
1700 goto descend;
1701
1702 if (ntfs_ih_zero_entry(&ib->index)) {
1703 errno = EIO;
1704 ntfs_log_perror("Empty index block");
1705 goto out;
1706 }
1707
1708 ie = ntfs_ie_dup(ie_succ);
1709 if (!ie)
1710 goto out;
1711
1712 if (ntfs_ie_add_vcn(&ie))
1713 goto out2;
1714
1715 ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(icx->entry));
1716
1717 if (icx->is_in_root)
1718 ih = &icx->ir->index;
1719 else
1720 ih = &icx->ib->index;
1721
1722 delta = le16_to_cpu(ie->length) - le16_to_cpu(icx->entry->length);
1723 new_size = le32_to_cpu(ih->index_length) + delta;
1724 if (delta > 0) {
1725 if (icx->is_in_root) {
1726 ret = ntfs_ir_make_space(icx, new_size);
1727 if (ret != STATUS_OK)
1728 goto out2;
1729
1730 ih = &icx->ir->index;
1731 entry = ntfs_ie_get_by_pos(ih, entry_pos);
1732
1733 } else if (new_size > le32_to_cpu(ih->allocated_size)) {
1734 icx->pindex = pindex;
1735 ret = ntfs_ib_split(icx, icx->ib);
1736 if (ret == STATUS_OK)
1737 ret = STATUS_KEEP_SEARCHING;
1738 goto out2;
1739 }
1740 }
1741
1742 ntfs_ie_delete(ih, entry);
1743 ntfs_ie_insert(ih, ie, entry);
1744
1745 if (icx->is_in_root) {
1746 if (ntfs_ir_truncate(icx, new_size))
1747 goto out2;
1748 } else
1749 if (ntfs_icx_ib_write(icx))
1750 goto out2;
1751
1752 ntfs_ie_delete(&ib->index, ie_succ);
1753
1754 if (ntfs_ih_zero_entry(&ib->index)) {
1755 if (ntfs_index_rm_leaf(icx))
1756 goto out2;
1757 } else
1758 if (ntfs_ib_write(icx, ib))
1759 goto out2;
1760
1761 ret = STATUS_OK;
1762out2:
1763 free(ie);
1764out:
1765 free(ib);
1766 return ret;
1767}
1768
1769/**
1770 * ntfs_index_rm - remove entry from the index
1771 * @icx: index context describing entry to delete
1772 *
1773 * Delete entry described by @icx from the index. Index context is always
1774 * reinitialized after use of this function, so it can be used for index
1775 * lookup once again.
1776 *
1777 * Return 0 on success or -1 on error with errno set to the error code.
1778 */
1779/*static JPA*/
1780int ntfs_index_rm(ntfs_index_context *icx)
1781{
1782 INDEX_HEADER *ih;
1783 int err, ret = STATUS_OK;
1784
1785 ntfs_log_trace("Entering\n");
1786
1787 if (!icx || (!icx->ib && !icx->ir) || ntfs_ie_end(icx->entry)) {
1788 ntfs_log_error("Invalid arguments.\n");
1789 errno = EINVAL;
1790 goto err_out;
1791 }
1792 if (icx->is_in_root)
1793 ih = &icx->ir->index;
1794 else
1795 ih = &icx->ib->index;
1796
1797 if (icx->entry->ie_flags & INDEX_ENTRY_NODE) {
1798
1799 ret = ntfs_index_rm_node(icx);
1800
1801 } else if (icx->is_in_root || !ntfs_ih_one_entry(ih)) {
1802
1803 ntfs_ie_delete(ih, icx->entry);
1804
1805 if (icx->is_in_root) {
1806 err = ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
1807 if (err != STATUS_OK)
1808 goto err_out;
1809 } else
1810 if (ntfs_icx_ib_write(icx))
1811 goto err_out;
1812 } else {
1813 if (ntfs_index_rm_leaf(icx))
1814 goto err_out;
1815 }
1816out:
1817 return ret;
1818err_out:
1819 ret = STATUS_ERROR;
1820 goto out;
1821}
1822
1823int ntfs_index_remove(ntfs_inode *dir_ni, ntfs_inode *ni,
1824 const void *key, const int keylen)
1825{
1826 int ret = STATUS_ERROR;
1827 ntfs_index_context *icx;
1828
1829 icx = ntfs_index_ctx_get(dir_ni, NTFS_INDEX_I30, 4);
1830 if (!icx)
1831 return -1;
1832
1833 while (1) {
1834
1835 if (ntfs_index_lookup(key, keylen, icx))
1836 goto err_out;
1837
1838 if ((((FILE_NAME_ATTR *)icx->data)->file_attributes &
1839 FILE_ATTR_REPARSE_POINT)
1840 && !ntfs_possible_symlink(ni)) {
1841 errno = EOPNOTSUPP;
1842 goto err_out;
1843 }
1844
1845 ret = ntfs_index_rm(icx);
1846 if (ret == STATUS_ERROR)
1847 goto err_out;
1848 else if (ret == STATUS_OK)
1849 break;
1850
1851 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1852 ntfs_index_ctx_reinit(icx);
1853 }
1854
1855 ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
1856out:
1857 ntfs_index_ctx_put(icx);
1858 return ret;
1859err_out:
1860 ret = STATUS_ERROR;
1861 ntfs_log_perror("Delete failed");
1862 goto out;
1863}
1864
1865/**
1866 * ntfs_index_root_get - read the index root of an attribute
1867 * @ni: open ntfs inode in which the ntfs attribute resides
1868 * @attr: attribute for which we want its index root
1869 *
1870 * This function will read the related index root an ntfs attribute.
1871 *
1872 * On success a buffer is allocated with the content of the index root
1873 * and which needs to be freed when it's not needed anymore.
1874 *
1875 * On error NULL is returned with errno set to the error code.
1876 */
1877INDEX_ROOT *ntfs_index_root_get(ntfs_inode *ni, ATTR_RECORD *attr)
1878{
1879 ntfs_attr_search_ctx *ctx;
1880 ntfschar *name;
1881 INDEX_ROOT *root = NULL;
1882
1883 name = (ntfschar *)((u8 *)attr + le16_to_cpu(attr->name_offset));
1884
1885 if (!ntfs_ir_lookup(ni, name, attr->name_length, &ctx))
1886 return NULL;
1887
1888 root = ntfs_malloc(sizeof(INDEX_ROOT));
1889 if (!root)
1890 goto out;
1891
1892 *root = *((INDEX_ROOT *)((u8 *)ctx->attr +
1893 le16_to_cpu(ctx->attr->value_offset)));
1894out:
1895 ntfs_attr_put_search_ctx(ctx);
1896 return root;
1897}
1898
1899
1900/*
1901 * Walk down the index tree (leaf bound)
1902 * until there are no subnode in the first index entry
1903 * returns the entry at the bottom left in subnode
1904 */
1905
1906static INDEX_ENTRY *ntfs_index_walk_down(INDEX_ENTRY *ie,
1907 ntfs_index_context *ictx)
1908{
1909 INDEX_ENTRY *entry;
1910 s64 vcn;
1911
1912 entry = ie;
1913 do {
1914 vcn = ntfs_ie_get_vcn(entry);
1915 if (ictx->is_in_root) {
1916
1917 /* down from level zero */
1918
1919 ictx->ir = (INDEX_ROOT*)NULL;
1920 ictx->ib = (INDEX_BLOCK*)ntfs_malloc(ictx->block_size);
1921 ictx->pindex = 1;
1922 ictx->is_in_root = FALSE;
1923 } else {
1924
1925 /* down from non-zero level */
1926
1927 ictx->pindex++;
1928 }
1929 ictx->parent_pos[ictx->pindex] = 0;
1930 ictx->parent_vcn[ictx->pindex] = vcn;
1931 if (!ntfs_ib_read(ictx,vcn,ictx->ib)) {
1932 ictx->entry = ntfs_ie_get_first(&ictx->ib->index);
1933 entry = ictx->entry;
1934 } else
1935 entry = (INDEX_ENTRY*)NULL;
1936 } while (entry && (entry->ie_flags & INDEX_ENTRY_NODE));
1937 return (entry);
1938}
1939
1940/*
1941 * Walk up the index tree (root bound)
1942 * until there is a valid data entry in parent
1943 * returns the parent entry or NULL if no more parent
1944 */
1945
1946static INDEX_ENTRY *ntfs_index_walk_up(INDEX_ENTRY *ie,
1947 ntfs_index_context *ictx)
1948{
1949 INDEX_ENTRY *entry;
1950 s64 vcn;
1951
1952 entry = ie;
1953 if (ictx->pindex > 0) {
1954 do {
1955 ictx->pindex--;
1956 if (!ictx->pindex) {
1957
1958 /* we have reached the root */
1959
1960 free(ictx->ib);
1961 ictx->ib = (INDEX_BLOCK*)NULL;
1962 ictx->is_in_root = TRUE;
1963 /* a new search context is to be allocated */
1964 if (ictx->actx)
1965 free(ictx->actx);
1966 ictx->ir = ntfs_ir_lookup(ictx->ni,
1967 ictx->name, ictx->name_len,
1968 &ictx->actx);
1969 if (ictx->ir)
1970 entry = ntfs_ie_get_by_pos(
1971 &ictx->ir->index,
1972 ictx->parent_pos[ictx->pindex]);
1973 else
1974 entry = (INDEX_ENTRY*)NULL;
1975 } else {
1976 /* up into non-root node */
1977 vcn = ictx->parent_vcn[ictx->pindex];
1978 if (!ntfs_ib_read(ictx,vcn,ictx->ib)) {
1979 entry = ntfs_ie_get_by_pos(
1980 &ictx->ib->index,
1981 ictx->parent_pos[ictx->pindex]);
1982 } else
1983 entry = (INDEX_ENTRY*)NULL;
1984 }
1985 ictx->entry = entry;
1986 } while (entry && (ictx->pindex > 0)
1987 && (entry->ie_flags & INDEX_ENTRY_END));
1988 } else
1989 entry = (INDEX_ENTRY*)NULL;
1990 return (entry);
1991}
1992
1993/*
1994 * Get next entry in an index according to collating sequence.
1995 * Must be initialized through a ntfs_index_lookup()
1996 *
1997 * Returns next entry or NULL if none
1998 *
1999 * Sample layout :
2000 *
2001 * +---+---+---+---+---+---+---+---+ n ptrs to subnodes
2002 * | | | 10| 25| 33| | | | n-1 keys in between
2003 * +---+---+---+---+---+---+---+---+ no key in last entry
2004 * | A | A
2005 * | | | +-------------------------------+
2006 * +--------------------------+ | +-----+ |
2007 * | +--+ | |
2008 * V | V |
2009 * +---+---+---+---+---+---+---+---+ | +---+---+---+---+---+---+---+---+
2010 * | 11| 12| 13| 14| 15| 16| 17| | | | 26| 27| 28| 29| 30| 31| 32| |
2011 * +---+---+---+---+---+---+---+---+ | +---+---+---+---+---+---+---+---+
2012 * | |
2013 * +-----------------------+ |
2014 * | |
2015 * +---+---+---+---+---+---+---+---+
2016 * | 18| 19| 20| 21| 22| 23| 24| |
2017 * +---+---+---+---+---+---+---+---+
2018 */
2019
2020INDEX_ENTRY *ntfs_index_next(INDEX_ENTRY *ie, ntfs_index_context *ictx)
2021{
2022 INDEX_ENTRY *next;
2023 int flags;
2024
2025 /*
2026 * lookup() may have returned an invalid node
2027 * when searching for a partial key
2028 * if this happens, walk up
2029 */
2030
2031 if (ie->ie_flags & INDEX_ENTRY_END)
2032 next = ntfs_index_walk_up(ie, ictx);
2033 else {
2034 /*
2035 * get next entry in same node
2036 * there is always one after any entry with data
2037 */
2038
2039 next = (INDEX_ENTRY*)((char*)ie + le16_to_cpu(ie->length));
2040 ++ictx->parent_pos[ictx->pindex];
2041 flags = next->ie_flags;
2042
2043 /* walk down if it has a subnode */
2044
2045 if (flags & INDEX_ENTRY_NODE) {
2046 next = ntfs_index_walk_down(next,ictx);
2047 } else {
2048
2049 /* walk up it has no subnode, nor data */
2050
2051 if (flags & INDEX_ENTRY_END) {
2052 next = ntfs_index_walk_up(next, ictx);
2053 }
2054 }
2055 }
2056 /* return NULL if stuck at end of a block */
2057
2058 if (next && (next->ie_flags & INDEX_ENTRY_END))
2059 next = (INDEX_ENTRY*)NULL;
2060 return (next);
2061}
2062
2063
2064
generated by cgit at 2024-05-19 02:22:55 (GMT)