开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Linux/Unix编程 > 查看源码
dir.c
资源名称：linux-2.4.20.tar.gz　[点击查看]
上传用户：jlfgdled
上传日期：2013-04-10
资源大小：33168k
文件大小：30k
源码类别：

Linux/Unix编程

开发平台：

Unix_Linux

dir.c：源码内容
  1. /*
  2.  * dir.c
  3.  *
  4.  * Copyright (C) 1995-1997, 1999 Martin von L鰓is
  5.  * Copyright (C) 1999 Steve Dodd
  6.  * Copyright (C) 1999 Joseph Malicki
  7.  * Copyright (C) 2001 Anton Altaparmakov (AIA)
  8.  */
  10. #include "ntfstypes.h"
  11. #include "struct.h"
  12. #include "dir.h"
  13. #include "macros.h"
  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>
  24. static char I30[] = "$I30";
  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. }
  34. static inline int ntfs_is_top(ntfs_u64 stack)
  35. {
  36. return stack == 14;
  37. }
  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;
  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 encodingn");
  63. }
  64. return res;
  65. }
  67. static inline unsigned int ntfs_top(void)
  68. {
  69. return 14;
  70. }
  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 entriesn");
  83. return ~((ntfs_u64)0);
  84. }
  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
  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. }
  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. }
  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;
  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 bitmapn");
  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. }
  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;
  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. }
  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;
  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. }
  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. }
  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;
  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. }
  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. }
  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. }
  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;
  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. }
  536. /* Necessary forward declaration. */
  537. static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry);
  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;
  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 failedn");
  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 recordn", 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. }
  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;
  585. if (!ntfs_entry_has_subnodes(entry)) {
  586. ntfs_error("illegal ntfs_descend calln");
  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. }
  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 loopn");
  651. break;
  652. }
  653. entry += length;
  654. }
  655. return -1;
  656. }
  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;
  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("TODOn"); /* FIXME: ? */
  708. }
  709. if (!ntfs_entry_is_used(entry))
  710. break;
  711. length = NTFS_GETU16(entry + 8);
  712. if (!length) {
  713. ntfs_error("infinite loopn");
  714. break;
  715. }
  716. entry += length;
  717. } while (1);
  718. return 0;
  719. }
  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. */
  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;
  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 directoryn");
  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. }
  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. }
  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. }
  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;
  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. }
  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;
  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. }
  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
  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];
  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. }
  1082. int ntfs_mkdir(ntfs_inode *dir, const char *name, int namelen,
  1083.        ntfs_inode *result)
  1084. {
  1085. int error;
  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. }