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.5 (Berkeley) 01/04/94 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 daddr; 83 long metalbn; 84 int error, maxrun, num; 85 86 ip = VTOI(vp); 87 mp = vp->v_mount; 88 ump = VFSTOUFS(mp); 89 #ifdef DIAGNOSTIC 90 if (ap != NULL && nump == NULL || ap == NULL && nump != NULL) 91 panic("ufs_bmaparray: invalid arguments"); 92 #endif 93 94 if (runp) { 95 /* 96 * XXX 97 * If MAXBSIZE is the largest transfer the disks can handle, 98 * we probably want maxrun to be 1 block less so that we 99 * don't create a block larger than the device can handle. 100 */ 101 *runp = 0; 102 maxrun = MAXBSIZE / mp->mnt_stat.f_iosize - 1; 103 } 104 105 xap = ap == NULL ? a : ap; 106 if (!nump) 107 nump = # 108 if (error = ufs_getlbns(vp, bn, xap, nump)) 109 return (error); 110 111 num = *nump; 112 if (num == 0) { 113 *bnp = blkptrtodb(ump, ip->i_db[bn]); 114 if (*bnp == 0) 115 *bnp = -1; 116 else if (runp) 117 for (++bn; bn < NDADDR && *runp < maxrun && 118 is_sequential(ump, ip->i_db[bn - 1], ip->i_db[bn]); 119 ++bn, ++*runp); 120 return (0); 121 } 122 123 124 /* Get disk address out of indirect block array */ 125 daddr = ip->i_ib[xap->in_off]; 126 127 devvp = VFSTOUFS(vp->v_mount)->um_devvp; 128 for (bp = NULL, ++xap; --num; ++xap) { 129 /* 130 * Exit the loop if there is no disk address assigned yet and 131 * the indirect block isn't in the cache, or if we were 132 * looking for an indirect block and we've found it. 133 */ 134 135 metalbn = xap->in_lbn; 136 if (daddr == 0 && !incore(vp, metalbn) || metalbn == bn) 137 break; 138 /* 139 * If we get here, we've either got the block in the cache 140 * or we have a disk address for it, go fetch it. 141 */ 142 if (bp) 143 brelse(bp); 144 145 xap->in_exists = 1; 146 bp = getblk(vp, metalbn, mp->mnt_stat.f_iosize, 0, 0); 147 if (bp->b_flags & (B_DONE | B_DELWRI)) { 148 trace(TR_BREADHIT, pack(vp, size), metalbn); 149 } 150 #ifdef DIAGNOSTIC 151 else if (!daddr) 152 panic("ufs_bmaparry: indirect block not in cache"); 153 #endif 154 else { 155 trace(TR_BREADMISS, pack(vp, size), metalbn); 156 bp->b_blkno = blkptrtodb(ump, daddr); 157 bp->b_flags |= B_READ; 158 VOP_STRATEGY(bp); 159 curproc->p_stats->p_ru.ru_inblock++; /* XXX */ 160 if (error = biowait(bp)) { 161 brelse(bp); 162 return (error); 163 } 164 } 165 166 daddr = ((daddr_t *)bp->b_data)[xap->in_off]; 167 if (num == 1 && daddr && runp) 168 for (bn = xap->in_off + 1; 169 bn < MNINDIR(ump) && *runp < maxrun && 170 is_sequential(ump, ((daddr_t *)bp->b_data)[bn - 1], 171 ((daddr_t *)bp->b_data)[bn]); 172 ++bn, ++*runp); 173 } 174 if (bp) 175 brelse(bp); 176 177 daddr = blkptrtodb(ump, daddr); 178 *bnp = daddr == 0 ? -1 : daddr; 179 return (0); 180 } 181 182 /* 183 * Create an array of logical block number/offset pairs which represent the 184 * path of indirect blocks required to access a data block. The first "pair" 185 * contains the logical block number of the appropriate single, double or 186 * triple indirect block and the offset into the inode indirect block array. 187 * Note, the logical block number of the inode single/double/triple indirect 188 * block appears twice in the array, once with the offset into the i_ib and 189 * once with the offset into the page itself. 190 */ 191 int 192 ufs_getlbns(vp, bn, ap, nump) 193 struct vnode *vp; 194 register daddr_t bn; 195 struct indir *ap; 196 int *nump; 197 { 198 long metalbn, realbn; 199 struct ufsmount *ump; 200 int blockcnt, i, numlevels, off; 201 202 ump = VFSTOUFS(vp->v_mount); 203 if (nump) 204 *nump = 0; 205 numlevels = 0; 206 realbn = bn; 207 if ((long)bn < 0) 208 bn = -(long)bn; 209 210 /* The first NDADDR blocks are direct blocks. */ 211 if (bn < NDADDR) 212 return (0); 213 214 /* 215 * Determine the number of levels of indirection. After this loop 216 * is done, blockcnt indicates the number of data blocks possible 217 * at the given level of indirection, and NIADDR - i is the number 218 * of levels of indirection needed to locate the requested block. 219 */ 220 for (blockcnt = 1, i = NIADDR, bn -= NDADDR;; i--, bn -= blockcnt) { 221 if (i == 0) 222 return (EFBIG); 223 blockcnt *= MNINDIR(ump); 224 if (bn < blockcnt) 225 break; 226 } 227 228 /* Calculate the address of the first meta-block. */ 229 if (realbn >= 0) 230 metalbn = -(realbn - bn + NIADDR - i); 231 else 232 metalbn = -(-realbn - bn + NIADDR - i); 233 234 /* 235 * At each iteration, off is the offset into the bap array which is 236 * an array of disk addresses at the current level of indirection. 237 * The logical block number and the offset in that block are stored 238 * into the argument array. 239 */ 240 ap->in_lbn = metalbn; 241 ap->in_off = off = NIADDR - i; 242 ap->in_exists = 0; 243 ap++; 244 for (++numlevels; i <= NIADDR; i++) { 245 /* If searching for a meta-data block, quit when found. */ 246 if (metalbn == realbn) 247 break; 248 249 blockcnt /= MNINDIR(ump); 250 off = (bn / blockcnt) % MNINDIR(ump); 251 252 ++numlevels; 253 ap->in_lbn = metalbn; 254 ap->in_off = off; 255 ap->in_exists = 0; 256 ++ap; 257 258 metalbn -= -1 + off * blockcnt; 259 } 260 if (nump) 261 *nump = numlevels; 262 return (0); 263 } 264