cc612a11ab1276b16e80f6a735ef647a34b24ee7
[dragonfly.git] / lib / libstand / ext2fs.c
1 /*-
2  * Copyright (c) 1999,2000 Jonathan Lemon <jlemon@freebsd.org>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  *
26  *      $FreeBSD: src/lib/libstand/ext2fs.c,v 1.1.2.2 2001/03/05 06:26:07 kris Exp $
27  *      $DragonFly: src/lib/libstand/ext2fs.c,v 1.2 2003/06/17 04:26:51 dillon Exp $
28  */
29 /*-
30  * Copyright (c) 1993
31  *      The Regents of the University of California.  All rights reserved.
32  *
33  * This code is derived from software contributed to Berkeley by
34  * The Mach Operating System project at Carnegie-Mellon University.
35  *
36  * Redistribution and use in source and binary forms, with or without
37  * modification, are permitted provided that the following conditions
38  * are met:
39  * 1. Redistributions of source code must retain the above copyright
40  *    notice, this list of conditions and the following disclaimer.
41  * 2. Redistributions in binary form must reproduce the above copyright
42  *    notice, this list of conditions and the following disclaimer in the
43  *    documentation and/or other materials provided with the distribution.
44  * 3. All advertising materials mentioning features or use of this software
45  *    must display the following acknowledgement:
46  *      This product includes software developed by the University of
47  *      California, Berkeley and its contributors.
48  * 4. Neither the name of the University nor the names of its contributors
49  *    may be used to endorse or promote products derived from this software
50  *    without specific prior written permission.
51  *
52  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
53  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
54  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
55  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
56  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
57  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
58  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
59  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
60  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
61  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
62  * SUCH DAMAGE.
63  *  
64  *
65  * Copyright (c) 1990, 1991 Carnegie Mellon University
66  * All Rights Reserved.
67  *
68  * Author: David Golub
69  * 
70  * Permission to use, copy, modify and distribute this software and its
71  * documentation is hereby granted, provided that both the copyright
72  * notice and this permission notice appear in all copies of the
73  * software, derivative works or modified versions, and any portions
74  * thereof, and that both notices appear in supporting documentation.
75  * 
76  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
77  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
78  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
79  * 
80  * Carnegie Mellon requests users of this software to return to
81  * 
82  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
83  *  School of Computer Science
84  *  Carnegie Mellon University
85  *  Pittsburgh PA 15213-3890
86  * 
87  * any improvements or extensions that they make and grant Carnegie the
88  * rights to redistribute these changes.
89  */
90
91 #include <sys/param.h>
92 #include <sys/time.h>
93 #include "stand.h"
94 #include "string.h"
95
96 static int      ext2fs_open(const char *path, struct open_file *f);
97 static int      ext2fs_close(struct open_file *f);
98 static int      ext2fs_read(struct open_file *f, void *buf,
99                          size_t size, size_t *resid);
100 static off_t    ext2fs_seek(struct open_file *f, off_t offset, int where);
101 static int      ext2fs_stat(struct open_file *f, struct stat *sb);
102 static int      ext2fs_readdir(struct open_file *f, struct dirent *d);
103
104 static int dtmap[] = { DT_UNKNOWN, DT_REG, DT_DIR, DT_CHR,
105                          DT_BLK, DT_FIFO, DT_SOCK, DT_LNK };
106 #define EXTFTODT(x)     (x) > sizeof(dtmap) / sizeof(dtmap[0]) ? \
107                         DT_UNKNOWN : dtmap[x]
108
109 struct fs_ops ext2fs_fsops = {
110         "ext2fs",
111         ext2fs_open,
112         ext2fs_close,
113         ext2fs_read,
114         null_write,
115         ext2fs_seek,
116         ext2fs_stat,
117         ext2fs_readdir
118 };
119
120 #define EXT2_SBSIZE     1024
121 #define EXT2_SBLOCK     (1024 / DEV_BSIZE)      /* block offset of superblock */
122 #define EXT2_MAGIC      0xef53
123 #define EXT2_ROOTINO    2
124
125 #define EXT2_REV0               0       /* original revision of ext2 */
126 #define EXT2_R0_ISIZE           128     /* inode size */
127 #define EXT2_R0_FIRSTINO        11      /* first inode */
128
129 #define EXT2_MINBSHIFT          10      /* mininum block shift */
130 #define EXT2_MINFSHIFT          10      /* mininum frag shift */
131
132 #define NDADDR          12              /* # of direct blocks */
133 #define NIADDR          3               /* # of indirect blocks */
134
135 /*
136  * file system block to disk address
137  */
138 #define fsb_to_db(fs, blk)      ((blk) << (fs)->fs_fsbtodb)
139
140 /*
141  * inode to block group offset
142  * inode to block group
143  * inode to disk address
144  * inode to block offset
145  */
146 #define ino_to_bgo(fs, ino)     (((ino) - 1) % (fs)->fs_ipg)
147 #define ino_to_bg(fs, ino)      (((ino) - 1) / (fs)->fs_ipg)
148 #define ino_to_db(fs, bg, ino) \
149         fsb_to_db(fs, ((bg)[ino_to_bg(fs, ino)].bg_inotbl + \
150             ino_to_bgo(fs, ino) / (fs)->fs_ipb))
151 #define ino_to_bo(fs, ino)      (ino_to_bgo(fs, ino) % (fs)->fs_ipb)
152
153 #define nindir(fs) \
154         ((fs)->fs_bsize / sizeof(u_int32_t))
155 #define lblkno(fs, loc)                         /* loc / bsize */ \
156         ((loc) >> (fs)->fs_bshift)
157 #define smalllblktosize(fs, blk)                /* blk * bsize */ \
158         ((blk) << (fs)->fs_bshift)
159 #define blkoff(fs, loc)                         /* loc % bsize */ \
160         ((loc) & (fs)->fs_bmask)
161 #define fragroundup(fs, size)                   /* roundup(size, fsize) */ \
162         (((size) + (fs)->fs_fmask) & ~(fs)->fs_fmask)
163 #define dblksize(fs, dip, lbn) \
164         (((lbn) >= NDADDR || (dip)->di_size >= smalllblktosize(fs, (lbn) + 1)) \
165             ? (fs)->fs_bsize \
166             : (fragroundup(fs, blkoff(fs, (dip)->di_size))))
167
168 /*
169  * superblock describing ext2fs
170  */
171 struct ext2fs_disk {
172         u_int32_t       fd_inodes;      /* # of inodes */
173         u_int32_t       fd_blocks;      /* # of blocks */
174         u_int32_t       fd_resblk;      /* # of reserved blocks */
175         u_int32_t       fd_freeblk;     /* # of free blocks */
176         u_int32_t       fd_freeino;     /* # of free inodes */
177         u_int32_t       fd_firstblk;    /* first data block */
178         u_int32_t       fd_bsize;       /* block size */
179         u_int32_t       fd_fsize;       /* frag size */
180         u_int32_t       fd_bpg;         /* blocks per group */
181         u_int32_t       fd_fpg;         /* frags per group */
182         u_int32_t       fd_ipg;         /* inodes per group */
183         u_int32_t       fd_mtime;       /* mount time */
184         u_int32_t       fd_wtime;       /* write time */
185         u_int16_t       fd_mount;       /* # of mounts */
186         int16_t         fd_maxmount;    /* max # of mounts */
187         u_int16_t       fd_magic;       /* magic number */
188         u_int16_t       fd_state;       /* state */
189         u_int16_t       fd_eflag;       /* error flags */
190         u_int16_t       fd_mnrrev;      /* minor revision */
191         u_int32_t       fd_lastchk;     /* last check */
192         u_int32_t       fd_chkintvl;    /* maximum check interval */
193         u_int32_t       fd_os;          /* os */
194         u_int32_t       fd_revision;    /* revision */
195         u_int16_t       fd_uid;         /* uid for reserved blocks */
196         u_int16_t       fd_gid;         /* gid for reserved blocks */
197
198         u_int32_t       fd_firstino;    /* first non-reserved inode */
199         u_int16_t       fd_isize;       /* inode size */
200         u_int16_t       fd_nblkgrp;     /* block group # of superblock */
201         u_int32_t       fd_fcompat;     /* compatible features */
202         u_int32_t       fd_fincompat;   /* incompatible features */
203         u_int32_t       fd_frocompat;   /* read-only compatibilties */
204         u_int8_t        fd_uuid[16];    /* volume uuid */
205         char            fd_volname[16]; /* volume name */
206         char            fd_fsmnt[64];   /* name last mounted on */
207         u_int32_t       fd_bitmap;      /* compression bitmap */
208
209         u_int8_t        fd_nblkpa;      /* # of blocks to preallocate */        
210         u_int8_t        fd_ndblkpa;     /* # of dir blocks to preallocate */
211 };
212
213 struct ext2fs_core {
214         int             fc_bsize;       /* block size */
215         int             fc_bshift;      /* block shift amount */
216         int             fc_bmask;       /* block mask */
217         int             fc_fsize;       /* frag size */
218         int             fc_fshift;      /* frag shift amount */
219         int             fc_fmask;       /* frag mask */
220         int             fc_isize;       /* inode size */
221         int             fc_imask;       /* inode mask */
222         int             fc_firstino;    /* first non-reserved inode */
223         int             fc_ipb;         /* inodes per block */
224         int             fc_fsbtodb;     /* fsb to ds shift */
225 };
226
227 struct ext2fs {
228         struct          ext2fs_disk fs_fd;
229         char            fs_pad[EXT2_SBSIZE - sizeof(struct ext2fs_disk)];
230         struct          ext2fs_core fs_fc;
231
232 #define fs_magic        fs_fd.fd_magic
233 #define fs_revision     fs_fd.fd_revision
234 #define fs_blocks       fs_fd.fd_blocks
235 #define fs_firstblk     fs_fd.fd_firstblk
236 #define fs_bpg          fs_fd.fd_bpg
237 #define fs_ipg          fs_fd.fd_ipg
238             
239 #define fs_bsize        fs_fc.fc_bsize
240 #define fs_bshift       fs_fc.fc_bshift
241 #define fs_bmask        fs_fc.fc_bmask
242 #define fs_fsize        fs_fc.fc_fsize
243 #define fs_fshift       fs_fc.fc_fshift
244 #define fs_fmask        fs_fc.fc_fmask
245 #define fs_isize        fs_fc.fc_isize
246 #define fs_imask        fs_fc.fc_imask
247 #define fs_firstino     fs_fc.fc_firstino
248 #define fs_ipb          fs_fc.fc_ipb
249 #define fs_fsbtodb      fs_fc.fc_fsbtodb
250 };
251
252 struct ext2blkgrp {
253         u_int32_t       bg_blkmap;      /* block bitmap */
254         u_int32_t       bg_inomap;      /* inode bitmap */
255         u_int32_t       bg_inotbl;      /* inode table */
256         u_int16_t       bg_nfblk;       /* # of free blocks */
257         u_int16_t       bg_nfino;       /* # of free inodes */
258         u_int16_t       bg_ndirs;       /* # of dirs */
259         char            bg_pad[14];
260 };
261
262 struct ext2dinode {
263         u_int16_t       di_mode;        /* mode */
264         u_int16_t       di_uid;         /* uid */
265         u_int32_t       di_size;        /* byte size */
266         u_int32_t       di_atime;       /* access time */
267         u_int32_t       di_ctime;       /* creation time */
268         u_int32_t       di_mtime;       /* modification time */
269         u_int32_t       di_dtime;       /* deletion time */
270         u_int16_t       di_gid;         /* gid */
271         u_int16_t       di_nlink;       /* link count */
272         u_int32_t       di_nblk;        /* block count */
273         u_int32_t       di_flags;       /* file flags */
274
275         u_int32_t       di_osdep1;      /* os dependent stuff */
276
277         u_int32_t       di_db[NDADDR];  /* direct blocks */
278         u_int32_t       di_ib[NIADDR];  /* indirect blocks */
279         u_int32_t       di_version;     /* version */
280         u_int32_t       di_facl;        /* file acl */
281         u_int32_t       di_dacl;        /* dir acl */
282         u_int32_t       di_faddr;       /* fragment addr */
283
284         u_int8_t        di_frag;        /* fragment number */
285         u_int8_t        di_fsize;       /* fragment size */
286
287         char            di_pad[10];
288
289 #define di_shortlink    di_db
290 };
291
292 #define EXT2_MAXNAMLEN       255
293
294 struct ext2dirent {
295         u_int32_t       d_ino;          /* inode */
296         u_int16_t       d_reclen;       /* directory entry length */
297         u_int8_t        d_namlen;       /* name length */
298         u_int8_t        d_type;         /* file type */
299         char            d_name[EXT2_MAXNAMLEN];
300 };
301
302 struct file {
303         off_t           f_seekp;                /* seek pointer */
304         struct          ext2fs *f_fs;           /* pointer to super-block */
305         struct          ext2blkgrp *f_bg;       /* pointer to blkgrp map */
306         struct          ext2dinode f_di;        /* copy of on-disk inode */
307         int             f_nindir[NIADDR];       /* number of blocks mapped by
308                                                    indirect block at level i */
309         char            *f_blk[NIADDR];         /* buffer for indirect block
310                                                    at level i */
311         size_t          f_blksize[NIADDR];      /* size of buffer */
312         daddr_t         f_blkno[NIADDR];        /* disk address of block in
313                                                    buffer */
314         char            *f_buf;                 /* buffer for data block */
315         size_t          f_buf_size;             /* size of data block */
316         daddr_t         f_buf_blkno;            /* block number of data block */
317 };
318
319 /* forward decls */
320 static int      read_inode(ino_t inumber, struct open_file *f);
321 static int      block_map(struct open_file *f, daddr_t file_block,
322                     daddr_t *disk_block_p);
323 static int      buf_read_file(struct open_file *f, char **buf_p,
324                     size_t *size_p);
325 static int      search_directory(char *name, struct open_file *f,
326                     ino_t *inumber_p);
327
328 /*
329  * Open a file.
330  */
331 static int
332 ext2fs_open(const char *upath, struct open_file *f)
333 {
334         struct file *fp;
335         struct ext2fs *fs;
336         size_t buf_size;
337         ino_t inumber, parent_inumber;
338         int i, len, groups, bg_per_blk, blkgrps, mult;
339         int nlinks = 0;
340         int error = 0;
341         char *cp, *ncp, *path = NULL, *buf = NULL;
342         char namebuf[MAXPATHLEN+1];
343         char c;
344
345         /* allocate file system specific data structure */
346         fp = malloc(sizeof(struct file));
347         if (fp == NULL)
348                 return (ENOMEM);
349         bzero(fp, sizeof(struct file));
350         f->f_fsdata = (void *)fp;
351
352         /* allocate space and read super block */
353         fs = (struct ext2fs *)malloc(sizeof(*fs));
354         fp->f_fs = fs;
355         twiddle();
356         error = (f->f_dev->dv_strategy)(f->f_devdata, F_READ,
357             EXT2_SBLOCK, EXT2_SBSIZE, (char *)fs, &buf_size);
358         if (error)
359                 goto out;
360
361         if (buf_size != EXT2_SBSIZE || fs->fs_magic != EXT2_MAGIC) {
362                 error = EINVAL;
363                 goto out;
364         }
365
366         /*
367          * compute in-core values for the superblock
368          */
369         fs->fs_bshift = EXT2_MINBSHIFT + fs->fs_fd.fd_bsize;
370         fs->fs_bsize = 1 << fs->fs_bshift;
371         fs->fs_bmask = fs->fs_bsize - 1;
372
373         fs->fs_fshift = EXT2_MINFSHIFT + fs->fs_fd.fd_fsize;
374         fs->fs_fsize = 1 << fs->fs_fshift;
375         fs->fs_fmask = fs->fs_fsize - 1;
376
377         if (fs->fs_revision == EXT2_REV0) {
378                 fs->fs_isize = EXT2_R0_ISIZE;
379                 fs->fs_firstino = EXT2_R0_FIRSTINO;
380         } else {
381                 fs->fs_isize = fs->fs_fd.fd_isize;
382                 fs->fs_firstino = fs->fs_fd.fd_firstino;
383         }
384         fs->fs_imask = fs->fs_isize - 1;
385         fs->fs_ipb = fs->fs_bsize / fs->fs_isize;
386         fs->fs_fsbtodb = (fs->fs_bsize / DEV_BSIZE) - 1;
387
388         /*
389          * we have to load in the "group descriptors" here
390          */
391         groups = howmany(fs->fs_blocks - fs->fs_firstblk, fs->fs_bpg);
392         bg_per_blk = fs->fs_bsize / sizeof(struct ext2blkgrp);
393         blkgrps = howmany(groups, bg_per_blk);
394         len = blkgrps * fs->fs_bsize;
395
396         fp->f_bg = malloc(len);
397         twiddle();
398         error = (f->f_dev->dv_strategy)(f->f_devdata, F_READ,
399             EXT2_SBLOCK + EXT2_SBSIZE / DEV_BSIZE, len,
400             (char *)fp->f_bg, &buf_size);
401         if (error)
402                 goto out;
403
404         /*
405          * XXX
406          * validation of values?  (blocksize, descriptors, etc?)
407          */
408
409         /*
410          * Calculate indirect block levels.
411          */
412         mult = 1;
413         for (i = 0; i < NIADDR; i++) {
414                 mult *= nindir(fs);
415                 fp->f_nindir[i] = mult;
416         }
417
418         inumber = EXT2_ROOTINO;
419         if ((error = read_inode(inumber, f)) != 0)
420                 goto out;
421
422         path = strdup(upath);
423         if (path == NULL) {
424                 error = ENOMEM;
425                 goto out;
426         }
427         cp = path;
428         while (*cp) {
429                 /*
430                  * Remove extra separators
431                  */
432                 while (*cp == '/')
433                         cp++;
434                 if (*cp == '\0')
435                         break;
436
437                 /*
438                  * Check that current node is a directory.
439                  */
440                 if (! S_ISDIR(fp->f_di.di_mode)) {
441                         error = ENOTDIR;
442                         goto out;
443                 }
444
445                 /*
446                  * Get next component of path name.
447                  */
448                 len = 0;
449
450                 ncp = cp;
451                 while ((c = *cp) != '\0' && c != '/') {
452                         if (++len > EXT2_MAXNAMLEN) {
453                                 error = ENOENT;
454                                 goto out;
455                         }
456                         cp++;
457                 }
458                 *cp = '\0';
459
460                 /*
461                  * Look up component in current directory.
462                  * Save directory inumber in case we find a
463                  * symbolic link.
464                  */
465                 parent_inumber = inumber;
466                 error = search_directory(ncp, f, &inumber);
467                 *cp = c;
468                 if (error)
469                         goto out;
470
471                 /*
472                  * Open next component.
473                  */
474                 if ((error = read_inode(inumber, f)) != 0)
475                         goto out;
476
477                 /*
478                  * Check for symbolic link.
479                  */
480                 if (S_ISLNK(fp->f_di.di_mode)) {
481                         int link_len = fp->f_di.di_size;
482                         int len;
483
484                         len = strlen(cp);
485                         if (link_len + len > MAXPATHLEN ||
486                             ++nlinks > MAXSYMLINKS) {
487                                 error = ENOENT;
488                                 goto out;
489                         }
490
491                         bcopy(cp, &namebuf[link_len], len + 1);
492                         if (fp->f_di.di_nblk == 0) {
493                                 bcopy(fp->f_di.di_shortlink,
494                                     namebuf, link_len);
495                         } else {
496                                 /*
497                                  * Read file for symbolic link
498                                  */
499                                 struct ext2fs *fs = fp->f_fs;
500                                 daddr_t disk_block;
501                                 size_t buf_size;
502
503                                 if (! buf)
504                                         buf = malloc(fs->fs_bsize);
505                                 error = block_map(f, (daddr_t)0, &disk_block);
506                                 if (error)
507                                         goto out;
508                                 
509                                 twiddle();
510                                 error = (f->f_dev->dv_strategy)(f->f_devdata,
511                                     F_READ, fsb_to_db(fs, disk_block),
512                                     fs->fs_bsize, buf, &buf_size);
513                                 if (error)
514                                         goto out;
515
516                                 bcopy((char *)buf, namebuf, link_len);
517                         }
518
519                         /*
520                          * If relative pathname, restart at parent directory.
521                          * If absolute pathname, restart at root.
522                          */
523                         cp = namebuf;
524                         if (*cp != '/')
525                                 inumber = parent_inumber;
526                         else
527                                 inumber = (ino_t)EXT2_ROOTINO;
528
529                         if ((error = read_inode(inumber, f)) != 0)
530                                 goto out;
531                 }
532         }
533
534         /*
535          * Found terminal component.
536          */
537         error = 0;
538 out:
539         if (buf)
540                 free(buf);
541         if (path)
542                 free(path);
543         if (error) {
544                 if (fp->f_buf)
545                         free(fp->f_buf);
546                 free(fp->f_fs);
547                 free(fp);
548         }
549         return (error);
550 }
551
552 /*
553  * Read a new inode into a file structure.
554  */
555 static int
556 read_inode(ino_t inumber, struct open_file *f)
557 {
558         struct file *fp = (struct file *)f->f_fsdata;
559         struct ext2fs *fs = fp->f_fs;
560         struct ext2dinode *dp;
561         char *buf;
562         size_t rsize;
563         int level, error = 0;
564
565         /*
566          * Read inode and save it.
567          */
568         buf = malloc(fs->fs_bsize);
569         twiddle();
570         error = (f->f_dev->dv_strategy)(f->f_devdata, F_READ,
571             ino_to_db(fs, fp->f_bg, inumber), fs->fs_bsize, buf, &rsize);
572         if (error)
573                 goto out;
574         if (rsize != fs->fs_bsize) {
575                 error = EIO;
576                 goto out;
577         }
578
579         dp = (struct ext2dinode *)buf;
580         fp->f_di = dp[ino_to_bo(fs, inumber)];
581
582         /* clear out old buffers */
583         for (level = 0; level < NIADDR; level++)
584                 fp->f_blkno[level] = -1;
585         fp->f_buf_blkno = -1;
586
587 out:
588         free(buf);
589         return (error);  
590 }
591
592 /*
593  * Given an offset in a file, find the disk block number that
594  * contains that block.
595  */
596 static int
597 block_map(struct open_file *f, daddr_t file_block, daddr_t *disk_block_p)
598 {
599         struct file *fp = (struct file *)f->f_fsdata;
600         struct ext2fs *fs = fp->f_fs;
601         daddr_t ind_block_num;
602         daddr_t *ind_p;
603         int idx, level;
604         int error;
605
606         /*
607          * Index structure of an inode:
608          *
609          * di_db[0..NDADDR-1]   hold block numbers for blocks
610          *                      0..NDADDR-1
611          *
612          * di_ib[0]             index block 0 is the single indirect block
613          *                      holds block numbers for blocks
614          *                      NDADDR .. NDADDR + NINDIR(fs)-1
615          *
616          * di_ib[1]             index block 1 is the double indirect block
617          *                      holds block numbers for INDEX blocks for blocks
618          *                      NDADDR + NINDIR(fs) ..
619          *                      NDADDR + NINDIR(fs) + NINDIR(fs)**2 - 1
620          *
621          * di_ib[2]             index block 2 is the triple indirect block
622          *                      holds block numbers for double-indirect
623          *                      blocks for blocks
624          *                      NDADDR + NINDIR(fs) + NINDIR(fs)**2 ..
625          *                      NDADDR + NINDIR(fs) + NINDIR(fs)**2
626          *                              + NINDIR(fs)**3 - 1
627          */
628
629         if (file_block < NDADDR) {
630                 /* Direct block. */
631                 *disk_block_p = fp->f_di.di_db[file_block];
632                 return (0);
633         }
634
635         file_block -= NDADDR;
636
637         /*
638          * nindir[0] = NINDIR
639          * nindir[1] = NINDIR**2
640          * nindir[2] = NINDIR**3
641          *      etc
642          */
643         for (level = 0; level < NIADDR; level++) {
644                 if (file_block < fp->f_nindir[level])
645                         break;
646                 file_block -= fp->f_nindir[level];
647         }
648         if (level == NIADDR) {
649                 /* Block number too high */
650                 return (EFBIG);
651         }
652
653         ind_block_num = fp->f_di.di_ib[level];
654
655         for (; level >= 0; level--) {
656                 if (ind_block_num == 0) {
657                         *disk_block_p = 0;      /* missing */
658                         return (0);
659                 }
660
661                 if (fp->f_blkno[level] != ind_block_num) {
662                         if (fp->f_blk[level] == (char *)0)
663                                 fp->f_blk[level] =
664                                         malloc(fs->fs_bsize);
665                         twiddle();
666                         error = (f->f_dev->dv_strategy)(f->f_devdata, F_READ,
667                             fsb_to_db(fp->f_fs, ind_block_num), fs->fs_bsize,
668                             fp->f_blk[level], &fp->f_blksize[level]);
669                         if (error)
670                                 return (error);
671                         if (fp->f_blksize[level] != fs->fs_bsize)
672                                 return (EIO);
673                         fp->f_blkno[level] = ind_block_num;
674                 }
675
676                 ind_p = (daddr_t *)fp->f_blk[level];
677
678                 if (level > 0) {
679                         idx = file_block / fp->f_nindir[level - 1];
680                         file_block %= fp->f_nindir[level - 1];
681                 } else {
682                         idx = file_block;
683                 }
684                 ind_block_num = ind_p[idx];
685         }
686
687         *disk_block_p = ind_block_num;
688
689         return (0);
690 }
691
692 /*
693  * Read a portion of a file into an internal buffer.  Return
694  * the location in the buffer and the amount in the buffer.
695  */
696 static int
697 buf_read_file(struct open_file *f, char **buf_p, size_t *size_p)
698 {
699         struct file *fp = (struct file *)f->f_fsdata;
700         struct ext2fs *fs = fp->f_fs;
701         long off;
702         daddr_t file_block;
703         daddr_t disk_block;
704         size_t block_size;
705         int error = 0;
706
707         off = blkoff(fs, fp->f_seekp);
708         file_block = lblkno(fs, fp->f_seekp);
709         block_size = dblksize(fs, &fp->f_di, file_block);
710
711         if (file_block != fp->f_buf_blkno) {
712                 error = block_map(f, file_block, &disk_block);
713                 if (error)
714                         goto done;
715
716                 if (fp->f_buf == (char *)0)
717                         fp->f_buf = malloc(fs->fs_bsize);
718
719                 if (disk_block == 0) {
720                         bzero(fp->f_buf, block_size);
721                         fp->f_buf_size = block_size;
722                 } else {
723                         twiddle();
724                         error = (f->f_dev->dv_strategy)(f->f_devdata, F_READ,
725                             fsb_to_db(fs, disk_block), block_size,
726                             fp->f_buf, &fp->f_buf_size);
727                         if (error)
728                                 goto done;
729                 }
730                 fp->f_buf_blkno = file_block;
731         }
732
733         /*
734          * Return address of byte in buffer corresponding to
735          * offset, and size of remainder of buffer after that
736          * byte.
737          */
738         *buf_p = fp->f_buf + off;
739         *size_p = block_size - off;
740
741         /*
742          * But truncate buffer at end of file.
743          */
744         if (*size_p > fp->f_di.di_size - fp->f_seekp)
745                 *size_p = fp->f_di.di_size - fp->f_seekp;
746 done:
747         return (error);
748 }
749
750 /*
751  * Search a directory for a name and return its
752  * i_number.
753  */
754 static int
755 search_directory(char *name, struct open_file *f, ino_t *inumber_p)
756 {
757         struct file *fp = (struct file *)f->f_fsdata;
758         struct ext2dirent *dp, *edp;
759         char *buf;
760         size_t buf_size;
761         int namlen, length;
762         int error;
763
764         length = strlen(name);
765         fp->f_seekp = 0;
766         while (fp->f_seekp < fp->f_di.di_size) {
767                 error = buf_read_file(f, &buf, &buf_size);
768                 if (error)
769                         return (error);
770                 dp = (struct ext2dirent *)buf;
771                 edp = (struct ext2dirent *)(buf + buf_size);
772                 while (dp < edp) {
773                         if (dp->d_ino == (ino_t)0)
774                                 goto next;
775                         namlen = dp->d_namlen;
776                         if (namlen == length &&
777                             strncmp(name, dp->d_name, length) == 0) {
778                                 /* found entry */
779                                 *inumber_p = dp->d_ino;
780                                 return (0);
781                         }
782                 next:
783                         dp = (struct ext2dirent *)((char *)dp + dp->d_reclen);
784                 }
785                 fp->f_seekp += buf_size;
786         }
787         return (ENOENT);
788 }
789
790 static int
791 ext2fs_close(struct open_file *f)
792 {
793         struct file *fp = (struct file *)f->f_fsdata;
794         int level;
795
796         f->f_fsdata = (void *)0;
797         if (fp == (struct file *)0)
798                 return (0);
799
800         for (level = 0; level < NIADDR; level++) {
801                 if (fp->f_blk[level])
802                         free(fp->f_blk[level]);
803         }
804         if (fp->f_buf)
805                 free(fp->f_buf);
806         if (fp->f_bg)
807                 free(fp->f_bg);
808         free(fp->f_fs);
809         free(fp);
810         return (0);
811 }
812
813 static int
814 ext2fs_read(struct open_file *f, void *addr, size_t size, size_t *resid)
815 {
816         struct file *fp = (struct file *)f->f_fsdata;
817         size_t csize, buf_size;
818         char *buf;
819         int error = 0;
820
821         while (size != 0) {
822                 if (fp->f_seekp >= fp->f_di.di_size)
823                         break;
824
825                 error = buf_read_file(f, &buf, &buf_size);
826                 if (error)
827                         break;
828
829                 csize = size;
830                 if (csize > buf_size)
831                         csize = buf_size;
832
833                 bcopy(buf, addr, csize);
834
835                 fp->f_seekp += csize;
836                 addr += csize;
837                 size -= csize;
838         }
839         if (resid)
840                 *resid = size;
841         return (error);
842 }
843
844 static off_t
845 ext2fs_seek(struct open_file *f, off_t offset, int where)
846 {
847         struct file *fp = (struct file *)f->f_fsdata;
848
849         switch (where) {
850         case SEEK_SET:
851                 fp->f_seekp = offset;
852                 break;
853         case SEEK_CUR:
854                 fp->f_seekp += offset;
855                 break;
856         case SEEK_END:
857                 fp->f_seekp = fp->f_di.di_size - offset;
858                 break;
859         default:
860                 return (-1);
861         }
862         return (fp->f_seekp);
863 }
864
865 static int
866 ext2fs_stat(struct open_file *f, struct stat *sb)
867 {
868         struct file *fp = (struct file *)f->f_fsdata;
869
870         /* only important stuff */
871         sb->st_mode = fp->f_di.di_mode;
872         sb->st_uid = fp->f_di.di_uid;
873         sb->st_gid = fp->f_di.di_gid;
874         sb->st_size = fp->f_di.di_size;
875         return (0);
876 }
877
878 static int
879 ext2fs_readdir(struct open_file *f, struct dirent *d)
880 {
881         struct file *fp = (struct file *)f->f_fsdata;
882         struct ext2dirent *ed;
883         char *buf;
884         size_t buf_size;
885         int error;
886
887         /*
888          * assume that a directory entry will not be split across blocks
889          */
890 again:
891         if (fp->f_seekp >= fp->f_di.di_size)
892                 return (ENOENT);
893         error = buf_read_file(f, &buf, &buf_size);
894         if (error)
895                 return (error);
896         ed = (struct ext2dirent *)buf;
897         fp->f_seekp += ed->d_reclen;
898         if (ed->d_ino == (ino_t)0)
899                 goto again;
900         d->d_type = EXTFTODT(ed->d_type);
901         strncpy(d->d_name, ed->d_name, ed->d_namlen);
902         d->d_name[ed->d_namlen] = '\0';
903         return (0);
904 }