Commit | Line | Data |
---|---|---|
da7c5cc6 | 1 | /* |
9fc995cf | 2 | * Copyright (c) 1989, 1991 Regents of the University of California. |
7188ac27 | 3 | * All rights reserved. |
da7c5cc6 | 4 | * |
b702c21d | 5 | * %sccs.include.redist.c% |
7188ac27 | 6 | * |
bc375a66 | 7 | * @(#)lfs_balloc.c 7.24 (Berkeley) %G% |
da7c5cc6 | 8 | */ |
52212483 | 9 | |
f6437c6d KB |
10 | #include <sys/param.h> |
11 | #include <sys/buf.h> | |
12 | #include <sys/proc.h> | |
13 | #include <sys/vnode.h> | |
14 | #include <sys/mount.h> | |
15 | #include <sys/resourcevar.h> | |
16 | #include <sys/specdev.h> | |
17 | #include <sys/trace.h> | |
c6f5111d | 18 | |
9fc995cf KB |
19 | #include <ufs/ufs/quota.h> |
20 | #include <ufs/ufs/inode.h> | |
21 | #include <ufs/ufs/ufsmount.h> | |
f6437c6d | 22 | |
9fc995cf KB |
23 | #include <ufs/lfs/lfs.h> |
24 | #include <ufs/lfs/lfs_extern.h> | |
52212483 | 25 | |
bc375a66 | 26 | int lfs_getlbns __P((struct vnode *, daddr_t, INDIR *, int *)); |
1cc06455 | 27 | |
52212483 | 28 | /* |
f6437c6d KB |
29 | * Bmap converts a the logical block number of a file to its physical block |
30 | * number on the disk. The conversion is done by using the logical block | |
31 | * number to index into the array of block pointers described by the dinode. | |
1cc06455 KB |
32 | */ |
33 | int | |
34 | lfs_bmap(vp, bn, vpp, bnp) | |
35 | struct vnode *vp; | |
36 | register daddr_t bn; | |
37 | struct vnode **vpp; | |
38 | daddr_t *bnp; | |
39 | { | |
40 | #ifdef VERBOSE | |
41 | printf("lfs_bmap\n"); | |
42 | #endif | |
43 | /* | |
44 | * Check for underlying vnode requests and ensure that logical | |
45 | * to physical mapping is requested. | |
46 | */ | |
47 | if (vpp != NULL) | |
48 | *vpp = VTOI(vp)->i_devvp; | |
49 | if (bnp == NULL) | |
50 | return (0); | |
51 | ||
52 | return (lfs_bmaparray(vp, bn, bnp, NULL, NULL)); | |
53 | } | |
54 | ||
55 | /* | |
fce00cda KB |
56 | * LFS has a different version of bmap from FFS because of a naming conflict. |
57 | * In FFS, meta blocks are given real disk addresses at allocation time, and | |
58 | * are linked into the device vnode, using a logical block number which is | |
59 | * the same as the physical block number. This can't be done by LFS because | |
60 | * blocks aren't given disk addresses until they're written, so there's no | |
61 | * way to distinguish the meta-data blocks for one file from any other file. | |
62 | * This means that meta-data blocks have to be on the vnode for the file so | |
63 | * they can be found, and have to have "names" different from the standard | |
64 | * data blocks. To do this, we divide the name space into positive and | |
65 | * negative block numbers, and give the meta-data blocks negative logical | |
175a033b KB |
66 | * numbers. Indirect blocks are addressed by the negative address of the |
67 | * first data block to which they point. Double indirect blocks are addressed | |
68 | * by one less than the address of the first indirect block to which they | |
69 | * point. Triple indirect blocks are addressed by one less than the address | |
70 | * of the first double indirect block to which they point. | |
52212483 | 71 | */ |
e3b6a940 | 72 | int |
1cc06455 | 73 | lfs_bmaparray(vp, bn, bnp, ap, nump) |
8ad16d99 | 74 | struct vnode *vp; |
7188ac27 | 75 | register daddr_t bn; |
8ad16d99 | 76 | daddr_t *bnp; |
1cc06455 KB |
77 | INDIR *ap; |
78 | int *nump; | |
52212483 | 79 | { |
8ad16d99 | 80 | register struct inode *ip; |
7188ac27 | 81 | struct buf *bp; |
1cc06455 | 82 | struct lfs *fs; |
fce00cda | 83 | struct vnode *devvp; |
1cc06455 KB |
84 | INDIR a[NIADDR], *xap; |
85 | daddr_t *bap, daddr; | |
86 | long metalbn; | |
87 | int error, num, off; | |
7188ac27 | 88 | |
d5075120 | 89 | |
1cc06455 | 90 | ip = VTOI(vp); |
fce00cda | 91 | #ifdef VERBOSE |
1cc06455 KB |
92 | printf("lfs_bmap: block number %d, inode %d\n", bn, ip->i_number); |
93 | #endif | |
94 | #ifdef DIAGNOSTIC | |
95 | if (ap != NULL && nump == NULL || ap == NULL && nump != NULL) | |
96 | panic("lfs_bmaparray: invalid arguments"); | |
fce00cda | 97 | #endif |
175a033b | 98 | |
1cc06455 KB |
99 | xap = ap == NULL ? a : ap; |
100 | if (error = lfs_getlbns(vp, bn, xap, nump)) | |
101 | return (error); | |
f6437c6d | 102 | |
1cc06455 | 103 | num = *nump; |
fce00cda | 104 | fs = ip->i_lfs; |
1cc06455 KB |
105 | if (num == 0) { |
106 | *bnp = ip->i_db[bn]; | |
107 | if (*bnp == 0) | |
108 | *bnp = UNASSIGNED; | |
109 | return (0); | |
7188ac27 | 110 | } |
d5075120 | 111 | |
1cc06455 | 112 | /* Fetch through the indirect blocks. */ |
fce00cda | 113 | bp = NULL; |
d5075120 | 114 | devvp = VFSTOUFS(vp->v_mount)->um_devvp; |
1cc06455 KB |
115 | for (bap = ip->i_ib; num--; off = xap->in_off, ++xap) { |
116 | off = xap->in_off; | |
117 | metalbn = xap->in_lbn; | |
118 | ||
fce00cda KB |
119 | /* |
120 | * In LFS, it's possible to have a block appended to a file | |
121 | * for which the meta-blocks have not yet been allocated. | |
122 | * This is a win if the file never gets written or if the | |
123 | * file's growing. | |
124 | */ | |
125 | if ((daddr = bap[off]) == 0) { | |
e3b6a940 | 126 | daddr = UNASSIGNED; |
d5075120 KB |
127 | break; |
128 | } | |
175a033b KB |
129 | |
130 | /* If searching for a meta-data block, quit when found. */ | |
1cc06455 | 131 | if (metalbn == bn) |
175a033b KB |
132 | break; |
133 | ||
fce00cda KB |
134 | /* |
135 | * Read in the appropriate indirect block. LFS can't do a | |
136 | * bread because bread knows that FFS will hand it the device | |
137 | * vnode, not the file vnode, so the b_dev and b_blkno would | |
138 | * be wrong. | |
139 | * | |
140 | * XXX | |
141 | * This REALLY needs to be fixed, at the very least it needs | |
1cc06455 KB |
142 | * to be rethought when the buffer cache goes away. When it's |
143 | * fixed, change lfs_bmaparray and lfs_getlbns to take an ip, | |
144 | * not a vp. | |
fce00cda | 145 | */ |
d5075120 | 146 | if (bp) |
7188ac27 | 147 | brelse(bp); |
175a033b | 148 | bp = getblk(vp, metalbn, fs->lfs_bsize); |
d5075120 | 149 | if (bp->b_flags & (B_DONE | B_DELWRI)) { |
175a033b | 150 | trace(TR_BREADHIT, pack(vp, size), metalbn); |
d5075120 | 151 | } else { |
175a033b | 152 | trace(TR_BREADMISS, pack(vp, size), metalbn); |
fce00cda | 153 | bp->b_blkno = daddr; |
175a033b | 154 | bp->b_flags |= B_READ; |
d5075120 | 155 | bp->b_dev = devvp->v_rdev; |
275ca4f0 | 156 | (devvp->v_op->vop_strategy)(bp); |
d5075120 KB |
157 | curproc->p_stats->p_ru.ru_inblock++; /* XXX */ |
158 | if (error = biowait(bp)) { | |
159 | brelse(bp); | |
160 | return (error); | |
161 | } | |
7188ac27 KM |
162 | } |
163 | bap = bp->b_un.b_daddr; | |
7188ac27 | 164 | } |
d5075120 KB |
165 | if (bp) |
166 | brelse(bp); | |
167 | ||
168 | *bnp = daddr; | |
7188ac27 | 169 | return (0); |
52212483 | 170 | } |
1cc06455 KB |
171 | |
172 | /* | |
173 | * Create an array of logical block number/offset pairs which represent the | |
174 | * path of indirect blocks required to access a data block. The first "pair" | |
175 | * contains the logical block number of the appropriate single, double or | |
176 | * triple indirect block and the offset into the inode indirect block array. | |
177 | * Note, the logical block number of the inode single/double/triple indirect | |
178 | * block appears twice in the array, once with the offset into the i_ib and | |
179 | * once with the offset into the page itself. | |
180 | */ | |
181 | int | |
182 | lfs_getlbns(vp, bn, ap, nump) | |
183 | struct vnode *vp; | |
184 | register daddr_t bn; | |
185 | INDIR *ap; | |
186 | int *nump; | |
187 | { | |
188 | struct lfs *fs; | |
189 | long metalbn, realbn; | |
190 | int j, off, sh; | |
191 | ||
192 | #ifdef VERBOSE | |
193 | printf("lfs_getlbns: bn %d, inode %d\n", bn, VTOI(vp)->i_number); | |
194 | #endif | |
195 | *nump = 0; | |
196 | realbn = bn; | |
197 | if ((long)bn < 0) | |
198 | bn = -(long)bn; | |
199 | ||
200 | /* The first NDADDR blocks are direct blocks. */ | |
201 | if (bn < NDADDR) | |
202 | return(0); | |
203 | ||
204 | /* | |
205 | * Determine the number of levels of indirection. After this loop | |
206 | * is done, sh indicates the number of data blocks possible at the | |
207 | * given level of indirection, and NIADDR - j is the number of levels | |
208 | * of indirection needed to locate the requested block. | |
209 | */ | |
210 | bn -= NDADDR; | |
211 | fs = VTOI(vp)->i_lfs; | |
212 | sh = 1; | |
213 | for (j = NIADDR; j > 0; j--) { | |
214 | sh *= NINDIR(fs); | |
215 | if (bn < sh) | |
216 | break; | |
217 | bn -= sh; | |
218 | } | |
219 | if (j == 0) | |
220 | return (EFBIG); | |
221 | ||
222 | /* Calculate the address of the first meta-block. */ | |
223 | if (realbn >= 0) | |
224 | metalbn = -(realbn - bn + NIADDR - j); | |
225 | else | |
226 | metalbn = -(-realbn - bn + NIADDR - j); | |
227 | ||
228 | /* | |
229 | * At each iteration, off is the offset into the bap array which is | |
230 | * an array of disk addresses at the current level of indirection. | |
231 | * The logical block number and the offset in that block are stored | |
232 | * into the argument array. | |
233 | */ | |
234 | ++*nump; | |
235 | ap->in_lbn = metalbn; | |
236 | ap->in_off = off = NIADDR - j; | |
237 | ap++; | |
238 | for (; j <= NIADDR; j++) { | |
239 | /* If searching for a meta-data block, quit when found. */ | |
240 | if (metalbn == realbn) | |
241 | break; | |
242 | ||
243 | sh /= NINDIR(fs); | |
244 | off = (bn / sh) % NINDIR(fs); | |
245 | ||
246 | ++*nump; | |
247 | ap->in_lbn = metalbn; | |
248 | ap->in_off = off; | |
249 | ++ap; | |
250 | ||
251 | metalbn -= -1 + off * sh; | |
252 | } | |
253 | return (0); | |
254 | } |