1 /* 2 * Copyright (c) 1989, 1991 Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 * 7 * @(#)lfs_balloc.c 7.37 (Berkeley) 09/02/92 8 */ 9 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/trace.h> 17 18 #include <miscfs/specfs/specdev.h> 19 20 #include <ufs/ufs/quota.h> 21 #include <ufs/ufs/inode.h> 22 #include <ufs/ufs/ufsmount.h> 23 24 #include <ufs/lfs/lfs.h> 25 #include <ufs/lfs/lfs_extern.h> 26 27 int lfs_getlbns __P((struct vnode *, daddr_t, INDIR *, int *)); 28 29 /* 30 * Bmap converts a the logical block number of a file to its physical block 31 * number on the disk. The conversion is done by using the logical block 32 * number to index into the array of block pointers described by the dinode. 33 */ 34 int 35 lfs_bmap(ap) 36 struct vop_bmap_args /* { 37 struct vnode *a_vp; 38 daddr_t a_bn; 39 struct vnode **a_vpp; 40 daddr_t *a_bnp; 41 } */ *ap; 42 { 43 /* 44 * Check for underlying vnode requests and ensure that logical 45 * to physical mapping is requested. 46 */ 47 if (ap->a_vpp != NULL) 48 *ap->a_vpp = VTOI(ap->a_vp)->i_devvp; 49 if (ap->a_bnp == NULL) 50 return (0); 51 52 return (lfs_bmaparray(ap->a_vp, ap->a_bn, ap->a_bnp, NULL, NULL)); 53 } 54 55 /* 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 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. 71 */ 72 int 73 lfs_bmaparray(vp, bn, bnp, ap, nump) 74 struct vnode *vp; 75 register daddr_t bn; 76 daddr_t *bnp; 77 INDIR *ap; 78 int *nump; 79 { 80 register struct inode *ip; 81 struct buf *bp; 82 struct lfs *fs; 83 struct vnode *devvp; 84 INDIR a[NIADDR], *xap; 85 daddr_t *bap, daddr; 86 long metalbn; 87 int bb, error, num, off; 88 struct vop_strategy_args vop_strategy_a; 89 90 ip = VTOI(vp); 91 #ifdef DIAGNOSTIC 92 if (ap != NULL && nump == NULL || ap == NULL && nump != NULL) 93 panic("lfs_bmaparray: invalid arguments"); 94 #endif 95 96 xap = ap == NULL ? a : ap; 97 if (!nump) 98 nump = # 99 if (error = lfs_getlbns(vp, bn, xap, nump)) 100 return (error); 101 102 num = *nump; 103 if (num == 0) { 104 *bnp = ip->i_db[bn]; 105 if (*bnp == 0) 106 *bnp = UNASSIGNED; 107 return (0); 108 } 109 110 111 /* Get disk address out of indirect block array */ 112 daddr = ip->i_ib[xap->in_off]; 113 114 /* Fetch through the indirect blocks. */ 115 fs = ip->i_lfs; 116 devvp = VFSTOUFS(vp->v_mount)->um_devvp; 117 118 for (bp = NULL, ++xap; --num; ++xap) { 119 /* 120 * If we were called explicitly then we don't want to create 121 * indirect blocks. Since BMAP calls pass NULL for the ap, 122 * we can use that to detect if we are called from BMAP or not. 123 */ 124 if (daddr == 0 && ap != NULL) 125 break; 126 127 /* If looking for a meta-block, break out when we find it. */ 128 metalbn = xap->in_lbn; 129 if (metalbn == bn) 130 break; 131 132 /* 133 * Read in the appropriate indirect block. LFS can't do a 134 * bread because bread knows that FFS will hand it the device 135 * vnode, not the file vnode, so the b_dev and b_blkno would 136 * be wrong. 137 * 138 * XXX 139 * This REALLY needs to be fixed, at the very least it needs 140 * to be rethought when the buffer cache goes away. When it's 141 * fixed, change lfs_bmaparray and lfs_getlbns to take an ip, 142 * not a vp. 143 */ 144 if (bp) 145 brelse(bp); 146 bp = getblk(vp, metalbn, fs->lfs_bsize); 147 if (bp->b_flags & (B_DONE | B_DELWRI)) { 148 trace(TR_BREADHIT, pack(vp, size), metalbn); 149 } else if (!daddr) { 150 /* Need to create an indirect block */ 151 trace(TR_BREADMISS, pack(vp, size), metalbn); 152 bzero(bp->b_un.b_addr, fs->lfs_bsize); 153 *bnp = UNASSIGNED; 154 bb = fsbtodb(fs, 1); 155 /* XXX Need to figure out how to get a cred */ 156 if (!ISSPACE_XXX(fs, bb)) { 157 bp->b_flags |= B_INVAL; 158 brelse (bp); 159 return (ENOSPC); 160 } 161 ip->i_blocks += bb; 162 fs->lfs_bfree -= bb; 163 daddr = bp->b_un.b_daddr[xap->in_off]; 164 if (error = VOP_BWRITE(bp)) 165 return (error); 166 bp = NULL; 167 continue; 168 } else { 169 trace(TR_BREADMISS, pack(vp, size), metalbn); 170 bp->b_blkno = daddr; 171 bp->b_flags |= B_READ; 172 bp->b_dev = devvp->v_rdev; 173 /* 174 * Call a strategy VOP by hand. 175 */ 176 vop_strategy_a.a_desc = VDESC(vop_strategy); 177 vop_strategy_a.a_bp=bp; 178 VOCALL(devvp->v_op, VOFFSET(vop_strategy), \ 179 &vop_strategy_a); 180 curproc->p_stats->p_ru.ru_inblock++; /* XXX */ 181 if (error = biowait(bp)) { 182 brelse(bp); 183 return (error); 184 } 185 } 186 daddr = bp->b_un.b_daddr[xap->in_off]; 187 } 188 if (bp) 189 brelse(bp); 190 191 *bnp = daddr == 0 ? UNASSIGNED : daddr; 192 return (0); 193 } 194 195 /* 196 * Create an array of logical block number/offset pairs which represent the 197 * path of indirect blocks required to access a data block. The first "pair" 198 * contains the logical block number of the appropriate single, double or 199 * triple indirect block and the offset into the inode indirect block array. 200 * Note, the logical block number of the inode single/double/triple indirect 201 * block appears twice in the array, once with the offset into the i_ib and 202 * once with the offset into the page itself. 203 */ 204 int 205 lfs_getlbns(vp, bn, ap, nump) 206 struct vnode *vp; 207 register daddr_t bn; 208 INDIR *ap; 209 int *nump; 210 { 211 struct lfs *fs; 212 long metalbn, realbn; 213 int j, numlevels, off, sh; 214 215 if (nump) 216 *nump = 0; 217 numlevels = 0; 218 realbn = bn; 219 if ((long)bn < 0) 220 bn = -(long)bn; 221 222 /* The first NDADDR blocks are direct blocks. */ 223 if (bn < NDADDR) 224 return (0); 225 226 /* 227 * Determine the number of levels of indirection. After this loop 228 * is done, sh indicates the number of data blocks possible at the 229 * given level of indirection, and NIADDR - j is the number of levels 230 * of indirection needed to locate the requested block. 231 */ 232 bn -= NDADDR; 233 fs = VTOI(vp)->i_lfs; 234 sh = 1; 235 for (j = NIADDR; j > 0; j--) { 236 sh *= NINDIR(fs); 237 if (bn < sh) 238 break; 239 bn -= sh; 240 } 241 if (j == 0) 242 return (EFBIG); 243 244 /* Calculate the address of the first meta-block. */ 245 if (realbn >= 0) 246 metalbn = -(realbn - bn + NIADDR - j); 247 else 248 metalbn = -(-realbn - bn + NIADDR - j); 249 250 /* 251 * At each iteration, off is the offset into the bap array which is 252 * an array of disk addresses at the current level of indirection. 253 * The logical block number and the offset in that block are stored 254 * into the argument array. 255 */ 256 ++numlevels; 257 ap->in_lbn = metalbn; 258 ap->in_off = off = NIADDR - j; 259 ap++; 260 for (; j <= NIADDR; j++) { 261 /* If searching for a meta-data block, quit when found. */ 262 if (metalbn == realbn) 263 break; 264 265 sh /= NINDIR(fs); 266 off = (bn / sh) % NINDIR(fs); 267 268 ++numlevels; 269 ap->in_lbn = metalbn; 270 ap->in_off = off; 271 ++ap; 272 273 metalbn -= -1 + off * sh; 274 } 275 if (nump) 276 *nump = numlevels; 277 return (0); 278 } 279 280 int 281 lfs_balloc(vp, iosize, lbn, bpp) 282 struct vnode *vp; 283 u_long iosize; 284 daddr_t lbn; 285 struct buf **bpp; 286 { 287 struct buf *bp; 288 struct inode *ip; 289 struct lfs *fs; 290 daddr_t daddr; 291 int bb, error; 292 293 ip = VTOI(vp); 294 fs = ip->i_lfs; 295 296 /* 297 * Three cases: it's a block beyond the end of file, it's a block in 298 * the file that may or may not have been assigned a disk address or 299 * we're writing an entire block. Note, if the daddr is unassigned, 300 * the block might still have existed in the cache. If it did, make 301 * sure we don't count it as a new block or zero out its contents. 302 * Note that we always call bmap, even if it's a new block beyond 303 * the end of file. The reason is so that we can allocate any new 304 * indirect blocks that are necessary. 305 */ 306 307 *bpp = NULL; 308 if (error = VOP_BMAP(vp, lbn, NULL, &daddr)) 309 return (error); 310 311 if (daddr == UNASSIGNED || iosize == fs->lfs_bsize) { 312 *bpp = bp = getblk(vp, lbn, fs->lfs_bsize); 313 if (daddr == UNASSIGNED && !(bp->b_flags & B_CACHE)) { 314 bb = fsbtodb(fs, 1); 315 if (!ISSPACE_XXX(fs, bb)) { 316 bp->b_flags |= B_INVAL; 317 *bpp = NULL; 318 brelse(bp); 319 return (ENOSPC); 320 } 321 ip->i_blocks += bb; 322 fs->lfs_bfree -= bb; 323 if (iosize != fs->lfs_bsize) 324 clrbuf(bp); 325 } 326 return (0); 327 } 328 return (bread(vp, lbn, fs->lfs_bsize, NOCRED, bpp)); 329 } 330