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