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 | */ |
65 | void ntfs_index_entry_mark_dirty(ntfs_index_context *ictx) |
66 | { |
67 | if (ictx->is_in_root) |
68 | ntfs_inode_mark_dirty(ictx->actx->ntfs_ino); |
69 | else |
70 | ictx->ib_dirty = TRUE; |
71 | } |
72 | |
73 | static s64 ntfs_ib_vcn_to_pos(ntfs_index_context *icx, VCN vcn) |
74 | { |
75 | return vcn << icx->vcn_size_bits; |
76 | } |
77 | |
78 | static VCN ntfs_ib_pos_to_vcn(ntfs_index_context *icx, s64 pos) |
79 | { |
80 | return pos >> icx->vcn_size_bits; |
81 | } |
82 | |
83 | static int ntfs_ib_write(ntfs_index_context *icx, INDEX_BLOCK *ib) |
84 | { |
85 | s64 ret, vcn = sle64_to_cpu(ib->index_block_vcn); |
86 | |
87 | ntfs_log_trace("vcn: %lld\n", (long long)vcn); |
88 | |
89 | ret = ntfs_attr_mst_pwrite(icx->ia_na, ntfs_ib_vcn_to_pos(icx, vcn), |
90 | 1, icx->block_size, ib); |
91 | if (ret != 1) { |
92 | ntfs_log_perror("Failed to write index block %lld, inode %llu", |
93 | (long long)vcn, (unsigned long long)icx->ni->mft_no); |
94 | return STATUS_ERROR; |
95 | } |
96 | |
97 | return STATUS_OK; |
98 | } |
99 | |
100 | static int ntfs_icx_ib_write(ntfs_index_context *icx) |
101 | { |
102 | if (ntfs_ib_write(icx, icx->ib)) |
103 | return STATUS_ERROR; |
104 | |
105 | icx->ib_dirty = FALSE; |
106 | |
107 | return STATUS_OK; |
108 | } |
109 | |
110 | /** |
111 | * ntfs_index_ctx_get - allocate and initialize a new index context |
112 | * @ni: ntfs inode with which to initialize the context |
113 | * @name: name of the which context describes |
114 | * @name_len: length of the index name |
115 | * |
116 | * Allocate a new index context, initialize it with @ni and return it. |
117 | * Return NULL if allocation failed. |
118 | */ |
119 | ntfs_index_context *ntfs_index_ctx_get(ntfs_inode *ni, |
120 | ntfschar *name, u32 name_len) |
121 | { |
122 | ntfs_index_context *icx; |
123 | |
124 | ntfs_log_trace("Entering\n"); |
125 | |
126 | if (!ni) { |
127 | errno = EINVAL; |
128 | return NULL; |
129 | } |
130 | if (ni->nr_extents == -1) |
131 | ni = ni->base_ni; |
132 | icx = ntfs_calloc(sizeof(ntfs_index_context)); |
133 | if (icx) |
134 | *icx = (ntfs_index_context) { |
135 | .ni = ni, |
136 | .name = name, |
137 | .name_len = name_len, |
138 | }; |
139 | return icx; |
140 | } |
141 | |
142 | static void ntfs_index_ctx_free(ntfs_index_context *icx) |
143 | { |
144 | ntfs_log_trace("Entering\n"); |
145 | |
146 | if (!icx->entry) |
147 | return; |
148 | |
149 | if (icx->actx) |
150 | ntfs_attr_put_search_ctx(icx->actx); |
151 | |
152 | if (!icx->is_in_root) { |
153 | if (icx->ib_dirty) { |
154 | /* FIXME: Error handling!!! */ |
155 | ntfs_ib_write(icx, icx->ib); |
156 | } |
157 | free(icx->ib); |
158 | } |
159 | |
160 | ntfs_attr_close(icx->ia_na); |
161 | } |
162 | |
163 | /** |
164 | * ntfs_index_ctx_put - release an index context |
165 | * @icx: index context to free |
166 | * |
167 | * Release the index context @icx, releasing all associated resources. |
168 | */ |
169 | void ntfs_index_ctx_put(ntfs_index_context *icx) |
170 | { |
171 | ntfs_index_ctx_free(icx); |
172 | free(icx); |
173 | } |
174 | |
175 | /** |
176 | * ntfs_index_ctx_reinit - reinitialize an index context |
177 | * @icx: index context to reinitialize |
178 | * |
179 | * Reinitialize the index context @icx so it can be used for ntfs_index_lookup. |
180 | */ |
181 | void ntfs_index_ctx_reinit(ntfs_index_context *icx) |
182 | { |
183 | ntfs_log_trace("Entering\n"); |
184 | |
185 | ntfs_index_ctx_free(icx); |
186 | |
187 | *icx = (ntfs_index_context) { |
188 | .ni = icx->ni, |
189 | .name = icx->name, |
190 | .name_len = icx->name_len, |
191 | }; |
192 | } |
193 | |
194 | static VCN *ntfs_ie_get_vcn_addr(INDEX_ENTRY *ie) |
195 | { |
196 | return (VCN *)((u8 *)ie + le16_to_cpu(ie->length) - sizeof(VCN)); |
197 | } |
198 | |
199 | /** |
200 | * Get the subnode vcn to which the index entry refers. |
201 | */ |
202 | VCN ntfs_ie_get_vcn(INDEX_ENTRY *ie) |
203 | { |
204 | return sle64_to_cpup(ntfs_ie_get_vcn_addr(ie)); |
205 | } |
206 | |
207 | static INDEX_ENTRY *ntfs_ie_get_first(INDEX_HEADER *ih) |
208 | { |
209 | return (INDEX_ENTRY *)((u8 *)ih + le32_to_cpu(ih->entries_offset)); |
210 | } |
211 | |
212 | static INDEX_ENTRY *ntfs_ie_get_next(INDEX_ENTRY *ie) |
213 | { |
214 | return (INDEX_ENTRY *)((char *)ie + le16_to_cpu(ie->length)); |
215 | } |
216 | |
217 | static u8 *ntfs_ie_get_end(INDEX_HEADER *ih) |
218 | { |
219 | /* FIXME: check if it isn't overflowing the index block size */ |
220 | return (u8 *)ih + le32_to_cpu(ih->index_length); |
221 | } |
222 | |
223 | static int ntfs_ie_end(INDEX_ENTRY *ie) |
224 | { |
225 | return ie->ie_flags & INDEX_ENTRY_END || !ie->length; |
226 | } |
227 | |
228 | /** |
229 | * Find the last entry in the index block |
230 | */ |
231 | static INDEX_ENTRY *ntfs_ie_get_last(INDEX_ENTRY *ie, char *ies_end) |
232 | { |
233 | ntfs_log_trace("Entering\n"); |
234 | |
235 | while ((char *)ie < ies_end && !ntfs_ie_end(ie)) |
236 | ie = ntfs_ie_get_next(ie); |
237 | |
238 | return ie; |
239 | } |
240 | |
241 | static INDEX_ENTRY *ntfs_ie_get_by_pos(INDEX_HEADER *ih, int pos) |
242 | { |
243 | INDEX_ENTRY *ie; |
244 | |
245 | ntfs_log_trace("pos: %d\n", pos); |
246 | |
247 | ie = ntfs_ie_get_first(ih); |
248 | |
249 | while (pos-- > 0) |
250 | ie = ntfs_ie_get_next(ie); |
251 | |
252 | return ie; |
253 | } |
254 | |
255 | static INDEX_ENTRY *ntfs_ie_prev(INDEX_HEADER *ih, INDEX_ENTRY *ie) |
256 | { |
257 | INDEX_ENTRY *ie_prev = NULL; |
258 | INDEX_ENTRY *tmp; |
259 | |
260 | ntfs_log_trace("Entering\n"); |
261 | |
262 | tmp = ntfs_ie_get_first(ih); |
263 | |
264 | while (tmp != ie) { |
265 | ie_prev = tmp; |
266 | tmp = ntfs_ie_get_next(tmp); |
267 | } |
268 | |
269 | return ie_prev; |
270 | } |
271 | |
272 | char *ntfs_ie_filename_get(INDEX_ENTRY *ie) |
273 | { |
274 | FILE_NAME_ATTR *fn; |
275 | |
276 | fn = (FILE_NAME_ATTR *)&ie->key; |
277 | return ntfs_attr_name_get(fn->file_name, fn->file_name_length); |
278 | } |
279 | |
280 | void ntfs_ie_filename_dump(INDEX_ENTRY *ie) |
281 | { |
282 | char *s; |
283 | |
284 | s = ntfs_ie_filename_get(ie); |
285 | ntfs_log_debug("'%s' ", s); |
286 | ntfs_attr_name_free(&s); |
287 | } |
288 | |
289 | void ntfs_ih_filename_dump(INDEX_HEADER *ih) |
290 | { |
291 | INDEX_ENTRY *ie; |
292 | |
293 | ntfs_log_trace("Entering\n"); |
294 | |
295 | ie = ntfs_ie_get_first(ih); |
296 | while (!ntfs_ie_end(ie)) { |
297 | ntfs_ie_filename_dump(ie); |
298 | ie = ntfs_ie_get_next(ie); |
299 | } |
300 | } |
301 | |
302 | static int ntfs_ih_numof_entries(INDEX_HEADER *ih) |
303 | { |
304 | int n; |
305 | INDEX_ENTRY *ie; |
306 | u8 *end; |
307 | |
308 | ntfs_log_trace("Entering\n"); |
309 | |
310 | end = ntfs_ie_get_end(ih); |
311 | ie = ntfs_ie_get_first(ih); |
312 | for (n = 0; !ntfs_ie_end(ie) && (u8 *)ie < end; n++) |
313 | ie = ntfs_ie_get_next(ie); |
314 | return n; |
315 | } |
316 | |
317 | static int ntfs_ih_one_entry(INDEX_HEADER *ih) |
318 | { |
319 | return (ntfs_ih_numof_entries(ih) == 1); |
320 | } |
321 | |
322 | static int ntfs_ih_zero_entry(INDEX_HEADER *ih) |
323 | { |
324 | return (ntfs_ih_numof_entries(ih) == 0); |
325 | } |
326 | |
327 | static void ntfs_ie_delete(INDEX_HEADER *ih, INDEX_ENTRY *ie) |
328 | { |
329 | u32 new_size; |
330 | |
331 | ntfs_log_trace("Entering\n"); |
332 | |
333 | new_size = le32_to_cpu(ih->index_length) - le16_to_cpu(ie->length); |
334 | ih->index_length = cpu_to_le32(new_size); |
335 | memmove(ie, (u8 *)ie + le16_to_cpu(ie->length), |
336 | new_size - ((u8 *)ie - (u8 *)ih)); |
337 | } |
338 | |
339 | static void ntfs_ie_set_vcn(INDEX_ENTRY *ie, VCN vcn) |
340 | { |
341 | *ntfs_ie_get_vcn_addr(ie) = cpu_to_le64(vcn); |
342 | } |
343 | |
344 | /** |
345 | * Insert @ie index entry at @pos entry. Used @ih values should be ok already. |
346 | */ |
347 | static void ntfs_ie_insert(INDEX_HEADER *ih, INDEX_ENTRY *ie, INDEX_ENTRY *pos) |
348 | { |
349 | int ie_size = le16_to_cpu(ie->length); |
350 | |
351 | ntfs_log_trace("Entering\n"); |
352 | |
353 | ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) + ie_size); |
354 | memmove((u8 *)pos + ie_size, pos, |
355 | le32_to_cpu(ih->index_length) - ((u8 *)pos - (u8 *)ih) - ie_size); |
356 | memcpy(pos, ie, ie_size); |
357 | } |
358 | |
359 | static INDEX_ENTRY *ntfs_ie_dup(INDEX_ENTRY *ie) |
360 | { |
361 | INDEX_ENTRY *dup; |
362 | |
363 | ntfs_log_trace("Entering\n"); |
364 | |
365 | dup = ntfs_malloc(le16_to_cpu(ie->length)); |
366 | if (dup) |
367 | memcpy(dup, ie, le16_to_cpu(ie->length)); |
368 | |
369 | return dup; |
370 | } |
371 | |
372 | static INDEX_ENTRY *ntfs_ie_dup_novcn(INDEX_ENTRY *ie) |
373 | { |
374 | INDEX_ENTRY *dup; |
375 | int size = le16_to_cpu(ie->length); |
376 | |
377 | ntfs_log_trace("Entering\n"); |
378 | |
379 | if (ie->ie_flags & INDEX_ENTRY_NODE) |
380 | size -= sizeof(VCN); |
381 | |
382 | dup = ntfs_malloc(size); |
383 | if (dup) { |
384 | memcpy(dup, ie, size); |
385 | dup->ie_flags &= ~INDEX_ENTRY_NODE; |
386 | dup->length = cpu_to_le16(size); |
387 | } |
388 | return dup; |
389 | } |
390 | |
391 | static int ntfs_ia_check(ntfs_index_context *icx, INDEX_BLOCK *ib, VCN vcn) |
392 | { |
393 | u32 ib_size = (unsigned)le32_to_cpu(ib->index.allocated_size) + 0x18; |
394 | |
395 | ntfs_log_trace("Entering\n"); |
396 | |
397 | if (!ntfs_is_indx_record(ib->magic)) { |
398 | |
399 | ntfs_log_error("Corrupt index block signature: vcn %lld inode " |
400 | "%llu\n", (long long)vcn, |
401 | (unsigned long long)icx->ni->mft_no); |
402 | return -1; |
403 | } |
404 | |
405 | if (sle64_to_cpu(ib->index_block_vcn) != vcn) { |
406 | |
407 | ntfs_log_error("Corrupt index block: VCN (%lld) is different " |
408 | "from expected VCN (%lld) in inode %llu\n", |
409 | (long long)sle64_to_cpu(ib->index_block_vcn), |
410 | (long long)vcn, |
411 | (unsigned long long)icx->ni->mft_no); |
412 | return -1; |
413 | } |
414 | |
415 | if (ib_size != icx->block_size) { |
416 | |
417 | ntfs_log_error("Corrupt index block : VCN (%lld) of inode %llu " |
418 | "has a size (%u) differing from the index " |
419 | "specified size (%u)\n", (long long)vcn, |
420 | (unsigned long long)icx->ni->mft_no, ib_size, |
421 | icx->block_size); |
422 | return -1; |
423 | } |
424 | return 0; |
425 | } |
426 | |
427 | static INDEX_ROOT *ntfs_ir_lookup(ntfs_inode *ni, ntfschar *name, |
428 | u32 name_len, ntfs_attr_search_ctx **ctx) |
429 | { |
430 | ATTR_RECORD *a; |
431 | INDEX_ROOT *ir = NULL; |
432 | |
433 | ntfs_log_trace("Entering\n"); |
434 | |
435 | *ctx = ntfs_attr_get_search_ctx(ni, NULL); |
436 | if (!*ctx) |
437 | return NULL; |
438 | |
439 | if (ntfs_attr_lookup(AT_INDEX_ROOT, name, name_len, CASE_SENSITIVE, |
440 | 0, NULL, 0, *ctx)) { |
441 | ntfs_log_perror("Failed to lookup $INDEX_ROOT"); |
442 | goto err_out; |
443 | } |
444 | |
445 | a = (*ctx)->attr; |
446 | if (a->non_resident) { |
447 | errno = EINVAL; |
448 | ntfs_log_perror("Non-resident $INDEX_ROOT detected"); |
449 | goto err_out; |
450 | } |
451 | |
452 | ir = (INDEX_ROOT *)((char *)a + le16_to_cpu(a->value_offset)); |
453 | err_out: |
454 | if (!ir) { |
455 | ntfs_attr_put_search_ctx(*ctx); |
456 | *ctx = NULL; |
457 | } |
458 | return ir; |
459 | } |
460 | |
461 | static INDEX_ROOT *ntfs_ir_lookup2(ntfs_inode *ni, ntfschar *name, u32 len) |
462 | { |
463 | ntfs_attr_search_ctx *ctx; |
464 | INDEX_ROOT *ir; |
465 | |
466 | ir = ntfs_ir_lookup(ni, name, len, &ctx); |
467 | if (ir) |
468 | ntfs_attr_put_search_ctx(ctx); |
469 | return ir; |
470 | } |
471 | |
472 | /** |
473 | * Find a key in the index block. |
474 | * |
475 | * Return values: |
476 | * STATUS_OK with errno set to ESUCCESS if we know for sure that the |
477 | * entry exists and @ie_out points to this entry. |
478 | * STATUS_NOT_FOUND with errno set to ENOENT if we know for sure the |
479 | * entry doesn't exist and @ie_out is the insertion point. |
480 | * STATUS_KEEP_SEARCHING if we can't answer the above question and |
481 | * @vcn will contain the node index block. |
482 | * STATUS_ERROR with errno set if on unexpected error during lookup. |
483 | */ |
484 | static int ntfs_ie_lookup(const void *key, const int key_len, |
485 | ntfs_index_context *icx, INDEX_HEADER *ih, |
486 | VCN *vcn, INDEX_ENTRY **ie_out) |
487 | { |
488 | INDEX_ENTRY *ie; |
489 | u8 *index_end; |
490 | int rc, item = 0; |
491 | |
492 | ntfs_log_trace("Entering\n"); |
493 | |
494 | index_end = ntfs_ie_get_end(ih); |
495 | |
496 | /* |
497 | * Loop until we exceed valid memory (corruption case) or until we |
498 | * reach the last entry. |
499 | */ |
500 | for (ie = ntfs_ie_get_first(ih); ; ie = ntfs_ie_get_next(ie)) { |
501 | /* Bounds checks. */ |
502 | if ((u8 *)ie + sizeof(INDEX_ENTRY_HEADER) > index_end || |
503 | (u8 *)ie + le16_to_cpu(ie->length) > index_end) { |
504 | errno = ERANGE; |
505 | ntfs_log_error("Index entry out of bounds in inode " |
506 | "%llu.\n", |
507 | (unsigned long long)icx->ni->mft_no); |
508 | return STATUS_ERROR; |
509 | } |
510 | /* |
511 | * The last entry cannot contain a key. It can however contain |
512 | * a pointer to a child node in the B+tree so we just break out. |
513 | */ |
514 | if (ntfs_ie_end(ie)) |
515 | break; |
516 | /* |
517 | * Not a perfect match, need to do full blown collation so we |
518 | * know which way in the B+tree we have to go. |
519 | */ |
520 | if (!icx->collate) { |
521 | ntfs_log_error("Collation function not defined\n"); |
522 | errno = EOPNOTSUPP; |
523 | return STATUS_ERROR; |
524 | } |
525 | rc = icx->collate(icx->ni->vol, key, key_len, |
526 | &ie->key, le16_to_cpu(ie->key_length)); |
527 | if (rc == NTFS_COLLATION_ERROR) { |
528 | ntfs_log_error("Collation error. Perhaps a filename " |
529 | "contains invalid characters?\n"); |
530 | errno = ERANGE; |
531 | return STATUS_ERROR; |
532 | } |
533 | /* |
534 | * If @key collates before the key of the current entry, there |
535 | * is definitely no such key in this index but we might need to |
536 | * descend into the B+tree so we just break out of the loop. |
537 | */ |
538 | if (rc == -1) |
539 | break; |
540 | |
541 | if (!rc) { |
542 | *ie_out = ie; |
543 | errno = 0; |
544 | icx->parent_pos[icx->pindex] = item; |
545 | return STATUS_OK; |
546 | } |
547 | |
548 | item++; |
549 | } |
550 | /* |
551 | * We have finished with this index block without success. Check for the |
552 | * presence of a child node and if not present return with errno ENOENT, |
553 | * otherwise we will keep searching in another index block. |
554 | */ |
555 | if (!(ie->ie_flags & INDEX_ENTRY_NODE)) { |
556 | ntfs_log_debug("Index entry wasn't found.\n"); |
557 | *ie_out = ie; |
558 | errno = ENOENT; |
559 | return STATUS_NOT_FOUND; |
560 | } |
561 | |
562 | /* Get the starting vcn of the index_block holding the child node. */ |
563 | *vcn = ntfs_ie_get_vcn(ie); |
564 | if (*vcn < 0) { |
565 | errno = EINVAL; |
566 | ntfs_log_perror("Negative vcn in inode %llu", |
567 | (unsigned long long)icx->ni->mft_no); |
568 | return STATUS_ERROR; |
569 | } |
570 | |
571 | ntfs_log_trace("Parent entry number %d\n", item); |
572 | icx->parent_pos[icx->pindex] = item; |
573 | |
574 | return STATUS_KEEP_SEARCHING; |
575 | } |
576 | |
577 | static ntfs_attr *ntfs_ia_open(ntfs_index_context *icx, ntfs_inode *ni) |
578 | { |
579 | ntfs_attr *na; |
580 | |
581 | na = ntfs_attr_open(ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len); |
582 | if (!na) { |
583 | ntfs_log_perror("Failed to open index allocation of inode " |
584 | "%llu", (unsigned long long)ni->mft_no); |
585 | return NULL; |
586 | } |
587 | |
588 | return na; |
589 | } |
590 | |
591 | static int ntfs_ib_read(ntfs_index_context *icx, VCN vcn, INDEX_BLOCK *dst) |
592 | { |
593 | s64 pos, ret; |
594 | |
595 | ntfs_log_trace("vcn: %lld\n", (long long)vcn); |
596 | |
597 | pos = ntfs_ib_vcn_to_pos(icx, vcn); |
598 | |
599 | ret = ntfs_attr_mst_pread(icx->ia_na, pos, 1, icx->block_size, (u8 *)dst); |
600 | if (ret != 1) { |
601 | if (ret == -1) |
602 | ntfs_log_perror("Failed to read index block"); |
603 | else |
604 | ntfs_log_error("Failed to read full index block at " |
605 | "%lld\n", (long long)pos); |
606 | return -1; |
607 | } |
608 | |
609 | if (ntfs_ia_check(icx, dst, vcn)) |
610 | return -1; |
611 | |
612 | return 0; |
613 | } |
614 | |
615 | static int ntfs_icx_parent_inc(ntfs_index_context *icx) |
616 | { |
617 | icx->pindex++; |
618 | if (icx->pindex >= MAX_PARENT_VCN) { |
619 | errno = EOPNOTSUPP; |
620 | ntfs_log_perror("Index is over %d level deep", MAX_PARENT_VCN); |
621 | return STATUS_ERROR; |
622 | } |
623 | return STATUS_OK; |
624 | } |
625 | |
626 | static int ntfs_icx_parent_dec(ntfs_index_context *icx) |
627 | { |
628 | icx->pindex--; |
629 | if (icx->pindex < 0) { |
630 | errno = EINVAL; |
631 | ntfs_log_perror("Corrupt index pointer (%d)", icx->pindex); |
632 | return STATUS_ERROR; |
633 | } |
634 | return STATUS_OK; |
635 | } |
636 | |
637 | /** |
638 | * ntfs_index_lookup - find a key in an index and return its index entry |
639 | * @key: [IN] key for which to search in the index |
640 | * @key_len: [IN] length of @key in bytes |
641 | * @icx: [IN/OUT] context describing the index and the returned entry |
642 | * |
643 | * Before calling ntfs_index_lookup(), @icx must have been obtained from a |
644 | * call to ntfs_index_ctx_get(). |
645 | * |
646 | * Look for the @key in the index specified by the index lookup context @icx. |
647 | * ntfs_index_lookup() walks the contents of the index looking for the @key. |
648 | * |
649 | * If the @key is found in the index, 0 is returned and @icx is setup to |
650 | * describe the index entry containing the matching @key. @icx->entry is the |
651 | * index entry and @icx->data and @icx->data_len are the index entry data and |
652 | * its length in bytes, respectively. |
653 | * |
654 | * If the @key is not found in the index, -1 is returned, errno = ENOENT and |
655 | * @icx is setup to describe the index entry whose key collates immediately |
656 | * after the search @key, i.e. this is the position in the index at which |
657 | * an index entry with a key of @key would need to be inserted. |
658 | * |
659 | * If an error occurs return -1, set errno to error code and @icx is left |
660 | * untouched. |
661 | * |
662 | * When finished with the entry and its data, call ntfs_index_ctx_put() to free |
663 | * the context and other associated resources. |
664 | * |
665 | * If the index entry was modified, call ntfs_index_entry_mark_dirty() before |
666 | * the call to ntfs_index_ctx_put() to ensure that the changes are written |
667 | * to disk. |
668 | */ |
669 | int ntfs_index_lookup(const void *key, const int key_len, ntfs_index_context *icx) |
670 | { |
671 | VCN old_vcn, vcn; |
672 | ntfs_inode *ni = icx->ni; |
673 | INDEX_ROOT *ir; |
674 | INDEX_ENTRY *ie; |
675 | INDEX_BLOCK *ib = NULL; |
676 | int ret, err = 0; |
677 | |
678 | ntfs_log_trace("Entering\n"); |
679 | |
680 | if (!key || key_len <= 0) { |
681 | errno = EINVAL; |
682 | ntfs_log_perror("key: %p key_len: %d", key, key_len); |
683 | return -1; |
684 | } |
685 | |
686 | ir = ntfs_ir_lookup(ni, icx->name, icx->name_len, &icx->actx); |
687 | if (!ir) { |
688 | if (errno == ENOENT) |
689 | errno = EIO; |
690 | return -1; |
691 | } |
692 | |
693 | icx->block_size = le32_to_cpu(ir->index_block_size); |
694 | if (icx->block_size < NTFS_BLOCK_SIZE) { |
695 | errno = EINVAL; |
696 | ntfs_log_perror("Index block size (%d) is smaller than the " |
697 | "sector size (%d)", icx->block_size, NTFS_BLOCK_SIZE); |
698 | goto err_out; |
699 | } |
700 | |
701 | if (ni->vol->cluster_size <= icx->block_size) |
702 | icx->vcn_size_bits = ni->vol->cluster_size_bits; |
703 | else |
704 | icx->vcn_size_bits = 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 | |
747 | descend_into_child_node: |
748 | |
749 | icx->parent_vcn[icx->pindex] = old_vcn; |
750 | if (ntfs_icx_parent_inc(icx)) { |
751 | err = errno; |
752 | goto err_out; |
753 | } |
754 | old_vcn = vcn; |
755 | |
756 | ntfs_log_debug("Descend into node with VCN %lld\n", (long long)vcn); |
757 | |
758 | if (ntfs_ib_read(icx, vcn, ib)) |
759 | goto err_out; |
760 | |
761 | ret = ntfs_ie_lookup(key, key_len, icx, &ib->index, &vcn, &ie); |
762 | if (ret != STATUS_KEEP_SEARCHING) { |
763 | err = errno; |
764 | if (ret == STATUS_ERROR) |
765 | goto err_out; |
766 | |
767 | /* STATUS_OK or STATUS_NOT_FOUND */ |
768 | icx->is_in_root = FALSE; |
769 | icx->ib = ib; |
770 | icx->parent_vcn[icx->pindex] = vcn; |
771 | goto done; |
772 | } |
773 | |
774 | if ((ib->index.ih_flags & NODE_MASK) == LEAF_NODE) { |
775 | ntfs_log_error("Index entry with child node found in a leaf " |
776 | "node in inode 0x%llx.\n", |
777 | (unsigned long long)ni->mft_no); |
778 | goto err_out; |
779 | } |
780 | |
781 | goto descend_into_child_node; |
782 | err_out: |
783 | free(ib); |
784 | if (!err) |
785 | err = EIO; |
786 | errno = err; |
787 | return -1; |
788 | done: |
789 | icx->entry = ie; |
790 | icx->data = (u8 *)ie + offsetof(INDEX_ENTRY, key); |
791 | icx->data_len = le16_to_cpu(ie->key_length); |
792 | ntfs_log_trace("Done.\n"); |
793 | if (err) { |
794 | errno = err; |
795 | return -1; |
796 | } |
797 | return 0; |
798 | |
799 | } |
800 | |
801 | static INDEX_BLOCK *ntfs_ib_alloc(VCN ib_vcn, u32 ib_size, |
802 | INDEX_HEADER_FLAGS node_type) |
803 | { |
804 | INDEX_BLOCK *ib; |
805 | int ih_size = sizeof(INDEX_HEADER); |
806 | |
807 | ntfs_log_trace("ib_vcn: %lld ib_size: %u\n", (long long)ib_vcn, ib_size); |
808 | |
809 | ib = ntfs_calloc(ib_size); |
810 | if (!ib) |
811 | return NULL; |
812 | |
813 | ib->magic = magic_INDX; |
814 | ib->usa_ofs = cpu_to_le16(sizeof(INDEX_BLOCK)); |
815 | ib->usa_count = cpu_to_le16(ib_size / NTFS_BLOCK_SIZE + 1); |
816 | /* Set USN to 1 */ |
817 | *(u16 *)((char *)ib + le16_to_cpu(ib->usa_ofs)) = cpu_to_le16(1); |
818 | ib->lsn = cpu_to_le64(0); |
819 | |
820 | ib->index_block_vcn = cpu_to_sle64(ib_vcn); |
821 | |
822 | ib->index.entries_offset = cpu_to_le32((ih_size + |
823 | le16_to_cpu(ib->usa_count) * 2 + 7) & ~7); |
824 | ib->index.index_length = 0; |
825 | ib->index.allocated_size = cpu_to_le32(ib_size - |
826 | (sizeof(INDEX_BLOCK) - ih_size)); |
827 | ib->index.ih_flags = node_type; |
828 | |
829 | return ib; |
830 | } |
831 | |
832 | /** |
833 | * Find the median by going through all the entries |
834 | */ |
835 | static INDEX_ENTRY *ntfs_ie_get_median(INDEX_HEADER *ih) |
836 | { |
837 | INDEX_ENTRY *ie, *ie_start; |
838 | u8 *ie_end; |
839 | int i = 0, median; |
840 | |
841 | ntfs_log_trace("Entering\n"); |
842 | |
843 | ie = ie_start = ntfs_ie_get_first(ih); |
844 | ie_end = (u8 *)ntfs_ie_get_end(ih); |
845 | |
846 | while ((u8 *)ie < ie_end && !ntfs_ie_end(ie)) { |
847 | ie = ntfs_ie_get_next(ie); |
848 | i++; |
849 | } |
850 | /* |
851 | * NOTE: this could be also the entry at the half of the index block. |
852 | */ |
853 | median = i / 2 - 1; |
854 | |
855 | ntfs_log_trace("Entries: %d median: %d\n", i, median); |
856 | |
857 | for (i = 0, ie = ie_start; i <= median; i++) |
858 | ie = ntfs_ie_get_next(ie); |
859 | |
860 | return ie; |
861 | } |
862 | |
863 | static s64 ntfs_ibm_vcn_to_pos(ntfs_index_context *icx, VCN vcn) |
864 | { |
865 | return ntfs_ib_vcn_to_pos(icx, vcn) / icx->block_size; |
866 | } |
867 | |
868 | static s64 ntfs_ibm_pos_to_vcn(ntfs_index_context *icx, s64 pos) |
869 | { |
870 | return ntfs_ib_pos_to_vcn(icx, pos * icx->block_size); |
871 | } |
872 | |
873 | static int ntfs_ibm_add(ntfs_index_context *icx) |
874 | { |
875 | u8 bmp[8]; |
876 | |
877 | ntfs_log_trace("Entering\n"); |
878 | |
879 | if (ntfs_attr_exist(icx->ni, AT_BITMAP, icx->name, icx->name_len)) |
880 | return STATUS_OK; |
881 | /* |
882 | * AT_BITMAP must be at least 8 bytes. |
883 | */ |
884 | memset(bmp, 0, sizeof(bmp)); |
885 | if (ntfs_attr_add(icx->ni, AT_BITMAP, icx->name, icx->name_len, |
886 | bmp, sizeof(bmp))) { |
887 | ntfs_log_perror("Failed to add AT_BITMAP"); |
888 | return STATUS_ERROR; |
889 | } |
890 | |
891 | return STATUS_OK; |
892 | } |
893 | |
894 | static int ntfs_ibm_modify(ntfs_index_context *icx, VCN vcn, int set) |
895 | { |
896 | u8 byte; |
897 | s64 pos = ntfs_ibm_vcn_to_pos(icx, vcn); |
898 | u32 bpos = pos / 8; |
899 | u32 bit = 1 << (pos % 8); |
900 | ntfs_attr *na; |
901 | int ret = STATUS_ERROR; |
902 | |
903 | ntfs_log_trace("%s vcn: %lld\n", set ? "set" : "clear", (long long)vcn); |
904 | |
905 | na = ntfs_attr_open(icx->ni, AT_BITMAP, icx->name, icx->name_len); |
906 | if (!na) { |
907 | ntfs_log_perror("Failed to open $BITMAP attribute"); |
908 | return -1; |
909 | } |
910 | |
911 | if (set) { |
912 | if (na->data_size < bpos + 1) { |
913 | if (ntfs_attr_truncate(na, (na->data_size + 8) & ~7)) { |
914 | ntfs_log_perror("Failed to truncate AT_BITMAP"); |
915 | goto err_na; |
916 | } |
917 | } |
918 | } |
919 | |
920 | if (ntfs_attr_pread(na, bpos, 1, &byte) != 1) { |
921 | ntfs_log_perror("Failed to read $BITMAP"); |
922 | goto err_na; |
923 | } |
924 | |
925 | if (set) |
926 | byte |= bit; |
927 | else |
928 | byte &= ~bit; |
929 | |
930 | if (ntfs_attr_pwrite(na, bpos, 1, &byte) != 1) { |
931 | ntfs_log_perror("Failed to write $Bitmap"); |
932 | goto err_na; |
933 | } |
934 | |
935 | ret = STATUS_OK; |
936 | err_na: |
937 | ntfs_attr_close(na); |
938 | return ret; |
939 | } |
940 | |
941 | |
942 | static int ntfs_ibm_set(ntfs_index_context *icx, VCN vcn) |
943 | { |
944 | return ntfs_ibm_modify(icx, vcn, 1); |
945 | } |
946 | |
947 | static int ntfs_ibm_clear(ntfs_index_context *icx, VCN vcn) |
948 | { |
949 | return ntfs_ibm_modify(icx, vcn, 0); |
950 | } |
951 | |
952 | static VCN ntfs_ibm_get_free(ntfs_index_context *icx) |
953 | { |
954 | u8 *bm; |
955 | int bit; |
956 | s64 vcn, byte, size; |
957 | |
958 | ntfs_log_trace("Entering\n"); |
959 | |
960 | bm = ntfs_attr_readall(icx->ni, AT_BITMAP, icx->name, icx->name_len, |
961 | &size); |
962 | if (!bm) |
963 | return (VCN)-1; |
964 | |
965 | for (byte = 0; byte < size; byte++) { |
966 | |
967 | if (bm[byte] == 255) |
968 | continue; |
969 | |
970 | for (bit = 0; bit < 8; bit++) { |
971 | if (!(bm[byte] & (1 << bit))) { |
972 | vcn = ntfs_ibm_pos_to_vcn(icx, byte * 8 + bit); |
973 | goto out; |
974 | } |
975 | } |
976 | } |
977 | |
978 | vcn = ntfs_ibm_pos_to_vcn(icx, size * 8); |
979 | out: |
980 | ntfs_log_trace("allocated vcn: %lld\n", (long long)vcn); |
981 | |
982 | if (ntfs_ibm_set(icx, vcn)) |
983 | vcn = (VCN)-1; |
984 | |
985 | free(bm); |
986 | return vcn; |
987 | } |
988 | |
989 | static INDEX_BLOCK *ntfs_ir_to_ib(INDEX_ROOT *ir, VCN ib_vcn) |
990 | { |
991 | INDEX_BLOCK *ib; |
992 | INDEX_ENTRY *ie_last; |
993 | char *ies_start, *ies_end; |
994 | int i; |
995 | |
996 | ntfs_log_trace("Entering\n"); |
997 | |
998 | ib = ntfs_ib_alloc(ib_vcn, le32_to_cpu(ir->index_block_size), LEAF_NODE); |
999 | if (!ib) |
1000 | return NULL; |
1001 | |
1002 | ies_start = (char *)ntfs_ie_get_first(&ir->index); |
1003 | ies_end = (char *)ntfs_ie_get_end(&ir->index); |
1004 | ie_last = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end); |
1005 | /* |
1006 | * Copy all entries, including the termination entry |
1007 | * as well, which can never have any data. |
1008 | */ |
1009 | i = (char *)ie_last - ies_start + le16_to_cpu(ie_last->length); |
1010 | memcpy(ntfs_ie_get_first(&ib->index), ies_start, i); |
1011 | |
1012 | ib->index.ih_flags = ir->index.ih_flags; |
1013 | ib->index.index_length = cpu_to_le32(i + |
1014 | le32_to_cpu(ib->index.entries_offset)); |
1015 | return ib; |
1016 | } |
1017 | |
1018 | static void ntfs_ir_nill(INDEX_ROOT *ir) |
1019 | { |
1020 | INDEX_ENTRY *ie_last; |
1021 | char *ies_start, *ies_end; |
1022 | |
1023 | ntfs_log_trace("Entering\n"); |
1024 | /* |
1025 | * TODO: This function could be much simpler. |
1026 | */ |
1027 | ies_start = (char *)ntfs_ie_get_first(&ir->index); |
1028 | ies_end = (char *)ntfs_ie_get_end(&ir->index); |
1029 | ie_last = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end); |
1030 | /* |
1031 | * Move the index root termination entry forward |
1032 | */ |
1033 | if ((char *)ie_last > ies_start) { |
1034 | memmove(ies_start, (char *)ie_last, le16_to_cpu(ie_last->length)); |
1035 | ie_last = (INDEX_ENTRY *)ies_start; |
1036 | } |
1037 | } |
1038 | |
1039 | static int ntfs_ib_copy_tail(ntfs_index_context *icx, INDEX_BLOCK *src, |
1040 | INDEX_ENTRY *median, VCN new_vcn) |
1041 | { |
1042 | u8 *ies_end; |
1043 | INDEX_ENTRY *ie_head; /* first entry after the median */ |
1044 | int tail_size, ret; |
1045 | INDEX_BLOCK *dst; |
1046 | |
1047 | ntfs_log_trace("Entering\n"); |
1048 | |
1049 | dst = ntfs_ib_alloc(new_vcn, icx->block_size, |
1050 | src->index.ih_flags & NODE_MASK); |
1051 | if (!dst) |
1052 | return STATUS_ERROR; |
1053 | |
1054 | ie_head = ntfs_ie_get_next(median); |
1055 | |
1056 | ies_end = (u8 *)ntfs_ie_get_end(&src->index); |
1057 | tail_size = ies_end - (u8 *)ie_head; |
1058 | memcpy(ntfs_ie_get_first(&dst->index), ie_head, tail_size); |
1059 | |
1060 | dst->index.index_length = cpu_to_le32(tail_size + |
1061 | le32_to_cpu(dst->index.entries_offset)); |
1062 | ret = ntfs_ib_write(icx, dst); |
1063 | |
1064 | free(dst); |
1065 | return ret; |
1066 | } |
1067 | |
1068 | static int ntfs_ib_cut_tail(ntfs_index_context *icx, INDEX_BLOCK *ib, |
1069 | INDEX_ENTRY *ie) |
1070 | { |
1071 | char *ies_start, *ies_end; |
1072 | INDEX_ENTRY *ie_last; |
1073 | |
1074 | ntfs_log_trace("Entering\n"); |
1075 | |
1076 | ies_start = (char *)ntfs_ie_get_first(&ib->index); |
1077 | ies_end = (char *)ntfs_ie_get_end(&ib->index); |
1078 | |
1079 | ie_last = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end); |
1080 | if (ie_last->ie_flags & INDEX_ENTRY_NODE) |
1081 | ntfs_ie_set_vcn(ie_last, ntfs_ie_get_vcn(ie)); |
1082 | |
1083 | memcpy(ie, ie_last, le16_to_cpu(ie_last->length)); |
1084 | |
1085 | ib->index.index_length = cpu_to_le32(((char *)ie - ies_start) + |
1086 | le16_to_cpu(ie->length) + le32_to_cpu(ib->index.entries_offset)); |
1087 | |
1088 | if (ntfs_ib_write(icx, ib)) |
1089 | return STATUS_ERROR; |
1090 | |
1091 | return STATUS_OK; |
1092 | } |
1093 | |
1094 | static int ntfs_ia_add(ntfs_index_context *icx) |
1095 | { |
1096 | ntfs_log_trace("Entering\n"); |
1097 | |
1098 | if (ntfs_ibm_add(icx)) |
1099 | return -1; |
1100 | |
1101 | if (!ntfs_attr_exist(icx->ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len)) { |
1102 | |
1103 | if (ntfs_attr_add(icx->ni, AT_INDEX_ALLOCATION, icx->name, |
1104 | icx->name_len, NULL, 0)) { |
1105 | ntfs_log_perror("Failed to add AT_INDEX_ALLOCATION"); |
1106 | return -1; |
1107 | } |
1108 | } |
1109 | |
1110 | icx->ia_na = ntfs_ia_open(icx, icx->ni); |
1111 | if (!icx->ia_na) |
1112 | return -1; |
1113 | |
1114 | return 0; |
1115 | } |
1116 | |
1117 | static int ntfs_ir_reparent(ntfs_index_context *icx) |
1118 | { |
1119 | ntfs_attr_search_ctx *ctx = NULL; |
1120 | INDEX_ROOT *ir; |
1121 | INDEX_ENTRY *ie; |
1122 | INDEX_BLOCK *ib = NULL; |
1123 | VCN new_ib_vcn; |
1124 | int 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; |
1180 | err_out: |
1181 | free(ib); |
1182 | ntfs_attr_put_search_ctx(ctx); |
1183 | out: |
1184 | return ret; |
1185 | clear_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 | */ |
1195 | static 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 | */ |
1233 | static 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 | */ |
1255 | static 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 | |
1270 | static 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; |
1294 | out: |
1295 | free(ie); |
1296 | |
1297 | return ret; |
1298 | } |
1299 | |
1300 | static VCN ntfs_icx_parent_vcn(ntfs_index_context *icx) |
1301 | { |
1302 | return icx->parent_vcn[icx->pindex]; |
1303 | } |
1304 | |
1305 | static VCN ntfs_icx_parent_pos(ntfs_index_context *icx) |
1306 | { |
1307 | return icx->parent_pos[icx->pindex]; |
1308 | } |
1309 | |
1310 | |
1311 | static 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 | |
1340 | static 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 | */ |
1346 | static 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; |
1381 | err_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 | */ |
1392 | static 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 */ |
1429 | int 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; |
1486 | err_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 | */ |
1499 | int 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; |
1534 | out: |
1535 | free(ie); |
1536 | return ret; |
1537 | } |
1538 | |
1539 | static 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); |
1562 | out: |
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 | */ |
1571 | static 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 | */ |
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 | |
1604 | return ntfs_ih_takeout(icx, ih, ie_prev, ib); |
1605 | } |
1606 | |
1607 | static 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; |
1654 | ok: |
1655 | ret = STATUS_OK; |
1656 | out: |
1657 | free(ib); |
1658 | return ret; |
1659 | } |
1660 | |
1661 | static 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; |
1686 | descend: |
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; |
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 | /*static JPA*/ |
1780 | int 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 | } |
1816 | out: |
1817 | return ret; |
1818 | err_out: |
1819 | ret = STATUS_ERROR; |
1820 | goto out; |
1821 | } |
1822 | |
1823 | int 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); |
1856 | out: |
1857 | ntfs_index_ctx_put(icx); |
1858 | return ret; |
1859 | err_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 | */ |
1877 | INDEX_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))); |
1894 | out: |
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 | |
1906 | static 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 | |
1946 | static 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 | |
2020 | INDEX_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 |