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.7 (Berkeley) 03/21/95 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 ufs_daddr_t a_bn; 40 struct vnode **a_vpp; 41 ufs_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 ufs_daddr_t bn; 76 ufs_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 ufs_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 = ((ufs_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, 176 ((ufs_daddr_t *)bp->b_data)[bn - 1], 177 ((ufs_daddr_t *)bp->b_data)[bn]); 178 ++bn, ++*runp); 179 } 180 if (bp) 181 brelse(bp); 182 183 daddr = blkptrtodb(ump, daddr); 184 *bnp = daddr == 0 ? -1 : daddr; 185 return (0); 186 } 187 188 /* 189 * Create an array of logical block number/offset pairs which represent the 190 * path of indirect blocks required to access a data block. The first "pair" 191 * contains the logical block number of the appropriate single, double or 192 * triple indirect block and the offset into the inode indirect block array. 193 * Note, the logical block number of the inode single/double/triple indirect 194 * block appears twice in the array, once with the offset into the i_ib and 195 * once with the offset into the page itself. 196 */ 197 int 198 ufs_getlbns(vp, bn, ap, nump) 199 struct vnode *vp; 200 ufs_daddr_t bn; 201 struct indir *ap; 202 int *nump; 203 { 204 long metalbn, realbn; 205 struct ufsmount *ump; 206 int blockcnt, i, numlevels, off; 207 208 ump = VFSTOUFS(vp->v_mount); 209 if (nump) 210 *nump = 0; 211 numlevels = 0; 212 realbn = bn; 213 if ((long)bn < 0) 214 bn = -(long)bn; 215 216 /* The first NDADDR blocks are direct blocks. */ 217 if (bn < NDADDR) 218 return (0); 219 220 /* 221 * Determine the number of levels of indirection. After this loop 222 * is done, blockcnt indicates the number of data blocks possible 223 * at the given level of indirection, and NIADDR - i is the number 224 * of levels of indirection needed to locate the requested block. 225 */ 226 for (blockcnt = 1, i = NIADDR, bn -= NDADDR;; i--, bn -= blockcnt) { 227 if (i == 0) 228 return (EFBIG); 229 blockcnt *= MNINDIR(ump); 230 if (bn < blockcnt) 231 break; 232 } 233 234 /* Calculate the address of the first meta-block. */ 235 if (realbn >= 0) 236 metalbn = -(realbn - bn + NIADDR - i); 237 else 238 metalbn = -(-realbn - bn + NIADDR - i); 239 240 /* 241 * At each iteration, off is the offset into the bap array which is 242 * an array of disk addresses at the current level of indirection. 243 * The logical block number and the offset in that block are stored 244 * into the argument array. 245 */ 246 ap->in_lbn = metalbn; 247 ap->in_off = off = NIADDR - i; 248 ap->in_exists = 0; 249 ap++; 250 for (++numlevels; i <= NIADDR; i++) { 251 /* If searching for a meta-data block, quit when found. */ 252 if (metalbn == realbn) 253 break; 254 255 blockcnt /= MNINDIR(ump); 256 off = (bn / blockcnt) % MNINDIR(ump); 257 258 ++numlevels; 259 ap->in_lbn = metalbn; 260 ap->in_off = off; 261 ap->in_exists = 0; 262 ++ap; 263 264 metalbn -= -1 + off * blockcnt; 265 } 266 if (nump) 267 *nump = numlevels; 268 return (0); 269 } 270