1 /* 2 * Copyright (c) 1989, 1991, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 * 7 * @(#)ufs_bmap.c 8.4 (Berkeley) 09/23/93 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 #include <ufs/ufs/ufs_extern.h> 24 25 /* 26 * Bmap converts a the logical block number of a file to its physical block 27 * number on the disk. The conversion is done by using the logical block 28 * number to index into the array of block pointers described by the dinode. 29 */ 30 int 31 ufs_bmap(ap) 32 struct vop_bmap_args /* { 33 struct vnode *a_vp; 34 daddr_t a_bn; 35 struct vnode **a_vpp; 36 daddr_t *a_bnp; 37 int *a_runp; 38 } */ *ap; 39 { 40 /* 41 * Check for underlying vnode requests and ensure that logical 42 * to physical mapping is requested. 43 */ 44 if (ap->a_vpp != NULL) 45 *ap->a_vpp = VTOI(ap->a_vp)->i_devvp; 46 if (ap->a_bnp == NULL) 47 return (0); 48 49 return (ufs_bmaparray(ap->a_vp, ap->a_bn, ap->a_bnp, NULL, NULL, 50 ap->a_runp)); 51 } 52 53 /* 54 * Indirect blocks are now on the vnode for the file. They are given negative 55 * logical block numbers. Indirect blocks are addressed by the negative 56 * address of the first data block to which they point. Double indirect blocks 57 * are addressed by one less than the address of the first indirect block to 58 * which they point. Triple indirect blocks are addressed by one less than 59 * the address of the first double indirect block to which they point. 60 * 61 * ufs_bmaparray does the bmap conversion, and if requested returns the 62 * array of logical blocks which must be traversed to get to a block. 63 * Each entry contains the offset into that block that gets you to the 64 * next block and the disk address of the block (if it is assigned). 65 */ 66 67 int 68 ufs_bmaparray(vp, bn, bnp, ap, nump, runp) 69 struct vnode *vp; 70 register daddr_t bn; 71 daddr_t *bnp; 72 struct indir *ap; 73 int *nump; 74 int *runp; 75 { 76 register struct inode *ip; 77 struct buf *bp; 78 struct ufsmount *ump; 79 struct mount *mp; 80 struct vnode *devvp; 81 struct indir a[NIADDR], *xap; 82 daddr_t *bap, daddr; 83 long metalbn; 84 int bb, error, maxrun, num, off; 85 struct vop_strategy_args vop_strategy_a; 86 87 ip = VTOI(vp); 88 mp = vp->v_mount; 89 ump = VFSTOUFS(mp); 90 #ifdef DIAGNOSTIC 91 if (ap != NULL && nump == NULL || ap == NULL && nump != NULL) 92 panic("ufs_bmaparray: invalid arguments"); 93 #endif 94 95 if (runp) { 96 /* 97 * XXX 98 * If MAXBSIZE is the largest transfer the disks can handle, 99 * we probably want maxrun to be 1 block less so that we 100 * don't create a block larger than the device can handle. 101 */ 102 *runp = 0; 103 maxrun = MAXBSIZE / mp->mnt_stat.f_iosize - 1; 104 } 105 106 xap = ap == NULL ? a : ap; 107 if (!nump) 108 nump = # 109 if (error = ufs_getlbns(vp, bn, xap, nump)) 110 return (error); 111 112 num = *nump; 113 if (num == 0) { 114 *bnp = blkptrtodb(ump, ip->i_db[bn]); 115 if (*bnp == 0) 116 *bnp = -1; 117 else if (runp) 118 for (++bn; bn < NDADDR && *runp < maxrun && 119 is_sequential(ump, ip->i_db[bn - 1], ip->i_db[bn]); 120 ++bn, ++*runp); 121 return (0); 122 } 123 124 125 /* Get disk address out of indirect block array */ 126 daddr = ip->i_ib[xap->in_off]; 127 128 devvp = VFSTOUFS(vp->v_mount)->um_devvp; 129 for (bp = NULL, ++xap; --num; ++xap) { 130 /* 131 * Exit the loop if there is no disk address assigned yet and 132 * the indirect block isn't in the cache, or if we were 133 * looking for an indirect block and we've found it. 134 */ 135 136 metalbn = xap->in_lbn; 137 if (daddr == 0 && !incore(vp, metalbn) || metalbn == bn) 138 break; 139 /* 140 * If we get here, we've either got the block in the cache 141 * or we have a disk address for it, go fetch it. 142 */ 143 if (bp) 144 brelse(bp); 145 146 xap->in_exists = 1; 147 bp = getblk(vp, metalbn, mp->mnt_stat.f_iosize, 0, 0); 148 if (bp->b_flags & (B_DONE | B_DELWRI)) { 149 trace(TR_BREADHIT, pack(vp, size), metalbn); 150 } 151 #ifdef DIAGNOSTIC 152 else if (!daddr) 153 panic("ufs_bmaparry: indirect block not in cache"); 154 #endif 155 else { 156 trace(TR_BREADMISS, pack(vp, size), metalbn); 157 bp->b_blkno = blkptrtodb(ump, daddr); 158 bp->b_flags |= B_READ; 159 VOP_STRATEGY(bp); 160 curproc->p_stats->p_ru.ru_inblock++; /* XXX */ 161 if (error = biowait(bp)) { 162 brelse(bp); 163 return (error); 164 } 165 } 166 167 daddr = ((daddr_t *)bp->b_data)[xap->in_off]; 168 if (num == 1 && daddr && runp) 169 for (bn = xap->in_off + 1; 170 bn < MNINDIR(ump) && *runp < maxrun && 171 is_sequential(ump, ((daddr_t *)bp->b_data)[bn - 1], 172 ((daddr_t *)bp->b_data)[bn]); 173 ++bn, ++*runp); 174 } 175 if (bp) 176 brelse(bp); 177 178 daddr = blkptrtodb(ump, daddr); 179 *bnp = daddr == 0 ? -1 : daddr; 180 return (0); 181 } 182 183 /* 184 * Create an array of logical block number/offset pairs which represent the 185 * path of indirect blocks required to access a data block. The first "pair" 186 * contains the logical block number of the appropriate single, double or 187 * triple indirect block and the offset into the inode indirect block array. 188 * Note, the logical block number of the inode single/double/triple indirect 189 * block appears twice in the array, once with the offset into the i_ib and 190 * once with the offset into the page itself. 191 */ 192 int 193 ufs_getlbns(vp, bn, ap, nump) 194 struct vnode *vp; 195 register daddr_t bn; 196 struct indir *ap; 197 int *nump; 198 { 199 long metalbn, realbn; 200 struct ufsmount *ump; 201 int blockcnt, i, numlevels, off; 202 203 ump = VFSTOUFS(vp->v_mount); 204 if (nump) 205 *nump = 0; 206 numlevels = 0; 207 realbn = bn; 208 if ((long)bn < 0) 209 bn = -(long)bn; 210 211 /* The first NDADDR blocks are direct blocks. */ 212 if (bn < NDADDR) 213 return (0); 214 215 /* 216 * Determine the number of levels of indirection. After this loop 217 * is done, blockcnt indicates the number of data blocks possible 218 * at the given level of indirection, and NIADDR - i is the number 219 * of levels of indirection needed to locate the requested block. 220 */ 221 for (blockcnt = 1, i = NIADDR, bn -= NDADDR;; i--, bn -= blockcnt) { 222 if (i == 0) 223 return (EFBIG); 224 blockcnt *= MNINDIR(ump); 225 if (bn < blockcnt) 226 break; 227 } 228 229 /* Calculate the address of the first meta-block. */ 230 if (realbn >= 0) 231 metalbn = -(realbn - bn + NIADDR - i); 232 else 233 metalbn = -(-realbn - bn + NIADDR - i); 234 235 /* 236 * At each iteration, off is the offset into the bap array which is 237 * an array of disk addresses at the current level of indirection. 238 * The logical block number and the offset in that block are stored 239 * into the argument array. 240 */ 241 ap->in_lbn = metalbn; 242 ap->in_off = off = NIADDR - i; 243 ap->in_exists = 0; 244 ap++; 245 for (++numlevels; i <= NIADDR; i++) { 246 /* If searching for a meta-data block, quit when found. */ 247 if (metalbn == realbn) 248 break; 249 250 blockcnt /= MNINDIR(ump); 251 off = (bn / blockcnt) % MNINDIR(ump); 252 253 ++numlevels; 254 ap->in_lbn = metalbn; 255 ap->in_off = off; 256 ap->in_exists = 0; 257 ++ap; 258 259 metalbn -= -1 + off * blockcnt; 260 } 261 if (nump) 262 *nump = numlevels; 263 return (0); 264 } 265