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