File: /usr/src/linux/fs/ntfs/dir.c
1 /*
2 * dir.c
3 *
4 * Copyright (C) 1995-1997, 1999 Martin von Löwis
5 * Copyright (C) 1999 Steve Dodd
6 * Copyright (C) 1999 Joseph Malicki
7 * Copyright (C) 2001 Anton Altaparmakov (AIA)
8 */
9
10 #include "ntfstypes.h"
11 #include "struct.h"
12 #include "dir.h"
13 #include "macros.h"
14
15 #include <linux/errno.h>
16 #include "super.h"
17 #include "inode.h"
18 #include "attr.h"
19 #include "support.h"
20 #include "util.h"
21 #include <linux/smp_lock.h>
22
23 static char I30[] = "$I30";
24
25 /* An index record should start with INDX, and the last word in each block
26 * should contain the check value. If it passes, the original values need to
27 * be restored. */
28 int ntfs_check_index_record(ntfs_inode *ino, char *record)
29 {
30 return ntfs_fixup_record(record, "INDX", ino->u.index.recordsize);
31 }
32
33 static inline int ntfs_is_top(ntfs_u64 stack)
34 {
35 return stack == 14;
36 }
37
38 static int ntfs_pop(ntfs_u64 *stack)
39 {
40 static int width[16] = {1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,-1};
41 int res = -1;
42
43 switch (width[*stack & 15]) {
44 case 1:
45 res = (int)((*stack & 15) >> 1);
46 *stack >>= 4;
47 break;
48 case 2:
49 res = (int)(((*stack & 63) >> 2) + 7);
50 *stack >>= 6;
51 break;
52 case 3:
53 res = (int)(((*stack & 255) >> 3) + 23);
54 *stack >>= 8;
55 break;
56 case 4:
57 res = (int)(((*stack & 1023) >> 4) + 55);
58 *stack >>= 10;
59 break;
60 default:
61 ntfs_error("Unknown encoding\n");
62 }
63 return res;
64 }
65
66 static inline unsigned int ntfs_top(void)
67 {
68 return 14;
69 }
70
71 static ntfs_u64 ntfs_push(ntfs_u64 stack, int i)
72 {
73 if (i < 7)
74 return (stack << 4) | (i << 1);
75 if (i < 23)
76 return (stack << 6) | ((i - 7) << 2) | 1;
77 if (i < 55)
78 return (stack << 8) | ((i - 23) << 3) | 3;
79 if (i < 120)
80 return (stack << 10) | ((i - 55) << 4) | 7;
81 ntfs_error("Too many entries\n");
82 return ~((ntfs_u64)0);
83 }
84
85 #if 0
86 static void ntfs_display_stack(ntfs_u64 stack)
87 {
88 while(!ntfs_is_top(stack))
89 {
90 printf("%d ", ntfs_pop(&stack));
91 }
92 printf("\n");
93 }
94 #endif
95
96 /* True if the entry points to another block of entries. */
97 static inline int ntfs_entry_has_subnodes(char *entry)
98 {
99 return (NTFS_GETU16(entry + 0xc) & 1);
100 }
101
102 /* True if it is not the 'end of dir' entry. */
103 static inline int ntfs_entry_is_used(char *entry)
104 {
105 return !(NTFS_GETU16(entry + 0xc) & 2);
106 }
107
108 /*
109 * Removed RACE for allocating index blocks. But stil not too happy.
110 * There might be more races afterwards. (AIA)
111 */
112 static int ntfs_allocate_index_block(ntfs_iterate_s *walk)
113 {
114 ntfs_attribute *allocation, *bitmap = 0;
115 int error, size, i, bit;
116 ntfs_u8 *bmap;
117 ntfs_io io;
118 ntfs_volume *vol = walk->dir->vol;
119
120 /* Check for allocation attribute. */
121 allocation = ntfs_find_attr(walk->dir, vol->at_index_allocation, I30);
122 if (!allocation) {
123 ntfs_u8 bmp[8];
124 /* Create index allocation attribute. */
125 error = ntfs_create_attr(walk->dir, vol->at_index_allocation,
126 I30, 0, 0, &allocation);
127 if (error)
128 goto err_ret;
129 ntfs_bzero(bmp, sizeof(bmp));
130 error = ntfs_create_attr(walk->dir, vol->at_bitmap, I30, bmp,
131 sizeof(bmp), &bitmap);
132 if (error)
133 goto err_ret;
134 } else
135 bitmap = ntfs_find_attr(walk->dir, vol->at_bitmap, I30);
136 if (!bitmap) {
137 ntfs_error("Directory w/o bitmap\n");
138 error = -EINVAL;
139 goto err_ret;
140 }
141 size = bitmap->size;
142 bmap = ntfs_malloc(size);
143 if (!bmap) {
144 error = -ENOMEM;
145 goto err_ret;
146 }
147 io.fn_put = ntfs_put;
148 io.fn_get = ntfs_get;
149 try_again:
150 io.param = bmap;
151 io.size = size;
152 error = ntfs_read_attr(walk->dir, vol->at_bitmap, I30, 0, &io);
153 if (error || (io.size != size && (error = -EIO, 1)))
154 goto err_fb_out;
155 /* Allocate a bit. */
156 for (bit = i = 0; i < size; i++) {
157 if (bmap[i] == 0xFF)
158 continue;
159 bit = ffz(bmap[i]);
160 if (bit < 8)
161 break;
162 }
163 if (i >= size) {
164 /* FIXME: Extend bitmap. */
165 error = -EOPNOTSUPP;
166 goto err_fb_out;
167 }
168 /* Get the byte containing our bit again, now taking the BKL. */
169 io.param = bmap;
170 io.size = 1;
171 lock_kernel();
172 error = ntfs_read_attr(walk->dir, vol->at_bitmap, I30, i, &io);
173 if (error || (io.size != 1 && (error = -EIO, 1)))
174 goto err_unl_out;
175 if (ntfs_test_and_set_bit(bmap, bit)) {
176 unlock_kernel();
177 /* Give other process(es) a chance to finish. */
178 schedule();
179 goto try_again;
180 }
181 walk->newblock = (i * 8 + bit) * walk->dir->u.index.clusters_per_record;
182 io.param = bmap;
183 error = ntfs_write_attr(walk->dir, vol->at_bitmap, I30, i, &io);
184 if (error || (io.size != size && (error = -EIO, 1)))
185 goto err_unl_out;
186 /* Change inode on disk, required when bitmap is resident. */
187 error = ntfs_update_inode(walk->dir);
188 if (error)
189 goto err_unl_out;
190 unlock_kernel();
191 ntfs_free(bmap);
192 /* Check whether record is out of allocated range. */
193 size = allocation->size;
194 if (walk->newblock * vol->cluster_size >= size) {
195 /* Build index record. */
196 int hsize;
197 int s1 = walk->dir->u.index.recordsize;
198 int nr_fix = (s1 >> vol->sector_size) + 1;
199 char *record = ntfs_malloc(s1);
200 if (!record) {
201 error = -ENOMEM;
202 goto err_ret;
203 }
204 ntfs_bzero(record, s1);
205 /* Magic */
206 ntfs_memcpy(record, "INDX", 4);
207 /* Offset to fixups */
208 NTFS_PUTU16(record + 4, 0x28);
209 /* Number of fixups. */
210 NTFS_PUTU16(record + 6, nr_fix);
211 /* Log file sequence number - We don't do journalling so we
212 * just set it to zero which should be the Right Thing. (AIA) */
213 NTFS_PUTU64(record + 8, 0);
214 /* VCN of buffer */
215 NTFS_PUTU64(record + 0x10, walk->newblock);
216 /* Header size. */
217 hsize = 0x10 + 2 * nr_fix;
218 hsize = (hsize + 7) & ~7; /* Align. */
219 NTFS_PUTU16(record + 0x18, hsize);
220 /* Total size of record. */
221 NTFS_PUTU32(record + 0x20, s1 - 0x18);
222 /* Writing the data will extend the attribute. */
223 io.param = record;
224 io.size = s1;
225 io.do_read = 0;
226 error = ntfs_readwrite_attr(walk->dir, allocation, size, &io);
227 ntfs_free(record);
228 if (error || (io.size != s1 && (error = -EIO, 1)))
229 goto err_ret;
230 error = ntfs_update_inode(walk->dir);
231 if (error)
232 goto err_ret;
233 }
234 return 0;
235 err_unl_out:
236 unlock_kernel();
237 err_fb_out:
238 ntfs_free(bmap);
239 err_ret:
240 return error;
241 }
242
243 /* Write an index block (root or allocation) back to storage.
244 * Used is the total number of bytes in buf, including all headers. */
245 static int ntfs_index_writeback(ntfs_iterate_s *walk, ntfs_u8 *buf, int block,
246 int used)
247 {
248 ntfs_io io;
249 int error;
250 ntfs_attribute *a;
251 ntfs_volume *vol = walk->dir->vol;
252
253 io.fn_put = 0;
254 io.fn_get = ntfs_get;
255 io.param = buf;
256 if (block == -1) { /* Index root. */
257 NTFS_PUTU16(buf + 0x14, used - 0x10);
258 /* 0x18 is a copy thereof. */
259 NTFS_PUTU16(buf + 0x18, used - 0x10);
260 io.size = used;
261 error = ntfs_write_attr(walk->dir, vol->at_index_root, I30, 0,
262 &io);
263 if (error || (io.size != used && (error = -EIO, 1)))
264 return error;
265 /* Shrink if necessary. */
266 a = ntfs_find_attr(walk->dir, vol->at_index_root, I30);
267 ntfs_resize_attr(walk->dir, a, used);
268 } else {
269 NTFS_PUTU16(buf + 0x1C, used - 0x18);
270 io.size = walk->dir->u.index.recordsize;
271 error = ntfs_insert_fixups(buf, io.size);
272 if (error) {
273 printk(KERN_ALERT "NTFS: ntfs_index_writeback() caught "
274 "corrupt index record ntfs record "
275 "header. Refusing to write corrupt "
276 "data to disk. Unmount and run chkdsk "
277 "immediately!\n");
278 return -EIO;
279 }
280 error = ntfs_write_attr(walk->dir, vol->at_index_allocation,
281 I30, (__s64)block << vol->cluster_size_bits,
282 &io);
283 if (error || (io.size != walk->dir->u.index.recordsize &&
284 (error = -EIO, 1)))
285 return error;
286 }
287 return 0;
288 }
289
290 static int ntfs_split_record(ntfs_iterate_s *walk, char *start, int bsize,
291 int usize)
292 {
293 char *entry, *prev;
294 ntfs_u8 *newbuf = 0, *middle = 0;
295 int error, othersize, mlen;
296 ntfs_io io;
297 ntfs_volume *vol = walk->dir->vol;
298 int oldblock;
299
300 error = ntfs_allocate_index_block(walk);
301 if (error)
302 return error;
303 /* This should not happen. */
304 if (walk->block == -1) {
305 ntfs_error("Trying to split root");
306 return -EOPNOTSUPP;
307 }
308 entry = start + NTFS_GETU16(start + 0x18) + 0x18;
309 for (prev = entry; entry - start < usize / 2;
310 entry += NTFS_GETU16(entry + 8))
311 prev = entry;
312 newbuf = ntfs_malloc(vol->index_record_size);
313 if (!newbuf)
314 return -ENOMEM;
315 io.fn_put = ntfs_put;
316 io.fn_get = ntfs_get;
317 io.param = newbuf;
318 io.size = vol->index_record_size;
319 /* Read in old header. FIXME: Reading everything is overkill. */
320 error = ntfs_read_attr(walk->dir, vol->at_index_allocation, I30,
321 (__s64)walk->newblock << vol->cluster_size_bits, &io);
322 if (error)
323 goto out;
324 if (io.size != vol->index_record_size) {
325 error = -EIO;
326 goto out;
327 }
328 /* FIXME: Adjust header. */
329 /* Copy everything from entry to new block. */
330 othersize = usize - (entry - start);
331 ntfs_memcpy(newbuf + NTFS_GETU16(newbuf + 0x18) + 0x18, entry,
332 othersize);
333 /* Copy flags. */
334 NTFS_PUTU32(newbuf + 0x24, NTFS_GETU32(start + 0x24));
335 error = ntfs_index_writeback(walk, newbuf, walk->newblock,
336 othersize + NTFS_GETU16(newbuf + 0x18) + 0x18);
337 if (error)
338 goto out;
339 /* Move prev to walk. */
340 mlen = NTFS_GETU16(prev + 0x8);
341 /* Remember old child node. */
342 if (ntfs_entry_has_subnodes(prev))
343 oldblock = NTFS_GETU32(prev + mlen - 8);
344 else
345 oldblock = -1;
346 /* Allow for pointer to subnode. */
347 middle = ntfs_malloc(ntfs_entry_has_subnodes(prev) ? mlen : mlen + 8);
348 if (!middle){
349 error = -ENOMEM;
350 goto out;
351 }
352 ntfs_memcpy(middle, prev, mlen);
353 /* Set has_subnodes flag. */
354 NTFS_PUTU8(middle + 0xC, NTFS_GETU8(middle + 0xC) | 1);
355 /* Middle entry points to block, parent entry will point to newblock. */
356 NTFS_PUTU64(middle + mlen - 8, walk->block);
357 if (walk->new_entry)
358 ntfs_error("Entry not reset");
359 walk->new_entry = middle;
360 walk->u.flags |= ITERATE_SPLIT_DONE;
361 /* Terminate old block. */
362 othersize = usize - (prev-start);
363 NTFS_PUTU64(prev, 0);
364 if (oldblock == -1) {
365 NTFS_PUTU32(prev + 8, 0x10);
366 NTFS_PUTU32(prev + 0xC, 2);
367 othersize += 0x10;
368 } else {
369 NTFS_PUTU32(prev + 8, 0x18);
370 NTFS_PUTU32(prev + 0xC, 3);
371 NTFS_PUTU64(prev + 0x10, oldblock);
372 othersize += 0x18;
373 }
374 /* Write back original block. */
375 error = ntfs_index_writeback(walk, start, walk->block, othersize);
376 out:
377 if (newbuf)
378 ntfs_free(newbuf);
379 if (middle)
380 ntfs_free(middle);
381 return error;
382 }
383
384 static int ntfs_dir_insert(ntfs_iterate_s *walk, char *start, char* entry)
385 {
386 int blocksize, usedsize, error, offset;
387 int do_split = 0;
388 offset = entry - start;
389 if (walk->block == -1) { /* index root */
390 blocksize = walk->dir->vol->mft_record_size;
391 usedsize = NTFS_GETU16(start + 0x14) + 0x10;
392 } else {
393 blocksize = walk->dir->u.index.recordsize;
394 usedsize = NTFS_GETU16(start + 0x1C) + 0x18;
395 }
396 if (usedsize + walk->new_entry_size > blocksize) {
397 char* s1 = ntfs_malloc(blocksize + walk->new_entry_size);
398 if (!s1)
399 return -ENOMEM;
400 ntfs_memcpy(s1, start, usedsize);
401 do_split = 1;
402 /* Adjust entry to s1. */
403 entry = s1 + (entry - start);
404 start = s1;
405 }
406 ntfs_memmove(entry + walk->new_entry_size, entry, usedsize - offset);
407 ntfs_memcpy(entry, walk->new_entry, walk->new_entry_size);
408 usedsize += walk->new_entry_size;
409 ntfs_free(walk->new_entry);
410 walk->new_entry = 0;
411 if (do_split) {
412 error = ntfs_split_record(walk, start, blocksize, usedsize);
413 ntfs_free(start);
414 } else {
415 error = ntfs_index_writeback(walk, start, walk->block,usedsize);
416 if (error)
417 return error;
418 }
419 return 0;
420 }
421
422 /* Try to split INDEX_ROOT attributes. Return -E2BIG if nothing changed. */
423 int ntfs_split_indexroot(ntfs_inode *ino)
424 {
425 ntfs_attribute *ra;
426 ntfs_u8 *root = 0, *index = 0;
427 ntfs_io io;
428 int error, off, i, bsize, isize;
429 ntfs_iterate_s walk;
430
431 ra = ntfs_find_attr(ino, ino->vol->at_index_root, I30);
432 if (!ra)
433 return -ENOTDIR;
434 bsize = ino->vol->mft_record_size;
435 root = ntfs_malloc(bsize);
436 if (!root)
437 return -E2BIG;
438 io.fn_put = ntfs_put;
439 io.param = root;
440 io.size = bsize;
441 error = ntfs_read_attr(ino, ino->vol->at_index_root, I30, 0, &io);
442 if (error)
443 goto out;
444 off = 0x20;
445 /* Count number of entries. */
446 for (i = 0; ntfs_entry_is_used(root + off); i++)
447 off += NTFS_GETU16(root + off + 8);
448 if (i <= 2) {
449 /* We don't split small index roots. */
450 error = -E2BIG;
451 goto out;
452 }
453 index = ntfs_malloc(ino->vol->index_record_size);
454 if (!index) {
455 error = -ENOMEM;
456 goto out;
457 }
458 walk.dir = ino;
459 walk.block = -1;
460 walk.result = walk.new_entry = 0;
461 walk.name = 0;
462 error = ntfs_allocate_index_block(&walk);
463 if (error)
464 goto out;
465 /* Write old root to new index block. */
466 io.param = index;
467 io.size = ino->vol->index_record_size;
468 error = ntfs_read_attr(ino, ino->vol->at_index_allocation, I30,
469 (__s64)walk.newblock << ino->vol->cluster_size_bits, &io);
470 if (error)
471 goto out;
472 isize = NTFS_GETU16(root + 0x18) - 0x10;
473 ntfs_memcpy(index + NTFS_GETU16(index + 0x18) + 0x18, root+0x20, isize);
474 /* Copy flags. */
475 NTFS_PUTU32(index + 0x24, NTFS_GETU32(root + 0x1C));
476 error = ntfs_index_writeback(&walk, index, walk.newblock,
477 isize + NTFS_GETU16(index + 0x18) + 0x18);
478 if (error)
479 goto out;
480 /* Mark root as split. */
481 NTFS_PUTU32(root + 0x1C, 1);
482 /* Truncate index root. */
483 NTFS_PUTU64(root + 0x20, 0);
484 NTFS_PUTU32(root + 0x28, 0x18);
485 NTFS_PUTU32(root + 0x2C, 3);
486 NTFS_PUTU64(root + 0x30, walk.newblock);
487 error = ntfs_index_writeback(&walk, root, -1, 0x38);
488 out:
489 ntfs_free(root);
490 ntfs_free(index);
491 return error;
492 }
493
494 /* The entry has been found. Copy the result in the caller's buffer */
495 static int ntfs_copyresult(char *dest, char *source)
496 {
497 int length = NTFS_GETU16(source + 8);
498 ntfs_memcpy(dest, source, length);
499 return 1;
500 }
501
502 /* Use $UpCase some day. */
503 static inline unsigned short ntfs_my_toupper(ntfs_volume *vol, ntfs_u16 x)
504 {
505 /* We should read any pending rest of $UpCase here. */
506 if (x >= vol->upcase_length)
507 return x;
508 return vol->upcase[x];
509 }
510
511 /* Everything passed in walk and entry. */
512 static int ntfs_my_strcmp(ntfs_iterate_s *walk, const unsigned char *entry)
513 {
514 int lu = *(entry + 0x50);
515 int i;
516
517 ntfs_u16* name = (ntfs_u16*)(entry + 0x52);
518 ntfs_volume *vol = walk->dir->vol;
519 for (i = 0; i < lu && i < walk->namelen; i++)
520 if (ntfs_my_toupper(vol, NTFS_GETU16(name + i)) !=
521 ntfs_my_toupper(vol, NTFS_GETU16(walk->name + i)))
522 break;
523 if (i == lu && i == walk->namelen)
524 return 0;
525 if (i == lu)
526 return 1;
527 if (i == walk->namelen)
528 return -1;
529 if (ntfs_my_toupper(vol, NTFS_GETU16(name + i)) <
530 ntfs_my_toupper(vol, NTFS_GETU16(walk->name + i)))
531 return 1;
532 return -1;
533 }
534
535 /* Necessary forward declaration. */
536 static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry);
537
538 /* Parse a block of entries. Load the block, fix it up, and iterate over the
539 * entries. The block is given as virtual cluster number. */
540 static int ntfs_getdir_record(ntfs_iterate_s *walk, int block)
541 {
542 int length = walk->dir->u.index.recordsize;
543 char *record = (char*)ntfs_malloc(length);
544 char *offset;
545 int retval,error;
546 int oldblock;
547 ntfs_io io;
548
549 if (!record)
550 return -ENOMEM;
551 io.fn_put = ntfs_put;
552 io.param = record;
553 io.size = length;
554 /* Read the block from the index allocation attribute. */
555 error = ntfs_read_attr(walk->dir, walk->dir->vol->at_index_allocation,
556 I30, (__s64)block << walk->dir->vol->cluster_size_bits, &io);
557 if (error || io.size != length) {
558 ntfs_error("read failed\n");
559 ntfs_free(record);
560 return 0;
561 }
562 if (!ntfs_check_index_record(walk->dir, record)) {
563 ntfs_error("%x is not an index record\n", block);
564 ntfs_free(record);
565 return 0;
566 }
567 offset = record + NTFS_GETU16(record + 0x18) + 0x18;
568 oldblock = walk->block;
569 walk->block = block;
570 retval = ntfs_getdir_iterate(walk, record, offset);
571 walk->block = oldblock;
572 ntfs_free(record);
573 return retval;
574 }
575
576 /* Go down to the next block of entries. These collate before the current
577 * entry. */
578 static int ntfs_descend(ntfs_iterate_s *walk, ntfs_u8 *start, ntfs_u8 *entry)
579 {
580 int length = NTFS_GETU16(entry + 8);
581 int nextblock = NTFS_GETU32(entry + length - 8);
582 int error;
583
584 if (!ntfs_entry_has_subnodes(entry)) {
585 ntfs_error("illegal ntfs_descend call\n");
586 return 0;
587 }
588 error = ntfs_getdir_record(walk, nextblock);
589 if (!error && walk->type == DIR_INSERT &&
590 (walk->u.flags & ITERATE_SPLIT_DONE)) {
591 /* Split has occurred. Adjust entry, insert new_entry. */
592 NTFS_PUTU32(entry + length - 8, walk->newblock);
593 /* Reset flags, as the current block might be split again. */
594 walk->u.flags &= ~ITERATE_SPLIT_DONE;
595 error = ntfs_dir_insert(walk, start, entry);
596 }
597 return error;
598 }
599
600 static int ntfs_getdir_iterate_byposition(ntfs_iterate_s *walk, char* start,
601 char *entry)
602 {
603 int retval = 0;
604 int curpos = 0, destpos = 0;
605 int length;
606 if (walk->u.pos != 0) {
607 if (ntfs_is_top(walk->u.pos))
608 return 0;
609 destpos = ntfs_pop(&walk->u.pos);
610 }
611 while (1) {
612 if (walk->u.pos == 0) {
613 if (ntfs_entry_has_subnodes(entry))
614 ntfs_descend(walk, start, entry);
615 else
616 walk->u.pos = ntfs_top();
617 if (ntfs_is_top(walk->u.pos) &&
618 !ntfs_entry_is_used(entry))
619 return 1;
620 walk->u.pos = ntfs_push(walk->u.pos, curpos);
621 return 1;
622 }
623 if (curpos == destpos) {
624 if (!ntfs_is_top(walk->u.pos) &&
625 ntfs_entry_has_subnodes(entry)) {
626 retval = ntfs_descend(walk, start, entry);
627 if (retval) {
628 walk->u.pos = ntfs_push(walk->u.pos,
629 curpos);
630 return retval;
631 }
632 if (!ntfs_entry_is_used(entry))
633 return 0;
634 walk->u.pos = 0;
635 }
636 if (ntfs_entry_is_used(entry)) {
637 retval = ntfs_copyresult(walk->result, entry);
638 walk->u.pos = 0;
639 } else {
640 walk->u.pos = ntfs_top();
641 return 0;
642 }
643 }
644 curpos++;
645 if (!ntfs_entry_is_used(entry))
646 break;
647 length = NTFS_GETU16(entry + 8);
648 if (!length) {
649 ntfs_error("infinite loop\n");
650 break;
651 }
652 entry += length;
653 }
654 return -1;
655 }
656
657 /* Iterate over a list of entries, either from an index block, or from the
658 * index root.
659 * If searching BY_POSITION, pop the top index from the position. If the
660 * position stack is empty then, return the item at the index and set the
661 * position to the next entry. If the position stack is not empty,
662 * recursively proceed for subnodes. If the entry at the position is the
663 * 'end of dir' entry, return 'not found' and the empty stack.
664 * If searching BY_NAME, walk through the items until found or until
665 * one item is collated after the requested item. In the former case, return
666 * the result. In the latter case, recursively proceed to the subnodes.
667 * If 'end of dir' is reached, the name is not in the directory */
668 static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry)
669 {
670 int length;
671 int cmp;
672
673 if (walk->type == BY_POSITION)
674 return ntfs_getdir_iterate_byposition(walk, start, entry);
675 do {
676 /* If the current entry is a real one, compare with the
677 * requested item. If the current entry is the last item, it
678 * is always larger than the requested item. */
679 cmp = ntfs_entry_is_used(entry) ?
680 ntfs_my_strcmp(walk,entry) : -1;
681 switch (walk->type) {
682 case BY_NAME:
683 switch (cmp) {
684 case -1:
685 return ntfs_entry_has_subnodes(entry) ?
686 ntfs_descend(walk, start, entry) : 0;
687 case 0:
688 return ntfs_copyresult(walk->result, entry);
689 case 1:
690 break;
691 }
692 break;
693 case DIR_INSERT:
694 switch (cmp) {
695 case -1:
696 return ntfs_entry_has_subnodes(entry) ?
697 ntfs_descend(walk, start, entry) :
698 ntfs_dir_insert(walk, start, entry);
699 case 0:
700 return -EEXIST;
701 case 1:
702 break;
703 }
704 break;
705 default:
706 ntfs_error("TODO\n"); /* FIXME: ? */
707 }
708 if (!ntfs_entry_is_used(entry))
709 break;
710 length = NTFS_GETU16(entry + 8);
711 if (!length) {
712 ntfs_error("infinite loop\n");
713 break;
714 }
715 entry += length;
716 } while (1);
717 return 0;
718 }
719
720 /* Tree walking is done using position numbers. The following numbers have a
721 * special meaning:
722 * 0 start (.)
723 * -1 no more entries
724 * -2 ..
725 * All other numbers encode sequences of indices. The sequence a, b, c is
726 * encoded as <stop><c><b><a>, where <foo> is the encoding of foo. The
727 * first few integers are encoded as follows:
728 * 0: 0000 1: 0010 2: 0100 3: 0110
729 * 4: 1000 5: 1010 6: 1100 stop: 1110
730 * 7: 000001 8: 000101 9: 001001 10: 001101
731 * The least significant bits give the width of this encoding, the other bits
732 * encode the value, starting from the first value of the interval.
733 * tag width first value last value
734 * 0 3 0 6
735 * 01 4 7 22
736 * 011 5 23 54
737 * 0111 6 55 119
738 * More values are hopefully not needed, as the file position has currently
739 * 64 bits in total. */
740
741 /* Find an entry in the directory. Return 0 if not found, otherwise copy the
742 * entry to the result buffer. */
743 int ntfs_getdir(ntfs_iterate_s *walk)
744 {
745 int length = walk->dir->vol->mft_record_size;
746 int retval, error;
747 /* Start at the index root. */
748 char *root = ntfs_malloc(length);
749 ntfs_io io;
750
751 if (!root)
752 return -ENOMEM;
753 io.fn_put = ntfs_put;
754 io.param = root;
755 io.size = length;
756 error = ntfs_read_attr(walk->dir, walk->dir->vol->at_index_root, I30,
757 0, &io);
758 if (error) {
759 ntfs_error("Not a directory\n");
760 return 0;
761 }
762 walk->block = -1;
763 /* FIXME: Move these to walk. */
764 walk->dir->u.index.recordsize = NTFS_GETU32(root + 0x8);
765 walk->dir->u.index.clusters_per_record = NTFS_GETU32(root + 0xC);
766 /* FIXME: Consistency check. */
767 /* Skip header. */
768 retval = ntfs_getdir_iterate(walk, root, root + 0x20);
769 ntfs_free(root);
770 return retval;
771 }
772
773 /* Find an entry in the directory by its position stack. Iteration starts
774 * if the stack is 0, in which case the position is set to the first item
775 * in the directory. If the position is nonzero, return the item at the
776 * position and change the position to the next item. The position is -1
777 * if there are no more items. */
778 int ntfs_getdir_byposition(ntfs_iterate_s *walk)
779 {
780 walk->type = BY_POSITION;
781 return ntfs_getdir(walk);
782 }
783
784 /* Find an entry in the directory by its name. Return 0 if not found. */
785 int ntfs_getdir_byname(ntfs_iterate_s *walk)
786 {
787 walk->type = BY_NAME;
788 return ntfs_getdir(walk);
789 }
790
791 int ntfs_getdir_unsorted(ntfs_inode *ino, u32 *p_high, u32 *p_low,
792 int (*cb)(ntfs_u8 *, void *), void *param)
793 {
794 s64 ib_ofs;
795 char *buf = 0, *entry = 0;
796 ntfs_attribute *attr;
797 ntfs_volume *vol;
798 int byte, bit, err = 0;
799 u32 start, finish, ibs, max_size;
800 ntfs_io io;
801 u8 ibs_bits;
802
803 if (!ino) {
804 ntfs_error(__FUNCTION__ "(): No inode! Returning -EINVAL.\n");
805 return -EINVAL;
806 }
807 vol = ino->vol;
808 if (!vol) {
809 ntfs_error(__FUNCTION__ "(): Inode 0x%lx has no volume. "
810 "Returning -EINVAL.\n", ino->i_number);
811 return -EINVAL;
812 }
813 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 1: Entering for "
814 "inode 0x%lx, p_high = 0x%x, p_low = 0x%x.\n",
815 ino->i_number, *p_high, *p_low);
816 if (!*p_high) {
817 /* We are still in the index root. */
818 buf = ntfs_malloc(io.size = vol->mft_record_size);
819 if (!buf)
820 return -ENOMEM;
821 io.fn_put = ntfs_put;
822 io.param = buf;
823 err = ntfs_read_attr(ino, vol->at_index_root, I30, 0, &io);
824 if (err || !io.size)
825 goto read_err_ret;
826 ino->u.index.recordsize = ibs = NTFS_GETU32(buf + 0x8);
827 ino->u.index.clusters_per_record = NTFS_GETU32(buf + 0xC);
828 entry = buf + 0x20;
829 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 2: In index "
830 "root.\n");
831 ibs_bits = ffs(ibs) - 1;
832 /* Compensate for faked "." and "..". */
833 start = 2;
834 } else { /* We are in an index record. */
835 io.size = ibs = ino->u.index.recordsize;
836 buf = ntfs_malloc(ibs);
837 if (!buf)
838 return -ENOMEM;
839 ibs_bits = ffs(ibs) - 1;
840 io.fn_put = ntfs_put;
841 io.param = buf;
842 /*
843 * 0 is index root, index allocation starts at 1 and works in
844 * units of index block size (ibs).
845 */
846 ib_ofs = (s64)(*p_high - 1) << ibs_bits;
847 err = ntfs_read_attr(ino, vol->at_index_allocation, I30, ib_ofs,
848 &io);
849 if (err || io.size != ibs)
850 goto read_err_ret;
851 if (!ntfs_check_index_record(ino, buf)) {
852 ntfs_error(__FUNCTION__ "(): Index block 0x%x is not "
853 "an index record. Returning "
854 "-ENOTDIR.\n", *p_high - 1);
855 ntfs_free(buf);
856 return -ENOTDIR;
857 }
858 entry = buf + 0x18 + NTFS_GETU16(buf + 0x18);
859 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 3: In index "
860 "allocation.\n");
861 start = 0;
862 }
863 /* Process the entries. */
864 finish = *p_low;
865 for (; entry < (buf + ibs) && ntfs_entry_is_used(entry);
866 entry += NTFS_GETU16(entry + 8)) {
867 if (start < finish) {
868 /* Skip entries that were already processed. */
869 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 4: "
870 "Skipping already processed entry "
871 "p_high 0x%x, p_low 0x%x.\n", *p_high,
872 start);
873 start++;
874 continue;
875 }
876 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 5: "
877 "Processing entry p_high 0x%x, p_low 0x%x.\n",
878 *p_high, *p_low);
879 if ((err = cb(entry, param))) {
880 /* filldir signalled us to stop. */
881 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): "
882 "Unsorted 6: cb returned %i, "
883 "returning 0, p_high 0x%x, p_low 0x%x."
884 "\n", *p_high, *p_low);
885 ntfs_free(buf);
886 return 0;
887 }
888 ++*p_low;
889 }
890 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 7: After processing "
891 "entries, p_high 0x%x, p_low 0x%x.\n", *p_high, *p_low);
892 /* We have to locate the next record. */
893 ntfs_free(buf);
894 buf = 0;
895 *p_low = 0;
896 attr = ntfs_find_attr(ino, vol->at_bitmap, I30);
897 if (!attr) {
898 /* Directory does not have index bitmap and index allocation. */
899 *p_high = 0x7fff;
900 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 8: No index "
901 "allocation. Returning 0, p_high 0x7fff, "
902 "p_low 0x0.\n");
903 return 0;
904 }
905 max_size = attr->size;
906 if (max_size > 0x7fff >> 3) {
907 ntfs_error(__FUNCTION__ "(): Directory too large. Visible "
908 "length is truncated.\n");
909 max_size = 0x7fff >> 3;
910 }
911 buf = ntfs_malloc(max_size);
912 if (!buf)
913 return -ENOMEM;
914 io.param = buf;
915 io.size = max_size;
916 err = ntfs_read_attr(ino, vol->at_bitmap, I30, 0, &io);
917 if (err || io.size != max_size)
918 goto read_err_ret;
919 attr = ntfs_find_attr(ino, vol->at_index_allocation, I30);
920 if (!attr) {
921 ntfs_free(buf);
922 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 9: Find "
923 "attr failed. Returning -EIO.\n");
924 return -EIO;
925 }
926 if (attr->resident) {
927 ntfs_free(buf);
928 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 9.5: IA is "
929 "resident. Not allowed. Returning EINVAL.\n");
930 return -EINVAL;
931 }
932 /* Loop while going through non-allocated index records. */
933 max_size <<= 3;
934 while (1) {
935 if (++*p_high >= 0x7fff) {
936 ntfs_error(__FUNCTION__ "(): Unsorted 10: Directory "
937 "inode 0x%lx overflowed the maximum "
938 "number of index allocation buffers "
939 "the driver can cope with. Pretending "
940 "to be at end of directory.\n",
941 ino->i_number);
942 goto fake_eod;
943 }
944 if (*p_high > max_size || (s64)*p_high << ibs_bits >
945 attr->initialized) {
946 fake_eod:
947 /* No more index records. */
948 *p_high = 0x7fff;
949 *p_low = 0;
950 ntfs_free(buf);
951 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted "
952 "10.5: No more index records. "
953 "Returning 0, p_high 0x7fff, p_low "
954 "0.\n");
955 return 0;
956 }
957 byte = (ntfs_cluster_t)(*p_high - 1);
958 bit = 1 << (byte & 7);
959 byte >>= 3;
960 if ((buf[byte] & bit))
961 break;
962 };
963 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 11: Done. "
964 "Returning 0, p_high 0x%x, p_low 0x%x.\n", *p_high,
965 *p_low);
966 ntfs_free(buf);
967 return 0;
968 read_err_ret:
969 if (!err)
970 err = -EIO;
971 ntfs_error(__FUNCTION__ "(): Read failed. Returning error code %i.\n",
972 err);
973 ntfs_free(buf);
974 return err;
975 }
976
977 int ntfs_dir_add(ntfs_inode *dir, ntfs_inode *new, ntfs_attribute *name)
978 {
979 ntfs_iterate_s walk;
980 int nsize, esize;
981 ntfs_u8* entry, *ndata;
982 int error;
983
984 walk.type = DIR_INSERT;
985 walk.dir = dir;
986 walk.u.flags = 0;
987 nsize = name->size;
988 ndata = name->d.data;
989 walk.name = (ntfs_u16*)(ndata + 0x42);
990 walk.namelen = NTFS_GETU8(ndata + 0x40);
991 walk.new_entry_size = esize = (nsize + 0x10 + 7) & ~7;
992 walk.new_entry = entry = ntfs_malloc(esize);
993 if (!entry)
994 return -ENOMEM;
995 NTFS_PUTINUM(entry, new);
996 NTFS_PUTU16(entry + 0x8, esize); /* Size of entry. */
997 NTFS_PUTU16(entry + 0xA, nsize); /* Size of original name attribute. */
998 NTFS_PUTU16(entry + 0xC, 0); /* Flags. */
999 NTFS_PUTU16(entry + 0xE, 0); /* Reserved. */
1000 ntfs_memcpy(entry + 0x10, ndata, nsize);
1001 ntfs_bzero(entry + 0x10 + nsize, esize - 0x10 - nsize);
1002 error = ntfs_getdir(&walk);
1003 if (walk.new_entry)
1004 ntfs_free(walk.new_entry);
1005 return error;
1006 }
1007
1008 #if 0
1009 int ntfs_dir_add1(ntfs_inode *dir, const char* name, int namelen,
1010 ntfs_inode *ino)
1011 {
1012 ntfs_iterate_s walk;
1013 int error;
1014 int nsize;
1015 char *entry;
1016 ntfs_attribute *name_attr;
1017 error = ntfs_decodeuni(dir->vol, name, namelen, &walk.name,
1018 &walk.namelen);
1019 if (error)
1020 return error;
1021 /* FIXME: Set flags. */
1022 walk.type = DIR_INSERT;
1023 walk.dir = dir;
1024 /* walk.new = ino; */
1025 /* Prepare new entry. */
1026 /* Round up to a multiple of 8. */
1027 walk.new_entry_size = nsize = ((0x52 + 2 * walk.namelen + 7) / 8) * 8;
1028 walk.new_entry = entry = ntfs_malloc(nsize);
1029 if (!entry)
1030 return -ENOMEM;
1031 ntfs_bzero(entry, nsize);
1032 NTFS_PUTINUM(entry, ino);
1033 NTFS_PUTU16(entry + 8, nsize);
1034 NTFS_PUTU16(entry + 0xA, 0x42 + 2 * namelen); /* FIXME: Size of name
1035 * attribute. */
1036 NTFS_PUTU32(entry + 0xC, 0); /* FIXME: D-F? */
1037 name_attr = ntfs_find_attr(ino, vol->at_file_name, 0);
1038 /* FIXME: multiple names */
1039 if (!name_attr || !name_attr->resident)
1040 return -EIDRM;
1041 /* Directory, file stamps, sizes, filename. */
1042 ntfs_memcpy(entry + 0x10, name_attr->d.data, 0x42 + 2 * namelen);
1043 error = ntfs_getdir(&walk);
1044 ntfs_free(walk.name);
1045 return error;
1046 }
1047 #endif
1048
1049 /* Fills out and creates an INDEX_ROOT attribute. */
1050 int ntfs_add_index_root(ntfs_inode *ino, int type)
1051 {
1052 ntfs_attribute *da;
1053 ntfs_u8 data[0x30]; /* 0x20 header, 0x10 last entry. */
1054 char name[10];
1055
1056 NTFS_PUTU32(data, type);
1057 /* Collation rule. 1 == COLLATION_FILENAME */
1058 NTFS_PUTU32(data + 4, 1);
1059 NTFS_PUTU32(data + 8, ino->vol->index_record_size);
1060 NTFS_PUTU32(data + 0xC, ino->vol->index_clusters_per_record);
1061 /* Byte offset to first INDEX_ENTRY. */
1062 NTFS_PUTU32(data + 0x10, 0x10);
1063 /* Size of entries, including header. */
1064 NTFS_PUTU32(data + 0x14, 0x20);
1065 NTFS_PUTU32(data + 0x18, 0x20);
1066 /* No index allocation, yet. */
1067 NTFS_PUTU32(data + 0x1C, 0);
1068 /* Add last entry. */
1069 /* Indexed MFT record. */
1070 NTFS_PUTU64(data + 0x20, 0);
1071 /* Size of entry. */
1072 NTFS_PUTU32(data + 0x28, 0x10);
1073 /* Flags: Last entry, no child nodes. */
1074 NTFS_PUTU32(data + 0x2C, 2);
1075 /* Compute name. */
1076 ntfs_indexname(name, type);
1077 return ntfs_create_attr(ino, ino->vol->at_index_root, name,
1078 data, sizeof(data), &da);
1079 }
1080
1081 int ntfs_mkdir(ntfs_inode *dir, const char *name, int namelen,
1082 ntfs_inode *result)
1083 {
1084 int error;
1085
1086 error = ntfs_alloc_inode(dir, result, name, namelen, NTFS_AFLAG_DIR);
1087 if (error)
1088 goto out;
1089 error = ntfs_add_index_root(result, 0x30);
1090 if (error)
1091 goto out;
1092 /* Set directory bit. */
1093 result->attr[0x16] |= 2;
1094 error = ntfs_update_inode(dir);
1095 if (error)
1096 goto out;
1097 error = ntfs_update_inode(result);
1098 if (error)
1099 goto out;
1100 out:
1101 return error;
1102 }
1103
1104