fs_reiserfs.c

   1 /* ReiserFS filesystem
   2
   3    Copyright (C) 2001 Jeffrey Mahoney (jeffm@suse.com)
   4
   5    Adapted from GRUB
   6
   7    Copyright (C) 2000, 2001 Free Software Foundation, Inc.
   8
   9    This program is free software; you can redistribute it and/or modify
  10    it under the terms of the GNU General Public License as published by
  11    the Free Software Foundation; either version 2 of the License, or
  12    (at your option) any later version.
  13
  14    This program is distributed in the hope that it will be useful,
  15    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17    GNU General Public License for more details.
  18
  19    You should have received a copy of the GNU General Public License
  20    along with this program; if not, write to the Free Software
  21    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22
  23 */
  24 #include "types.h"
  25 #include "ctype.h"
  26 #include "string.h"
  27 #include "stdlib.h"
  28 #include "fs.h"
  29 #include "reiserfs/reiserfs.h"
  30
  31
  32 /* Exported in struct fs_t */
  33 static int reiserfs_open( struct boot_file_t *file, const char *dev_name,
  34     struct partition_t *part, const char *file_name );
  35 static int reiserfs_read( struct boot_file_t *file, unsigned int size,
  36
  37     void *buffer );
  38 static int reiserfs_seek( struct boot_file_t *file, unsigned int newpos );
  39 static int reiserfs_close( struct boot_file_t *file );
  40
  41 struct fs_t reiserfs_filesystem = {
  42     name:"reiserfs",
  43     open:reiserfs_open,
  44     read:reiserfs_read,
  45     seek:reiserfs_seek,
  46     close:reiserfs_close
  47 };
  48
  49 static int reiserfs_read_super( void );
  50 static int reiserfs_open_file( char *dirname );
  51 static int reiserfs_read_data( char *buf, __u32 len );
  52
  53
  54 static struct reiserfs_state reiserfs;
  55 static struct reiserfs_state *INFO = &reiserfs;
  56
  57 /* Adapted from GRUB: */
  58 static char FSYS_BUF[FSYSREISER_CACHE_SIZE];
  59 int errnum;
  60
  61
  62 static int
  63 reiserfs_open( struct boot_file_t *file, const char *dev_name,
  64                struct partition_t *part, const char *file_name )
  65 {
  66     static char buffer[1024];
  67
  68     DEBUG_ENTER;
  69     DEBUG_OPEN;
  70
  71     memset( INFO, 0, sizeof(struct reiserfs_state) );
  72     INFO->file = file;
  73
  74     if (part)
  75     {
  76         DEBUG_F( "Determining offset for partition %d\n", part->part_number );
  77         INFO->partition_offset = ((__u64)(part->part_start)) * ((__u64)part->blocksize);
  78         DEBUG_F( "%Lu = %lu * %hu\n", INFO->partition_offset,
  79                                      part->part_start,
  80                                      part->blocksize );
  81     }
  82     else
  83         INFO->partition_offset = 0;
  84
  85     sprintf( buffer, "%s:%d", dev_name, /*part ? part->part_number :*/ 0 );
  86     file->of_device = prom_open( buffer );
  87     DEBUG_F( "Trying to open dev_name=%s; filename=%s; partition offset=%Lu\n",
  88              buffer, file_name, INFO->partition_offset );
  89
  90     if ( file->of_device == PROM_INVALID_HANDLE || file->of_device == NULL )
  91     {
  92         DEBUG_F( "Can't open device %s\n", file->of_device );
  93         DEBUG_LEAVE(FILE_ERR_NOTFOUND);
  94         return FILE_ERR_NOTFOUND;
  95     }
  96
  97     DEBUG_F( "%s was successfully opened\n" );
  98
  99     if ( reiserfs_read_super() != 1 )
 100     {
 101         DEBUG_F( "Couldn't open ReiserFS @ %s/%Lu\n", buffer, INFO->partition_offset );
 102         prom_close( file->of_device );
 103         DEBUG_LEAVE(FILE_ERR_NOTFOUND);
 104         return FILE_ERR_NOTFOUND;
 105     }
 106
 107     DEBUG_F( "Attempting to open %s\n", file_name );
 108     strcpy(buffer, file_name); /* reiserfs_open_file modifies argument */
 109     if( reiserfs_open_file(buffer) == 0 )
 110     {
 111         DEBUG_F( "reiserfs_open_file failed. errnum = %d\n", errnum );
 112         prom_close( file->of_device );
 113         DEBUG_LEAVE(FILE_ERR_NOTFOUND);
 114         return FILE_ERR_NOTFOUND;
 115     }
 116
 117     DEBUG_F( "Successfully opened %s\n", file_name );
 118
 119     DEBUG_LEAVE(FILE_ERR_OK);
 120     return FILE_ERR_OK;
 121 }
 122
 123 static int
 124 reiserfs_read( struct boot_file_t *file, unsigned int size, void *buffer )
 125 {
 126     return reiserfs_read_data( buffer, size );
 127 }
 128
 129 static int
 130 reiserfs_seek( struct boot_file_t *file, unsigned int newpos )
 131 {
 132     file->pos = newpos;
 133     return FILE_ERR_OK;
 134 }
 135
 136 static int
 137 reiserfs_close( struct boot_file_t *file )
 138 {
 139     if( file->of_device )
 140     {
 141         prom_close(file->of_device);
 142         file->of_device = 0;
 143     }
 144     return FILE_ERR_OK;
 145 }
 146
 147
 148 static __inline__ __u32
 149 log2( __u32 word )
 150 {
 151     int i = 0;
 152     while( word && (word & (1 << ++i)) == 0 );
 153     return i;
 154 }
 155
 156 static __inline__ int
 157 is_power_of_two( unsigned long word )
 158 {
 159     return ( word & -word ) == word;
 160 }
 161
 162 static int
 163 read_disk_block( struct boot_file_t *file, __u32 block, __u32 start,
 164                  __u32 length, void *buf )
 165 {
 166     __u16 fs_blocksize = INFO->blocksize == 0 ? REISERFS_OLD_BLOCKSIZE
 167                                               : INFO->blocksize;
 168     unsigned long long pos = block * fs_blocksize;
 169     pos += INFO->partition_offset + start;
 170     DEBUG_F( "Reading %lu bytes, starting at block %lu, disk offset %Lu\n",
 171              length, block, pos );
 172     prom_lseek( file->of_device, pos );
 173     return prom_read( file->of_device, buf, length );
 174 }
 175
 176
 177 static int
 178 journal_read( __u32 block, __u32 len, char *buffer )
 179 {
 180     return read_disk_block( INFO->file,
 181                       (INFO->journal_block + block), 0,
 182                        len, buffer );
 183 }
 184
 185 /* Read a block from ReiserFS file system, taking the journal into
 186  * account.  If the block nr is in the journal, the block from the
 187  * journal taken.
 188  */
 189 static int
 190 block_read( __u32 blockNr, __u32 start, __u32 len, char *buffer )
 191 {
 192     __u32 transactions = INFO->journal_transactions;
 193     __u32 desc_block = INFO->journal_first_desc;
 194     __u32 journal_mask = INFO->journal_block_count - 1;
 195     __u32 translatedNr = blockNr;
 196     __u32 *journal_table = JOURNAL_START;
 197
 198 //    DEBUG_F( "block_read( %u, %u, %u, ..)\n", blockNr, start, len );
 199
 200     while ( transactions-- > 0 )
 201     {
 202         int i = 0;
 203         int j_len;
 204
 205         if ( *journal_table != 0xffffffff )
 206         {
 207             /* Search for the blockNr in cached journal */
 208             j_len = le32_to_cpu(*journal_table++);
 209             while ( i++ < j_len )
 210             {
 211                 if ( le32_to_cpu(*journal_table++) == blockNr )
 212                 {
 213                     journal_table += j_len - i;
 214                     goto found;
 215                 }
 216             }
 217         }
 218         else
 219         {
 220             /* This is the end of cached journal marker.  The remaining
 221              * transactions are still on disk. */
 222             struct reiserfs_journal_desc desc;
 223             struct reiserfs_journal_commit commit;
 224
 225             if ( !journal_read( desc_block, sizeof(desc), (char *) &desc ) )
 226                 return 0;
 227
 228             j_len = le32_to_cpu(desc.j_len);
 229             while ( i < j_len && i < JOURNAL_TRANS_HALF )
 230                 if ( le32_to_cpu(desc.j_realblock[i++]) == blockNr )
 231                     goto found;
 232
 233             if ( j_len >= JOURNAL_TRANS_HALF )
 234             {
 235                 int commit_block = ( desc_block + 1 + j_len ) & journal_mask;
 236
 237                 if ( !journal_read( commit_block,
 238                         sizeof(commit), (char *) &commit ) )
 239                     return 0;
 240
 241                 while ( i < j_len )
 242                     if ( le32_to_cpu(commit.j_realblock[i++ - JOURNAL_TRANS_HALF]) == blockNr )
 243                         goto found;
 244             }
 245         }
 246         goto not_found;
 247
 248       found:
 249         translatedNr =
 250             INFO->journal_block + ( ( desc_block + i ) & journal_mask );
 251
 252         DEBUG_F( "block_read: block %u is mapped to journal block %u.\n",
 253             blockNr, translatedNr - INFO->journal_block );
 254
 255         /* We must continue the search, as this block may be overwritten in
 256          * later transactions. */
 257       not_found:
 258         desc_block = (desc_block + 2 + j_len) & journal_mask;
 259     }
 260
 261     return read_disk_block( INFO->file, translatedNr, start, len, buffer );
 262 }
 263
 264 /* Init the journal data structure.  We try to cache as much as
 265  * possible in the JOURNAL_START-JOURNAL_END space, but if it is full
 266  * we can still read the rest from the disk on demand.
 267  *
 268  * The first number of valid transactions and the descriptor block of the
 269  * first valid transaction are held in INFO.  The transactions are all
 270  * adjacent, but we must take care of the journal wrap around.
 271  */
 272 static int
 273 journal_init( void )
 274 {
 275     struct reiserfs_journal_header header;
 276     struct reiserfs_journal_desc desc;
 277     struct reiserfs_journal_commit commit;
 278     __u32 block_count = INFO->journal_block_count;
 279     __u32 desc_block;
 280     __u32 commit_block;
 281     __u32 next_trans_id;
 282     __u32 *journal_table = JOURNAL_START;
 283
 284     journal_read( block_count, sizeof ( header ), ( char * ) &header );
 285     desc_block = le32_to_cpu(header.j_first_unflushed_offset);
 286     if ( desc_block >= block_count )
 287         return 0;
 288
 289     INFO->journal_transactions = 0;
 290     INFO->journal_first_desc = desc_block;
 291     next_trans_id = le32_to_cpu(header.j_last_flush_trans_id) + 1;
 292
 293     DEBUG_F( "journal_init: last flushed %u\n", le32_to_cpu(header.j_last_flush_trans_id) );
 294
 295     while ( 1 )
 296     {
 297         journal_read( desc_block, sizeof(desc), (char *) &desc );
 298         if ( strcmp( JOURNAL_DESC_MAGIC, desc.j_magic ) != 0
 299             || desc.j_trans_id != next_trans_id
 300             || desc.j_mount_id != header.j_mount_id )
 301             /* no more valid transactions */
 302             break;
 303
 304         commit_block = ( desc_block + le32_to_cpu(desc.j_len) + 1 ) & ( block_count - 1 );
 305         journal_read( commit_block, sizeof(commit), (char *) &commit );
 306         if ( desc.j_trans_id != commit.j_trans_id
 307             || desc.j_len != commit.j_len )
 308             /* no more valid transactions */
 309             break;
 310
 311
 312         DEBUG_F( "Found valid transaction %u/%u at %u.\n",
 313             le32_to_cpu(desc.j_trans_id), le32_to_cpu(desc.j_mount_id),
 314             desc_block );
 315
 316
 317         next_trans_id++;
 318         if ( journal_table < JOURNAL_END )
 319         {
 320             if ( ( journal_table + 1 + le32_to_cpu(desc.j_len) ) >= JOURNAL_END )
 321             {
 322                 /* The table is almost full; mark the end of the cached * *
 323                  * journal. */
 324                 *journal_table = 0xffffffff;
 325                 journal_table = JOURNAL_END;
 326             }
 327             else
 328             {
 329                 int i;
 330
 331                 /* Cache the length and the realblock numbers in the table. *
 332                  * The block number of descriptor can easily be computed. *
 333                  * and need not to be stored here. */
 334                 *journal_table++ = desc.j_len;
 335                 for ( i = 0; i < le32_to_cpu(desc.j_len) && i < JOURNAL_TRANS_HALF; i++ )
 336                 {
 337                     *journal_table++ = desc.j_realblock[i];
 338
 339                     DEBUG_F( "block %u is in journal %u.\n",
 340                         le32_to_cpu(desc.j_realblock[i]), desc_block );
 341
 342                 }
 343                 for ( ; i < le32_to_cpu(desc.j_len); i++ )
 344                 {
 345                     *journal_table++ =
 346                         commit.j_realblock[i - JOURNAL_TRANS_HALF];
 347
 348                     DEBUG_F( "block %u is in journal %u.\n",
 349                         le32_to_cpu(commit.j_realblock[i - JOURNAL_TRANS_HALF]),
 350                         desc_block );
 351
 352                 }
 353             }
 354         }
 355         desc_block = (commit_block + 1) & (block_count - 1);
 356     }
 357
 358     DEBUG_F( "Transaction %u/%u at %u isn't valid.\n",
 359         le32_to_cpu(desc.j_trans_id), le32_to_cpu(desc.j_mount_id),
 360         desc_block );
 361
 362
 363     INFO->journal_transactions
 364         = next_trans_id - le32_to_cpu(header.j_last_flush_trans_id) - 1;
 365     return errnum == 0;
 366 }
 367
 368 /* check filesystem types and read superblock into memory buffer */
 369 static int
 370 reiserfs_read_super( void )
 371 {
 372     struct reiserfs_super_block super;
 373     __u64 superblock = REISERFS_SUPERBLOCK_BLOCK;
 374
 375     read_disk_block( INFO->file, superblock, 0, sizeof(super), &super );
 376
 377     DEBUG_F( "Found super->magic %s\n", super.s_magic );
 378
 379     if( strcmp( REISER2FS_SUPER_MAGIC_STRING, super.s_magic ) != 0 &&
 380         strcmp( REISERFS_SUPER_MAGIC_STRING, super.s_magic ) != 0 )
 381     {
 382         /* Try old super block position */
 383         superblock = REISERFS_OLD_SUPERBLOCK_BLOCK;
 384         read_disk_block( INFO->file, superblock, 0, sizeof (super),  &super );
 385
 386         if ( strcmp( REISER2FS_SUPER_MAGIC_STRING, super.s_magic ) != 0 &&
 387              strcmp( REISERFS_SUPER_MAGIC_STRING, super.s_magic ) != 0 )
 388         {
 389             /* pre journaling super block - untested */
 390             if ( strcmp( REISERFS_SUPER_MAGIC_STRING,
 391                     (char *) ((__u32) &super + 20 ) ) != 0 )
 392                 return 0;
 393
 394             super.s_blocksize = cpu_to_le16(REISERFS_OLD_BLOCKSIZE);
 395             super.s_journal_block = 0;
 396             super.s_version = 0;
 397         }
 398     }
 399
 400     DEBUG_F( "ReiserFS superblock data:\n" );
 401     DEBUG_F( "Block count: %lu\n", le32_to_cpu(super.s_block_count) )
 402     DEBUG_F( "Free blocks: %lu\n", le32_to_cpu(super.s_free_blocks) );
 403     DEBUG_F( "Journal block: %lu\n", le32_to_cpu(super.s_journal_block) );
 404     DEBUG_F( "Journal size (in blocks): %lu\n",
 405                                     le32_to_cpu(super.s_orig_journal_size) );
 406     DEBUG_F( "Root block: %lu\n\n", le32_to_cpu(super.s_root_block) );
 407
 408
 409     INFO->version = le16_to_cpu(super.s_version);
 410     INFO->blocksize = le16_to_cpu(super.s_blocksize);
 411     INFO->blocksize_shift = log2( INFO->blocksize );
 412
 413     INFO->journal_block = le32_to_cpu(super.s_journal_block);
 414     INFO->journal_block_count = le32_to_cpu(super.s_orig_journal_size);
 415
 416     INFO->cached_slots = (FSYSREISER_CACHE_SIZE >> INFO->blocksize_shift) - 1;
 417
 418     /* At this point, we've found a valid superblock. If we run into problems
 419      * mounting the FS, the user should probably know. */
 420
 421     /* A few sanity checks ... */
 422     if ( INFO->version > REISERFS_MAX_SUPPORTED_VERSION )
 423     {
 424         prom_printf( "ReiserFS: Unsupported version field: %u\n",
 425                      INFO->version );
 426         return 0;
 427     }
 428
 429     if ( INFO->blocksize < FSYSREISER_MIN_BLOCKSIZE
 430         || INFO->blocksize > FSYSREISER_MAX_BLOCKSIZE )
 431     {
 432         prom_printf( "ReiserFS: Unsupported block size: %u\n",
 433                      INFO->blocksize );
 434         return 0;
 435     }
 436
 437     /* Setup the journal.. */
 438     if ( INFO->journal_block != 0 )
 439     {
 440         if ( !is_power_of_two( INFO->journal_block_count ) )
 441         {
 442             prom_printf( "ReiserFS: Unsupported journal size, "
 443                          "not a power of 2: %lu\n",
 444                          INFO->journal_block_count );
 445             return 0;
 446         }
 447
 448         journal_init();
 449         /* Read in super block again, maybe it is in the journal */
 450         block_read( superblock, 0, sizeof (struct reiserfs_super_block),
 451                     (char *) &super );
 452     }
 453
 454     /* Read in the root block */
 455     if ( !block_read( le32_to_cpu(super.s_root_block), 0,
 456             INFO->blocksize, ROOT ) )
 457     {
 458         prom_printf( "ReiserFS: Failed to read in root block\n" );
 459         return 0;
 460     }
 461
 462     /* The root node is always the "deepest", so we can
 463        determine the hieght of the tree using it. */
 464     INFO->tree_depth = blkh_level(BLOCKHEAD(ROOT));
 465
 466
 467     DEBUG_F( "root read_in: block=%u, depth=%u\n",
 468         le32_to_cpu(super.s_root_block), INFO->tree_depth );
 469
 470     if ( INFO->tree_depth >= REISERFS_MAX_TREE_HEIGHT )
 471     {
 472         prom_printf( "ReiserFS: Unsupported tree depth (too deep): %u\n",
 473                  INFO->tree_depth );
 474         return 0;
 475     }
 476
 477     if ( INFO->tree_depth == BLKH_LEVEL_LEAF )
 478     {
 479         /* There is only one node in the whole filesystem, which is
 480            simultanously leaf and root */
 481         memcpy( LEAF, ROOT, INFO->blocksize );
 482     }
 483     return 1;
 484 }
 485
 486 /***************** TREE ACCESSING METHODS *****************************/
 487
 488 /* I assume you are familiar with the ReiserFS tree, if not go to
 489  * http://devlinux.com/projects/reiserfs/
 490  *
 491  * My tree node cache is organized as following
 492  *   0   ROOT node
 493  *   1   LEAF node  (if the ROOT is also a LEAF it is copied here
 494  *   2-n other nodes on current path from bottom to top.
 495  *       if there is not enough space in the cache, the top most are
 496  *       omitted.
 497  *
 498  * I have only two methods to find a key in the tree:
 499  *   search_stat(dir_id, objectid) searches for the stat entry (always
 500  *       the first entry) of an object.
 501  *   next_key() gets the next key in tree order.
 502  *
 503  * This means, that I can only sequential reads of files are
 504  * efficient, but this really doesn't hurt for grub.
 505  */
 506
 507 /* Read in the node at the current path and depth into the node cache.
 508  * You must set INFO->blocks[depth] before.
 509  */
 510 static char *
 511 read_tree_node( __u32 blockNr, __u16 depth )
 512 {
 513     char *cache = CACHE(depth);
 514     int num_cached = INFO->cached_slots;
 515
 516     if ( depth < num_cached )
 517     {
 518         /* This is the cached part of the path.
 519            Check if same block is needed. */
 520         if ( blockNr == INFO->blocks[depth] )
 521             return cache;
 522     }
 523     else
 524         cache = CACHE(num_cached);
 525
 526     DEBUG_F( "  next read_in: block=%u (depth=%u)\n", blockNr, depth );
 527
 528     if ( !block_read( blockNr, 0, INFO->blocksize, cache ) )
 529     {
 530         DEBUG_F( "block_read failed\n" );
 531         return 0;
 532     }
 533
 534     DEBUG_F( "FOUND: blk_level=%u, blk_nr_item=%u, blk_free_space=%u\n",
 535             blkh_level(BLOCKHEAD(cache)),
 536             blkh_nr_item(BLOCKHEAD(cache)),
 537             le16_to_cpu(BLOCKHEAD(cache)->blk_free_space) );
 538
 539     /* Make sure it has the right node level */
 540     if ( blkh_level(BLOCKHEAD(cache)) != depth )
 541     {
 542         DEBUG_F( "depth = %u != %u\n", blkh_level(BLOCKHEAD(cache)), depth );
 543         DEBUG_LEAVE(FILE_ERR_BAD_FSYS);
 544         errnum = FILE_ERR_BAD_FSYS;
 545         return 0;
 546     }
 547
 548     INFO->blocks[depth] = blockNr;
 549     return cache;
 550 }
 551
 552 /* Get the next key, i.e. the key following the last retrieved key in
 553  * tree order.  INFO->current_ih and
 554  * INFO->current_info are adapted accordingly.  */
 555 static int
 556 next_key( void )
 557 {
 558     __u16 depth;
 559     struct item_head *ih = INFO->current_ih + 1;
 560     char *cache;
 561
 562
 563     DEBUG_F( "next_key:\n  old ih: key %u:%u:%u:%u version:%u\n",
 564         le32_to_cpu(INFO->current_ih->ih_key.k_dir_id),
 565         le32_to_cpu(INFO->current_ih->ih_key.k_objectid),
 566         le32_to_cpu(INFO->current_ih->ih_key.u.k_offset_v1.k_offset),
 567         le32_to_cpu(INFO->current_ih->ih_key.u.k_offset_v1.k_uniqueness),
 568         ih_version(INFO->current_ih) );
 569
 570
 571     if ( ih == &ITEMHEAD[blkh_nr_item(BLOCKHEAD( LEAF ))] )
 572     {
 573         depth = BLKH_LEVEL_LEAF;
 574         /* The last item, was the last in the leaf node. * Read in the next
 575          * * block */
 576         do
 577         {
 578             if ( depth == INFO->tree_depth )
 579             {
 580                 /* There are no more keys at all. * Return a dummy item with
 581                  * * MAX_KEY */
 582                 ih =
 583                     ( struct item_head * )
 584                     &BLOCKHEAD( LEAF )->blk_right_delim_key;
 585                 goto found;
 586             }
 587             depth++;
 588
 589             DEBUG_F( "  depth=%u, i=%u\n", depth, INFO->next_key_nr[depth] );
 590
 591         }
 592         while ( INFO->next_key_nr[depth] == 0 );
 593
 594         if ( depth == INFO->tree_depth )
 595             cache = ROOT;
 596         else if ( depth <= INFO->cached_slots )
 597             cache = CACHE( depth );
 598         else
 599         {
 600             cache = read_tree_node( INFO->blocks[depth], --depth );
 601             if ( !cache )
 602                 return 0;
 603         }
 604
 605         do
 606         {
 607             __u16 nr_item = blkh_nr_item(BLOCKHEAD( cache ));
 608             int key_nr = INFO->next_key_nr[depth]++;
 609
 610
 611             DEBUG_F( "  depth=%u, i=%u/%u\n", depth, key_nr, nr_item );
 612
 613             if ( key_nr == nr_item )
 614                 /* This is the last item in this block, set the next_key_nr *
 615                  * to 0 */
 616                 INFO->next_key_nr[depth] = 0;
 617
 618             cache =
 619                 read_tree_node( dc_block_number( &(DC( cache )[key_nr])),
 620                 --depth );
 621             if ( !cache )
 622                 return 0;
 623         }
 624         while ( depth > BLKH_LEVEL_LEAF );
 625
 626         ih = ITEMHEAD;
 627     }
 628   found:
 629     INFO->current_ih = ih;
 630     INFO->current_item = &LEAF[ih_location(ih)];
 631
 632     DEBUG_F( "  new ih: key %u:%u:%u:%u version:%u\n",
 633         le32_to_cpu(INFO->current_ih->ih_key.k_dir_id),
 634         le32_to_cpu(INFO->current_ih->ih_key.k_objectid),
 635         le32_to_cpu(INFO->current_ih->ih_key.u.k_offset_v1.k_offset),
 636         le32_to_cpu(INFO->current_ih->ih_key.u.k_offset_v1.k_uniqueness),
 637         ih_version(INFO->current_ih) );
 638
 639     return 1;
 640 }
 641
 642 /* preconditions: reiserfs_read_super already executed, therefore
 643  *   INFO block is valid
 644  * returns: 0 if error (errnum is set),
 645  *   nonzero iff we were able to find the key successfully.
 646  * postconditions: on a nonzero return, the current_ih and
 647  *   current_item fields describe the key that equals the
 648  *   searched key.  INFO->next_key contains the next key after
 649  *   the searched key.
 650  * side effects: messes around with the cache.
 651  */
 652 static int
 653 search_stat( __u32 dir_id, __u32 objectid )
 654 {
 655     char *cache;
 656     int depth;
 657     int nr_item;
 658     int i;
 659     struct item_head *ih;
 660
 661
 662     DEBUG_F( "search_stat:\n  key %u:%u:0:0\n", le32_to_cpu(dir_id),
 663             le32_to_cpu(objectid) );
 664
 665
 666     depth = INFO->tree_depth;
 667     cache = ROOT;
 668
 669     DEBUG_F( "depth = %d\n", depth );
 670     while ( depth > BLKH_LEVEL_LEAF )
 671     {
 672         struct key *key;
 673
 674         nr_item = blkh_nr_item(BLOCKHEAD( cache ));
 675
 676         key = KEY( cache );
 677
 678         for ( i = 0; i < nr_item; i++ )
 679         {
 680           if (le32_to_cpu(key->k_dir_id) > le32_to_cpu(dir_id)
 681               || (key->k_dir_id == dir_id
 682                   && (le32_to_cpu(key->k_objectid) > le32_to_cpu(objectid)
 683                       || (key->k_objectid == objectid
 684                           && (key->u.k_offset_v1.k_offset
 685                               | key->u.k_offset_v1.k_uniqueness) > 0))))
 686                 break;
 687             key++;
 688         }
 689
 690
 691         DEBUG_F( "  depth=%d, i=%d/%d\n", depth, i, nr_item );
 692
 693         INFO->next_key_nr[depth] = ( i == nr_item ) ? 0 : i + 1;
 694         cache = read_tree_node( dc_block_number(&(DC(cache)[i])), --depth );
 695         if ( !cache )
 696             return 0;
 697     }
 698
 699     /* cache == LEAF */
 700     nr_item = blkh_nr_item(BLOCKHEAD(LEAF));
 701     ih = ITEMHEAD;
 702     DEBUG_F( "nr_item = %d\n", nr_item );
 703     for ( i = 0; i < nr_item; i++ )
 704     {
 705         if ( ih->ih_key.k_dir_id == dir_id
 706             && ih->ih_key.k_objectid == objectid
 707             && ih->ih_key.u.k_offset_v1.k_offset == 0
 708             && ih->ih_key.u.k_offset_v1.k_uniqueness == 0 )
 709         {
 710
 711             DEBUG_F( "  depth=%d, i=%d/%d\n", depth, i, nr_item );
 712
 713             INFO->current_ih = ih;
 714             INFO->current_item = &LEAF[ih_location(ih)];
 715
 716             return 1;
 717         }
 718
 719         ih++;
 720     }
 721
 722     DEBUG_LEAVE(FILE_ERR_BAD_FSYS);
 723     errnum = FILE_ERR_BAD_FSYS;
 724     return 0;
 725 }
 726
 727 static int
 728 reiserfs_read_data( char *buf, __u32 len )
 729 {
 730     __u32 blocksize;
 731     __u32 offset;
 732     __u32 to_read;
 733     char *prev_buf = buf;
 734
 735
 736     DEBUG_F( "reiserfs_read_data: INFO->file->pos=%Lu len=%u, offset=%Lu\n",
 737         INFO->file->pos, len, (__u64) IH_KEY_OFFSET(INFO->current_ih) - 1 );
 738
 739
 740     if ( INFO->current_ih->ih_key.k_objectid != INFO->fileinfo.k_objectid
 741         || IH_KEY_OFFSET( INFO->current_ih ) > INFO->file->pos + 1 )
 742     {
 743         search_stat( INFO->fileinfo.k_dir_id, INFO->fileinfo.k_objectid );
 744         goto get_next_key;
 745     }
 746
 747     while ( errnum == 0 )
 748     {
 749         if ( INFO->current_ih->ih_key.k_objectid != INFO->fileinfo.k_objectid )
 750             break;
 751
 752         offset = INFO->file->pos - IH_KEY_OFFSET( INFO->current_ih ) + 1;
 753         blocksize = ih_item_len(INFO->current_ih);
 754
 755
 756         DEBUG_F( "  loop: INFO->file->pos=%Lu len=%u, offset=%u blocksize=%u\n",
 757             INFO->file->pos, len, offset, blocksize );
 758
 759
 760         if ( IH_KEY_ISTYPE( INFO->current_ih, TYPE_DIRECT )
 761             && offset < blocksize )
 762         {
 763             to_read = blocksize - offset;
 764             if ( to_read > len )
 765                 to_read = len;
 766
 767             memcpy( buf, INFO->current_item + offset, to_read );
 768             goto update_buf_len;
 769         }
 770         else if ( IH_KEY_ISTYPE( INFO->current_ih, TYPE_INDIRECT ) )
 771         {
 772             blocksize = ( blocksize >> 2 ) << INFO->blocksize_shift;
 773
 774             while ( offset < blocksize )
 775             {
 776                 __u32 blocknr = le32_to_cpu(((__u32 *)
 777                     INFO->current_item)[offset >> INFO->blocksize_shift]);
 778
 779                 int blk_offset = offset & (INFO->blocksize - 1);
 780
 781                 to_read = INFO->blocksize - blk_offset;
 782                 if ( to_read > len )
 783                     to_read = len;
 784
 785                 /* Journal is only for meta data.
 786                    Data blocks can be read directly without using block_read */
 787                 read_disk_block( INFO->file, blocknr, blk_offset, to_read,
 788                                  buf );
 789
 790               update_buf_len:
 791                 len -= to_read;
 792                 buf += to_read;
 793                 offset += to_read;
 794                 INFO->file->pos += to_read;
 795                 if ( len == 0 )
 796                     goto done;
 797             }
 798         }
 799       get_next_key:
 800         next_key();
 801     }
 802   done:
 803     return (errnum != 0) ? 0 : buf - prev_buf;
 804 }
 805
 806
 807 /* preconditions: reiserfs_read_super already executed, therefore
 808  *   INFO block is valid
 809  * returns: 0 if error, nonzero iff we were able to find the file successfully
 810  * postconditions: on a nonzero return, INFO->fileinfo contains the info
 811  *   of the file we were trying to look up, filepos is 0 and filemax is
 812  *   the size of the file.
 813  */
 814 static int
 815 reiserfs_open_file( char *dirname )
 816 {
 817     struct reiserfs_de_head *de_head;
 818     char *rest, ch;
 819     __u32 dir_id, objectid, parent_dir_id = 0, parent_objectid = 0;
 820
 821     char linkbuf[PATH_MAX];     /* buffer for following symbolic links */
 822     int link_count = 0;
 823     int mode;
 824
 825     dir_id = cpu_to_le32(REISERFS_ROOT_PARENT_OBJECTID);
 826     objectid = cpu_to_le32(REISERFS_ROOT_OBJECTID);
 827
 828     while ( 1 )
 829     {
 830
 831         DEBUG_F( "dirname=%s\n", dirname );
 832
 833         /* Search for the stat info first. */
 834         if ( !search_stat( dir_id, objectid ) )
 835             return 0;
 836
 837
 838         DEBUG_F( "sd_mode=0%o sd_size=%u\n",
 839             sd_mode((struct stat_data *) INFO->current_item ),
 840             sd_size(INFO->current_ih, INFO->current_item ));
 841
 842
 843         mode = sd_mode((struct stat_data *)INFO->current_item);
 844
 845         /* If we've got a symbolic link, then chase it. */
 846         if ( S_ISLNK( mode ) )
 847         {
 848             int len = 0;
 849
 850             if ( ++link_count > MAX_LINK_COUNT )
 851             {
 852                 errnum = FILE_ERR_SYMLINK_LOOP;
 853                 return 0;
 854             }
 855
 856             /* Get the symlink size. */
 857             INFO->file->len = sd_size(INFO->current_ih, INFO->current_item);
 858
 859             /* Find out how long our remaining name is. */
 860             while ( dirname[len] && !isspace( dirname[len] ) )
 861                 len++;
 862
 863             if ( INFO->file->len + len > sizeof ( linkbuf ) - 1 )
 864             {
 865                 errnum = FILE_ERR_LENGTH;
 866                 return 0;
 867             }
 868
 869             /* Copy the remaining name to the end of the symlink data. Note *
 870              * that DIRNAME and LINKBUF may overlap! */
 871             memmove( linkbuf + INFO->file->len, dirname, len + 1 );
 872
 873             INFO->fileinfo.k_dir_id = dir_id;
 874             INFO->fileinfo.k_objectid = objectid;
 875             INFO->file->pos = 0;
 876             if ( !next_key()
 877                 || reiserfs_read_data( linkbuf, INFO->file->len ) != INFO->file->len )
 878                 return 0;
 879
 880
 881             DEBUG_F( "symlink=%s\n", linkbuf );
 882
 883
 884             dirname = linkbuf;
 885             if ( *dirname == '/' )
 886             {
 887                 /* It's an absolute link, so look it up in root. */
 888                 dir_id = cpu_to_le32(REISERFS_ROOT_PARENT_OBJECTID);
 889                 objectid = cpu_to_le32(REISERFS_ROOT_OBJECTID);
 890             }
 891             else
 892             {
 893                 /* Relative, so look it up in our parent directory. */
 894                 dir_id = parent_dir_id;
 895                 objectid = parent_objectid;
 896             }
 897
 898             /* Now lookup the new name. */
 899             continue;
 900         }
 901
 902         /* if we have a real file (and we're not just printing *
 903          * possibilities), then this is where we want to exit */
 904
 905         if ( !*dirname || isspace( *dirname ) )
 906         {
 907             if ( !S_ISREG( mode ) )
 908             {
 909                 errnum = FILE_ERR_BAD_TYPE;
 910                 return 0;
 911             }
 912
 913             INFO->file->pos = 0;
 914             INFO->file->len = sd_size(INFO->current_ih, INFO->current_item);
 915
 916             INFO->fileinfo.k_dir_id = dir_id;
 917             INFO->fileinfo.k_objectid = objectid;
 918             return next_key();
 919         }
 920
 921         /* continue with the file/directory name interpretation */
 922         while ( *dirname == '/' )
 923             dirname++;
 924         if ( !S_ISDIR( mode ) )
 925         {
 926             errnum = FILE_ERR_BAD_TYPE;
 927             return 0;
 928         }
 929         for ( rest = dirname; ( ch = *rest ) && !isspace( ch ) && ch != '/';
 930             rest++ ) ;
 931         *rest = 0;
 932
 933         while ( 1 )
 934         {
 935             char *name_end;
 936             int num_entries;
 937
 938             if ( !next_key() )
 939                 return 0;
 940
 941             if ( INFO->current_ih->ih_key.k_objectid != objectid )
 942                 break;
 943
 944             name_end = INFO->current_item + ih_item_len(INFO->current_ih);
 945             de_head = ( struct reiserfs_de_head * ) INFO->current_item;
 946             num_entries = ih_entry_count(INFO->current_ih);
 947             while ( num_entries > 0 )
 948             {
 949                 char *filename = INFO->current_item + deh_location(de_head);
 950                 char tmp = *name_end;
 951
 952                 if( deh_state(de_head) & (1 << DEH_Visible))
 953                 {
 954                     int cmp;
 955
 956                     /* Directory names in ReiserFS are not null * terminated.
 957                      * We write a temporary 0 behind it. * NOTE: that this
 958                      * may overwrite the first block in * the tree cache.
 959                      * That doesn't hurt as long as we * don't call next_key
 960                      * () in between. */
 961                     *name_end = 0;
 962                     cmp = strcmp( dirname, filename );
 963                     *name_end = tmp;
 964                     if ( cmp == 0 )
 965                         goto found;
 966                 }
 967                 /* The beginning of this name marks the end of the next name.
 968                  */
 969                 name_end = filename;
 970                 de_head++;
 971                 num_entries--;
 972             }
 973         }
 974
 975         errnum = FILE_ERR_NOTFOUND;
 976         *rest = ch;
 977         return 0;
 978
 979       found:
 980         *rest = ch;
 981         dirname = rest;
 982
 983         parent_dir_id = dir_id;
 984         parent_objectid = objectid;
 985         dir_id = de_head->deh_dir_id; /* LE */
 986         objectid = de_head->deh_objectid; /* LE */
 987     }
 988 }
 989
 990
 991
 992 #ifndef __LITTLE_ENDIAN
 993 typedef union {
 994     struct offset_v2 offset_v2;
 995     __u64 linear;
 996 } offset_v2_esafe_overlay;
 997
 998 inline __u16
 999 offset_v2_k_type( struct offset_v2 *v2 )
1000 {
1001     offset_v2_esafe_overlay tmp = *(offset_v2_esafe_overlay *)v2;
1002     tmp.linear = le64_to_cpu( tmp.linear );
1003     return tmp.offset_v2.k_type;
1004 }
1005
1006 inline loff_t
1007 offset_v2_k_offset( struct offset_v2 *v2 )
1008 {
1009     offset_v2_esafe_overlay tmp = *(offset_v2_esafe_overlay *)v2;
1010     tmp.linear = le64_to_cpu( tmp.linear );
1011     return tmp.offset_v2.k_offset;
1012 }
1013 #endif
1014
1015 inline int
1016 uniqueness2type (__u32 uniqueness)
1017 {
1018     switch (uniqueness) {
1019     case V1_SD_UNIQUENESS: return TYPE_STAT_DATA;
1020     case V1_INDIRECT_UNIQUENESS: return TYPE_INDIRECT;
1021     case V1_DIRECT_UNIQUENESS: return TYPE_DIRECT;
1022     case V1_DIRENTRY_UNIQUENESS: return TYPE_DIRENTRY;
1023     }
1024     return TYPE_ANY;
1025 }