Commit yaboot 1.3.0
[yaboot.git] / second / 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 }