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