i386/linux/linux-2.3.21/fs/ntfs/dir.c

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