xref: /illumos-gate/usr/src/grub/grub-0.97/stage2/fsys_ext2fs.c (revision 1b8adde7ba7d5e04395c141c5400dc2cffd7d809)
1 /*
2  *  GRUB  --  GRand Unified Bootloader
3  *  Copyright (C) 1999, 2001, 2003  Free Software Foundation, Inc.
4  *
5  *  This program is free software; you can redistribute it and/or modify
6  *  it under the terms of the GNU General Public License as published by
7  *  the Free Software Foundation; either version 2 of the License, or
8  *  (at your option) any later version.
9  *
10  *  This program is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  *  GNU General Public License for more details.
14  *
15  *  You should have received a copy of the GNU General Public License
16  *  along with this program; if not, write to the Free Software
17  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18  */
19 
20 #ifdef FSYS_EXT2FS
21 
22 #include "shared.h"
23 #include "filesys.h"
24 
25 static int mapblock1, mapblock2;
26 
27 /* sizes are always in bytes, BLOCK values are always in DEV_BSIZE (sectors) */
28 #define DEV_BSIZE 512
29 
30 /* include/linux/fs.h */
31 #define BLOCK_SIZE 1024		/* initial block size for superblock read */
32 /* made up, defaults to 1 but can be passed via mount_opts */
33 #define WHICH_SUPER 1
34 /* kind of from fs/ext2/super.c */
35 #define SBLOCK (WHICH_SUPER * BLOCK_SIZE / DEV_BSIZE)	/* = 2 */
36 
37 /* include/asm-i386/types.h */
38 typedef __signed__ char __s8;
39 typedef unsigned char __u8;
40 typedef __signed__ short __s16;
41 typedef unsigned short __u16;
42 typedef __signed__ int __s32;
43 typedef unsigned int __u32;
44 
45 /*
46  * Constants relative to the data blocks, from ext2_fs.h
47  */
48 #define EXT2_NDIR_BLOCKS                12
49 #define EXT2_IND_BLOCK                  EXT2_NDIR_BLOCKS
50 #define EXT2_DIND_BLOCK                 (EXT2_IND_BLOCK + 1)
51 #define EXT2_TIND_BLOCK                 (EXT2_DIND_BLOCK + 1)
52 #define EXT2_N_BLOCKS                   (EXT2_TIND_BLOCK + 1)
53 
54 /* include/linux/ext2_fs.h */
55 struct ext2_super_block
56   {
57     __u32 s_inodes_count;	/* Inodes count */
58     __u32 s_blocks_count;	/* Blocks count */
59     __u32 s_r_blocks_count;	/* Reserved blocks count */
60     __u32 s_free_blocks_count;	/* Free blocks count */
61     __u32 s_free_inodes_count;	/* Free inodes count */
62     __u32 s_first_data_block;	/* First Data Block */
63     __u32 s_log_block_size;	/* Block size */
64     __s32 s_log_frag_size;	/* Fragment size */
65     __u32 s_blocks_per_group;	/* # Blocks per group */
66     __u32 s_frags_per_group;	/* # Fragments per group */
67     __u32 s_inodes_per_group;	/* # Inodes per group */
68     __u32 s_mtime;		/* Mount time */
69     __u32 s_wtime;		/* Write time */
70     __u16 s_mnt_count;		/* Mount count */
71     __s16 s_max_mnt_count;	/* Maximal mount count */
72     __u16 s_magic;		/* Magic signature */
73     __u16 s_state;		/* File system state */
74     __u16 s_errors;		/* Behaviour when detecting errors */
75     __u16 s_pad;
76     __u32 s_lastcheck;		/* time of last check */
77     __u32 s_checkinterval;	/* max. time between checks */
78     __u32 s_creator_os;		/* OS */
79     __u32 s_rev_level;		/* Revision level */
80     __u16 s_def_resuid;		/* Default uid for reserved blocks */
81     __u16 s_def_resgid;		/* Default gid for reserved blocks */
82    /*
83     * These fields are for EXT2_DYNAMIC_REV superblocks only.
84     *
85     * Note: the difference between the compatible feature set and
86     * the incompatible feature set is that if there is a bit set
87     * in the incompatible feature set that the kernel doesn't
88     * know about, it should refuse to mount the filesystem.
89     *
90     * e2fsck's requirements are more strict; if it doesn't know
91     * about a feature in either the compatible or incompatible
92     * feature set, it must abort and not try to meddle with
93     * things it doesn't understand...
94     */
95    __u32 s_first_ino;		/* First non-reserved inode */
96    __u16 s_inode_size;		/* size of inode structure */
97    __u16 s_block_group_nr;	/* block group # of this superblock */
98    __u32 s_feature_compat;	/* compatible feature set */
99    __u32 s_feature_incompat;	/* incompatible feature set */
100    __u32 s_feature_ro_compat;	/* readonly-compatible feature set */
101    __u8  s_uuid[16];		/* 128-bit uuid for volume */
102    char  s_volume_name[16];	/* volume name */
103    char  s_last_mounted[64];	/* directory where last mounted */
104    __u32 s_algorithm_usage_bitmap; /* For compression */
105    /*
106     * Performance hints.  Directory preallocation should only
107     * happen if the EXT2_FEATURE_COMPAT_DIR_PREALLOC flag is on.
108     */
109    __u8  s_prealloc_blocks;	/* Nr of blocks to try to preallocate*/
110    __u8  s_prealloc_dir_blocks;	/* Nr to preallocate for dirs */
111    __u16 s_reserved_gdt_blocks;/* Per group table for online growth */
112    /*
113     * Journaling support valid if EXT2_FEATURE_COMPAT_HAS_JOURNAL set.
114     */
115    __u8 s_journal_uuid[16];	/* uuid of journal superblock */
116    __u32 s_journal_inum;	/* inode number of journal file */
117    __u32 s_journal_dev;	/* device number of journal file */
118    __u32 s_last_orphan;	/* start of list of inodes to delete */
119    __u32 s_hash_seed[4];	/* HTREE hash seed */
120    __u8  s_def_hash_version;	/* Default hash version to use */
121    __u8  s_jnl_backup_type; 	/* Default type of journal backup */
122    __u16 s_reserved_word_pad;
123    __u32 s_default_mount_opts;
124    __u32 s_first_meta_bg;	/* First metablock group */
125    __u32 s_mkfs_time;		/* When the filesystem was created */
126    __u32 s_jnl_blocks[17]; 	/* Backup of the journal inode */
127    __u32 s_reserved[172];	/* Padding to the end of the block */
128   };
129 
130 struct ext2_group_desc
131   {
132     __u32 bg_block_bitmap;	/* Blocks bitmap block */
133     __u32 bg_inode_bitmap;	/* Inodes bitmap block */
134     __u32 bg_inode_table;	/* Inodes table block */
135     __u16 bg_free_blocks_count;	/* Free blocks count */
136     __u16 bg_free_inodes_count;	/* Free inodes count */
137     __u16 bg_used_dirs_count;	/* Directories count */
138     __u16 bg_pad;
139     __u32 bg_reserved[3];
140   };
141 
142 struct ext2_inode
143   {
144     __u16 i_mode;		/* File mode */
145     __u16 i_uid;		/* Owner Uid */
146     __u32 i_size;		/* 4: Size in bytes */
147     __u32 i_atime;		/* Access time */
148     __u32 i_ctime;		/* 12: Creation time */
149     __u32 i_mtime;		/* Modification time */
150     __u32 i_dtime;		/* 20: Deletion Time */
151     __u16 i_gid;		/* Group Id */
152     __u16 i_links_count;	/* 24: Links count */
153     __u32 i_blocks;		/* Blocks count */
154     __u32 i_flags;		/* 32: File flags */
155     union
156       {
157 	struct
158 	  {
159 	    __u32 l_i_reserved1;
160 	  }
161 	linux1;
162 	struct
163 	  {
164 	    __u32 h_i_translator;
165 	  }
166 	hurd1;
167 	struct
168 	  {
169 	    __u32 m_i_reserved1;
170 	  }
171 	masix1;
172       }
173     osd1;			/* OS dependent 1 */
174     __u32 i_block[EXT2_N_BLOCKS];	/* 40: Pointers to blocks */
175     __u32 i_version;		/* File version (for NFS) */
176     __u32 i_file_acl;		/* File ACL */
177     __u32 i_dir_acl;		/* Directory ACL */
178     __u32 i_faddr;		/* Fragment address */
179     union
180       {
181 	struct
182 	  {
183 	    __u8 l_i_frag;	/* Fragment number */
184 	    __u8 l_i_fsize;	/* Fragment size */
185 	    __u16 i_pad1;
186 	    __u32 l_i_reserved2[2];
187 	  }
188 	linux2;
189 	struct
190 	  {
191 	    __u8 h_i_frag;	/* Fragment number */
192 	    __u8 h_i_fsize;	/* Fragment size */
193 	    __u16 h_i_mode_high;
194 	    __u16 h_i_uid_high;
195 	    __u16 h_i_gid_high;
196 	    __u32 h_i_author;
197 	  }
198 	hurd2;
199 	struct
200 	  {
201 	    __u8 m_i_frag;	/* Fragment number */
202 	    __u8 m_i_fsize;	/* Fragment size */
203 	    __u16 m_pad1;
204 	    __u32 m_i_reserved2[2];
205 	  }
206 	masix2;
207       }
208     osd2;			/* OS dependent 2 */
209   };
210 
211 /* linux/limits.h */
212 #define NAME_MAX         255	/* # chars in a file name */
213 
214 /* linux/posix_type.h */
215 typedef long linux_off_t;
216 
217 /* linux/ext2fs.h */
218 #define EXT2_NAME_LEN 255
219 struct ext2_dir_entry
220   {
221     __u32 inode;		/* Inode number */
222     __u16 rec_len;		/* Directory entry length */
223     __u8 name_len;		/* Name length */
224     __u8 file_type;
225     char name[EXT2_NAME_LEN];	/* File name */
226   };
227 
228 /* linux/ext2fs.h */
229 /*
230  * EXT2_DIR_PAD defines the directory entries boundaries
231  *
232  * NOTE: It must be a multiple of 4
233  */
234 #define EXT2_DIR_PAD                    4
235 #define EXT2_DIR_ROUND                  (EXT2_DIR_PAD - 1)
236 #define EXT2_DIR_REC_LEN(name_len)      (((name_len) + 8 + EXT2_DIR_ROUND) & \
237                                          ~EXT2_DIR_ROUND)
238 
239 
240 /* ext2/super.c */
241 #define log2(n) ffz(~(n))
242 
243 #define EXT2_SUPER_MAGIC      0xEF53	/* include/linux/ext2_fs.h */
244 #define EXT2_ROOT_INO              2	/* include/linux/ext2_fs.h */
245 #define PATH_MAX                1024	/* include/linux/limits.h */
246 #define MAX_LINK_COUNT             5	/* number of symbolic links to follow */
247 
248 /* made up, these are pointers into FSYS_BUF */
249 /* read once, always stays there: */
250 #define SUPERBLOCK \
251     ((struct ext2_super_block *)(FSYS_BUF))
252 #define GROUP_DESC \
253     ((struct ext2_group_desc *) \
254      ((int)SUPERBLOCK + sizeof(struct ext2_super_block)))
255 #define INODE \
256     ((struct ext2_inode *)((int)GROUP_DESC + EXT2_BLOCK_SIZE(SUPERBLOCK)))
257 #define DATABLOCK1 \
258     ((int)((int)INODE + sizeof(struct ext2_inode)))
259 #define DATABLOCK2 \
260     ((int)((int)DATABLOCK1 + EXT2_BLOCK_SIZE(SUPERBLOCK)))
261 
262 /* linux/ext2_fs.h */
263 #define EXT2_ADDR_PER_BLOCK(s)          (EXT2_BLOCK_SIZE(s) / sizeof (__u32))
264 #define EXT2_ADDR_PER_BLOCK_BITS(s)		(log2(EXT2_ADDR_PER_BLOCK(s)))
265 
266 #define EXT2_INODE_SIZE(s)		(SUPERBLOCK->s_inode_size)
267 #define EXT2_INODES_PER_BLOCK(s)	(EXT2_BLOCK_SIZE(s)/EXT2_INODE_SIZE(s))
268 
269 /* linux/ext2_fs.h */
270 #define EXT2_BLOCK_SIZE_BITS(s)        ((s)->s_log_block_size + 10)
271 /* kind of from ext2/super.c */
272 #define EXT2_BLOCK_SIZE(s)	(1 << EXT2_BLOCK_SIZE_BITS(s))
273 /* linux/ext2fs.h */
274 #define EXT2_DESC_PER_BLOCK(s) \
275      (EXT2_BLOCK_SIZE(s) / sizeof (struct ext2_group_desc))
276 /* linux/stat.h */
277 #define S_IFMT  00170000
278 #define S_IFLNK  0120000
279 #define S_IFREG  0100000
280 #define S_IFDIR  0040000
281 #define S_ISLNK(m)	(((m) & S_IFMT) == S_IFLNK)
282 #define S_ISREG(m)      (((m) & S_IFMT) == S_IFREG)
283 #define S_ISDIR(m)      (((m) & S_IFMT) == S_IFDIR)
284 
285 /* include/asm-i386/bitops.h */
286 /*
287  * ffz = Find First Zero in word. Undefined if no zero exists,
288  * so code should check against ~0UL first..
289  */
290 static __inline__ unsigned long
ffz(unsigned long word)291 ffz (unsigned long word)
292 {
293   __asm__ ("bsfl %1,%0"
294 :	   "=r" (word)
295 :	   "r" (~word));
296   return word;
297 }
298 
299 /* check filesystem types and read superblock into memory buffer */
300 int
ext2fs_mount(void)301 ext2fs_mount (void)
302 {
303   int retval = 1;
304 
305   if ((((current_drive & 0x80) || (current_slice != 0))
306        && (current_slice != PC_SLICE_TYPE_EXT2FS)
307        && (current_slice != PC_SLICE_TYPE_LINUX_RAID)
308        && (! IS_PC_SLICE_TYPE_BSD_WITH_FS (current_slice, FS_EXT2FS))
309        && (! IS_PC_SLICE_TYPE_BSD_WITH_FS (current_slice, FS_OTHER)))
310       || part_length < (SBLOCK + (sizeof (struct ext2_super_block) / DEV_BSIZE))
311       || !devread (SBLOCK, 0, sizeof (struct ext2_super_block),
312 		   (char *) SUPERBLOCK)
313       || SUPERBLOCK->s_magic != EXT2_SUPER_MAGIC)
314       retval = 0;
315 
316   return retval;
317 }
318 
319 /* Takes a file system block number and reads it into BUFFER. */
320 static int
ext2_rdfsb(int fsblock,int buffer)321 ext2_rdfsb (int fsblock, int buffer)
322 {
323 #ifdef E2DEBUG
324   printf ("fsblock %d buffer %d\n", fsblock, buffer);
325 #endif /* E2DEBUG */
326   return devread (fsblock * (EXT2_BLOCK_SIZE (SUPERBLOCK) / DEV_BSIZE), 0,
327 		  EXT2_BLOCK_SIZE (SUPERBLOCK), (char *) buffer);
328 }
329 
330 /* from
331   ext2/inode.c:ext2_bmap()
332 */
333 /* Maps LOGICAL_BLOCK (the file offset divided by the blocksize) into
334    a physical block (the location in the file system) via an inode. */
335 static int
ext2fs_block_map(int logical_block)336 ext2fs_block_map (int logical_block)
337 {
338 
339 #ifdef E2DEBUG
340   unsigned char *i;
341   for (i = (unsigned char *) INODE;
342        i < ((unsigned char *) INODE + sizeof (struct ext2_inode));
343        i++)
344     {
345       printf ("%c", "0123456789abcdef"[*i >> 4]);
346       printf ("%c", "0123456789abcdef"[*i % 16]);
347       if (!((i + 1 - (unsigned char *) INODE) % 16))
348 	{
349 	  printf ("\n");
350 	}
351       else
352 	{
353 	  printf (" ");
354 	}
355     }
356   printf ("logical block %d\n", logical_block);
357 #endif /* E2DEBUG */
358 
359   /* if it is directly pointed to by the inode, return that physical addr */
360   if (logical_block < EXT2_NDIR_BLOCKS)
361     {
362 #ifdef E2DEBUG
363       printf ("returning %d\n", (unsigned char *) (INODE->i_block[logical_block]));
364       printf ("returning %d\n", INODE->i_block[logical_block]);
365 #endif /* E2DEBUG */
366       return INODE->i_block[logical_block];
367     }
368   /* else */
369   logical_block -= EXT2_NDIR_BLOCKS;
370   /* try the indirect block */
371   if (logical_block < EXT2_ADDR_PER_BLOCK (SUPERBLOCK))
372     {
373       if (mapblock1 != 1
374 	  && !ext2_rdfsb (INODE->i_block[EXT2_IND_BLOCK], DATABLOCK1))
375 	{
376 	  errnum = ERR_FSYS_CORRUPT;
377 	  return -1;
378 	}
379       mapblock1 = 1;
380       return ((__u32 *) DATABLOCK1)[logical_block];
381     }
382   /* else */
383   logical_block -= EXT2_ADDR_PER_BLOCK (SUPERBLOCK);
384   /* now try the double indirect block */
385   if (logical_block < (1 << (EXT2_ADDR_PER_BLOCK_BITS (SUPERBLOCK) * 2)))
386     {
387       int bnum;
388       if (mapblock1 != 2
389 	  && !ext2_rdfsb (INODE->i_block[EXT2_DIND_BLOCK], DATABLOCK1))
390 	{
391 	  errnum = ERR_FSYS_CORRUPT;
392 	  return -1;
393 	}
394       mapblock1 = 2;
395       if ((bnum = (((__u32 *) DATABLOCK1)
396 		   [logical_block >> EXT2_ADDR_PER_BLOCK_BITS (SUPERBLOCK)]))
397 	  != mapblock2
398 	  && !ext2_rdfsb (bnum, DATABLOCK2))
399 	{
400 	  errnum = ERR_FSYS_CORRUPT;
401 	  return -1;
402 	}
403       mapblock2 = bnum;
404       return ((__u32 *) DATABLOCK2)
405 	[logical_block & (EXT2_ADDR_PER_BLOCK (SUPERBLOCK) - 1)];
406     }
407   /* else */
408   mapblock2 = -1;
409   logical_block -= (1 << (EXT2_ADDR_PER_BLOCK_BITS (SUPERBLOCK) * 2));
410   if (mapblock1 != 3
411       && !ext2_rdfsb (INODE->i_block[EXT2_TIND_BLOCK], DATABLOCK1))
412     {
413       errnum = ERR_FSYS_CORRUPT;
414       return -1;
415     }
416   mapblock1 = 3;
417   if (!ext2_rdfsb (((__u32 *) DATABLOCK1)
418 		   [logical_block >> (EXT2_ADDR_PER_BLOCK_BITS (SUPERBLOCK)
419 				      * 2)],
420 		   DATABLOCK2))
421     {
422       errnum = ERR_FSYS_CORRUPT;
423       return -1;
424     }
425   if (!ext2_rdfsb (((__u32 *) DATABLOCK2)
426 		   [(logical_block >> EXT2_ADDR_PER_BLOCK_BITS (SUPERBLOCK))
427 		    & (EXT2_ADDR_PER_BLOCK (SUPERBLOCK) - 1)],
428 		   DATABLOCK2))
429     {
430       errnum = ERR_FSYS_CORRUPT;
431       return -1;
432     }
433   return ((__u32 *) DATABLOCK2)
434     [logical_block & (EXT2_ADDR_PER_BLOCK (SUPERBLOCK) - 1)];
435 }
436 
437 /* preconditions: all preconds of ext2fs_block_map */
438 int
ext2fs_read(char * buf,int len)439 ext2fs_read (char *buf, int len)
440 {
441   int logical_block;
442   int offset;
443   int map;
444   int ret = 0;
445   int size = 0;
446 
447 #ifdef E2DEBUG
448   static char hexdigit[] = "0123456789abcdef";
449   unsigned char *i;
450   for (i = (unsigned char *) INODE;
451        i < ((unsigned char *) INODE + sizeof (struct ext2_inode));
452        i++)
453     {
454       printf ("%c", hexdigit[*i >> 4]);
455       printf ("%c", hexdigit[*i % 16]);
456       if (!((i + 1 - (unsigned char *) INODE) % 16))
457 	{
458 	  printf ("\n");
459 	}
460       else
461 	{
462 	  printf (" ");
463 	}
464     }
465 #endif /* E2DEBUG */
466   while (len > 0)
467     {
468       /* find the (logical) block component of our location */
469       logical_block = filepos >> EXT2_BLOCK_SIZE_BITS (SUPERBLOCK);
470       offset = filepos & (EXT2_BLOCK_SIZE (SUPERBLOCK) - 1);
471       map = ext2fs_block_map (logical_block);
472 #ifdef E2DEBUG
473       printf ("map=%d\n", map);
474 #endif /* E2DEBUG */
475       if (map < 0)
476 	break;
477 
478       size = EXT2_BLOCK_SIZE (SUPERBLOCK);
479       size -= offset;
480       if (size > len)
481 	size = len;
482 
483       if (map == 0) {
484         memset ((char *) buf, 0, size);
485       } else {
486         disk_read_func = disk_read_hook;
487 
488         devread (map * (EXT2_BLOCK_SIZE (SUPERBLOCK) / DEV_BSIZE),
489 	         offset, size, buf);
490 
491         disk_read_func = NULL;
492       }
493 
494       buf += size;
495       len -= size;
496       filepos += size;
497       ret += size;
498     }
499 
500   if (errnum)
501     ret = 0;
502 
503   return ret;
504 }
505 
506 
507 /* Based on:
508    def_blk_fops points to
509    blkdev_open, which calls (I think):
510    sys_open()
511    do_open()
512    open_namei()
513    dir_namei() which accesses current->fs->root
514      fs->root was set during original mount:
515      (something)... which calls (I think):
516      ext2_read_super()
517      iget()
518      __iget()
519      read_inode()
520      ext2_read_inode()
521        uses desc_per_block_bits, which is set in ext2_read_super()
522        also uses group descriptors loaded during ext2_read_super()
523    lookup()
524    ext2_lookup()
525    ext2_find_entry()
526    ext2_getblk()
527 
528 */
529 
530 static inline
ext2_is_fast_symlink(void)531 int ext2_is_fast_symlink (void)
532 {
533   int ea_blocks;
534   ea_blocks = INODE->i_file_acl ? EXT2_BLOCK_SIZE (SUPERBLOCK) / DEV_BSIZE : 0;
535   return INODE->i_blocks == ea_blocks;
536 }
537 
538 /* preconditions: ext2fs_mount already executed, therefore supblk in buffer
539  *   known as SUPERBLOCK
540  * returns: 0 if error, nonzero iff we were able to find the file successfully
541  * postconditions: on a nonzero return, buffer known as INODE contains the
542  *   inode of the file we were trying to look up
543  * side effects: messes up GROUP_DESC buffer area
544  */
545 int
ext2fs_dir(char * dirname)546 ext2fs_dir (char *dirname)
547 {
548   int current_ino = EXT2_ROOT_INO;	/* start at the root */
549   int updir_ino = current_ino;	/* the parent of the current directory */
550   int group_id;			/* which group the inode is in */
551   int group_desc;		/* fs pointer to that group */
552   int desc;			/* index within that group */
553   int ino_blk;			/* fs pointer of the inode's information */
554   int str_chk = 0;		/* used to hold the results of a string compare */
555   struct ext2_group_desc *gdp;
556   struct ext2_inode *raw_inode;	/* inode info corresponding to current_ino */
557 
558   char linkbuf[PATH_MAX];	/* buffer for following symbolic links */
559   int link_count = 0;
560 
561   char *rest;
562   char ch;			/* temp char holder */
563 
564   int off;			/* offset within block of directory entry (off mod blocksize) */
565   int loc;			/* location within a directory */
566   int blk;			/* which data blk within dir entry (off div blocksize) */
567   long map;			/* fs pointer of a particular block from dir entry */
568   struct ext2_dir_entry *dp;	/* pointer to directory entry */
569 #ifdef E2DEBUG
570   unsigned char *i;
571 #endif	/* E2DEBUG */
572 
573   /* loop invariants:
574      current_ino = inode to lookup
575      dirname = pointer to filename component we are cur looking up within
576      the directory known pointed to by current_ino (if any)
577    */
578 
579   while (1)
580     {
581 #ifdef E2DEBUG
582       printf ("inode %d\n", current_ino);
583       printf ("dirname=%s\n", dirname);
584 #endif /* E2DEBUG */
585 
586       /* look up an inode */
587       group_id = (current_ino - 1) / (SUPERBLOCK->s_inodes_per_group);
588       group_desc = group_id >> log2 (EXT2_DESC_PER_BLOCK (SUPERBLOCK));
589       desc = group_id & (EXT2_DESC_PER_BLOCK (SUPERBLOCK) - 1);
590 #ifdef E2DEBUG
591       printf ("ipg=%d, dpb=%d\n", SUPERBLOCK->s_inodes_per_group,
592 	      EXT2_DESC_PER_BLOCK (SUPERBLOCK));
593       printf ("group_id=%d group_desc=%d desc=%d\n", group_id, group_desc, desc);
594 #endif /* E2DEBUG */
595       if (!ext2_rdfsb (
596 			(WHICH_SUPER + group_desc + SUPERBLOCK->s_first_data_block),
597 			(int) GROUP_DESC))
598 	{
599 	  return 0;
600 	}
601       gdp = GROUP_DESC;
602       ino_blk = gdp[desc].bg_inode_table +
603 	(((current_ino - 1) % (SUPERBLOCK->s_inodes_per_group))
604 	 >> log2 (EXT2_INODES_PER_BLOCK (SUPERBLOCK)));
605 #ifdef E2DEBUG
606       printf ("inode table fsblock=%d\n", ino_blk);
607 #endif /* E2DEBUG */
608       if (!ext2_rdfsb (ino_blk, (int) INODE))
609 	{
610 	  return 0;
611 	}
612 
613       /* reset indirect blocks! */
614       mapblock2 = mapblock1 = -1;
615 
616       raw_inode = (struct ext2_inode *)((char *)INODE +
617 	((current_ino - 1) & (EXT2_INODES_PER_BLOCK (SUPERBLOCK) - 1)) *
618 	EXT2_INODE_SIZE (SUPERBLOCK));
619 
620 #ifdef E2DEBUG
621       printf ("ipb=%d, sizeof(inode)=%d\n",
622 	      EXT2_INODES_PER_BLOCK (SUPERBLOCK), EXT2_INODE_SIZE (SUPERBLOCK));
623       printf ("inode=%x, raw_inode=%x\n", INODE, raw_inode);
624       printf ("offset into inode table block=%d\n", (int) raw_inode - (int) INODE);
625       for (i = (unsigned char *) INODE; i <= (unsigned char *) raw_inode;
626 	   i++)
627 	{
628 	  printf ("%c", "0123456789abcdef"[*i >> 4]);
629 	  printf ("%c", "0123456789abcdef"[*i % 16]);
630 	  if (!((i + 1 - (unsigned char *) INODE) % 16))
631 	    {
632 	      printf ("\n");
633 	    }
634 	  else
635 	    {
636 	      printf (" ");
637 	    }
638 	}
639       printf ("first word=%x\n", *((int *) raw_inode));
640 #endif /* E2DEBUG */
641 
642       /* copy inode to fixed location */
643       memmove ((void *) INODE, (void *) raw_inode, sizeof (struct ext2_inode));
644 
645 #ifdef E2DEBUG
646       printf ("first word=%x\n", *((int *) INODE));
647 #endif /* E2DEBUG */
648 
649       /* If we've got a symbolic link, then chase it. */
650       if (S_ISLNK (INODE->i_mode))
651 	{
652 	  int len;
653 	  if (++link_count > MAX_LINK_COUNT)
654 	    {
655 	      errnum = ERR_SYMLINK_LOOP;
656 	      return 0;
657 	    }
658 
659 	  /* Find out how long our remaining name is. */
660 	  len = 0;
661 	  while (dirname[len] && !isspace (dirname[len]))
662 	    len++;
663 
664 	  /* Get the symlink size. */
665 	  filemax = (INODE->i_size);
666 	  if (filemax + len > sizeof (linkbuf) - 2)
667 	    {
668 	      errnum = ERR_FILELENGTH;
669 	      return 0;
670 	    }
671 
672 	  if (len)
673 	    {
674 	      /* Copy the remaining name to the end of the symlink data.
675 	         Note that DIRNAME and LINKBUF may overlap! */
676 	      memmove (linkbuf + filemax, dirname, len);
677 	    }
678 	  linkbuf[filemax + len] = '\0';
679 
680 	  /* Read the symlink data. */
681 	  if (! ext2_is_fast_symlink ())
682 	    {
683 	      /* Read the necessary blocks, and reset the file pointer. */
684 	      len = grub_read (linkbuf, filemax);
685 	      filepos = 0;
686 	      if (!len)
687 		return 0;
688 	    }
689 	  else
690 	    {
691 	      /* Copy the data directly from the inode. */
692 	      len = filemax;
693 	      memmove (linkbuf, (char *) INODE->i_block, len);
694 	    }
695 
696 #ifdef E2DEBUG
697 	  printf ("symlink=%s\n", linkbuf);
698 #endif
699 
700 	  dirname = linkbuf;
701 	  if (*dirname == '/')
702 	    {
703 	      /* It's an absolute link, so look it up in root. */
704 	      current_ino = EXT2_ROOT_INO;
705 	      updir_ino = current_ino;
706 	    }
707 	  else
708 	    {
709 	      /* Relative, so look it up in our parent directory. */
710 	      current_ino = updir_ino;
711 	    }
712 
713 	  /* Try again using the new name. */
714 	  continue;
715 	}
716 
717       /* if end of filename, INODE points to the file's inode */
718       if (!*dirname || isspace (*dirname))
719 	{
720 	  if (!S_ISREG (INODE->i_mode))
721 	    {
722 	      errnum = ERR_BAD_FILETYPE;
723 	      return 0;
724 	    }
725 
726 	  filemax = (INODE->i_size);
727 	  return 1;
728 	}
729 
730       /* else we have to traverse a directory */
731       updir_ino = current_ino;
732 
733       /* skip over slashes */
734       while (*dirname == '/')
735 	dirname++;
736 
737       /* if this isn't a directory of sufficient size to hold our file, abort */
738       if (!(INODE->i_size) || !S_ISDIR (INODE->i_mode))
739 	{
740 	  errnum = ERR_BAD_FILETYPE;
741 	  return 0;
742 	}
743 
744       /* skip to next slash or end of filename (space) */
745       for (rest = dirname; (ch = *rest) && !isspace (ch) && ch != '/';
746 	   rest++);
747 
748       /* look through this directory and find the next filename component */
749       /* invariant: rest points to slash after the next filename component */
750       *rest = 0;
751       loc = 0;
752 
753       do
754 	{
755 
756 #ifdef E2DEBUG
757 	  printf ("dirname=%s, rest=%s, loc=%d\n", dirname, rest, loc);
758 #endif /* E2DEBUG */
759 
760 	  /* if our location/byte offset into the directory exceeds the size,
761 	     give up */
762 	  if (loc >= INODE->i_size)
763 	    {
764 	      if (print_possibilities < 0)
765 		{
766 # if 0
767 		  putchar ('\n');
768 # endif
769 		}
770 	      else
771 		{
772 		  errnum = ERR_FILE_NOT_FOUND;
773 		  *rest = ch;
774 		}
775 	      return (print_possibilities < 0);
776 	    }
777 
778 	  /* else, find the (logical) block component of our location */
779 	  blk = loc >> EXT2_BLOCK_SIZE_BITS (SUPERBLOCK);
780 
781 	  /* we know which logical block of the directory entry we are looking
782 	     for, now we have to translate that to the physical (fs) block on
783 	     the disk */
784 	  map = ext2fs_block_map (blk);
785 #ifdef E2DEBUG
786 	  printf ("fs block=%d\n", map);
787 #endif /* E2DEBUG */
788 	  mapblock2 = -1;
789 	  if ((map < 0) || !ext2_rdfsb (map, DATABLOCK2))
790 	    {
791 	      errnum = ERR_FSYS_CORRUPT;
792 	      *rest = ch;
793 	      return 0;
794 	    }
795 	  off = loc & (EXT2_BLOCK_SIZE (SUPERBLOCK) - 1);
796 	  dp = (struct ext2_dir_entry *) (DATABLOCK2 + off);
797 	  /* advance loc prematurely to next on-disk directory entry  */
798 	  loc += dp->rec_len;
799 
800 	  /* NOTE: ext2fs filenames are NOT null-terminated */
801 
802 #ifdef E2DEBUG
803 	  printf ("directory entry ino=%d\n", dp->inode);
804 	  if (dp->inode)
805 	    printf ("entry=%s\n", dp->name);
806 #endif /* E2DEBUG */
807 
808 	  if (dp->inode)
809 	    {
810 	      int saved_c = dp->name[dp->name_len];
811 
812 	      dp->name[dp->name_len] = 0;
813 	      str_chk = substring (dirname, dp->name);
814 
815 # ifndef STAGE1_5
816 	      if (print_possibilities && ch != '/'
817 		  && (!*dirname || str_chk <= 0))
818 		{
819 		  if (print_possibilities > 0)
820 		    print_possibilities = -print_possibilities;
821 		  print_a_completion (dp->name);
822 		}
823 # endif
824 
825 	      dp->name[dp->name_len] = saved_c;
826 	    }
827 
828 	}
829       while (!dp->inode || (str_chk || (print_possibilities && ch != '/')));
830 
831       current_ino = dp->inode;
832       *(dirname = rest) = ch;
833     }
834   /* never get here */
835 }
836 
837 #endif /* FSYS_EXT2_FS */
838