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