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.1 (Berkeley) 06/11/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 If MAXBSIZE is the largest transfer the disks can 98 * handle, we probably want maxrun to be 1 block less so 99 * that we don't create a block larger than the device 100 * 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 /* Fetch through the indirect blocks. */ 129 devvp = VFSTOUFS(vp->v_mount)->um_devvp; 130 131 for (bp = NULL, ++xap; --num; ++xap) { 132 /* 133 * Exit the loop if there is no disk address assigned yet and 134 * the indirect block isn't in the cache, or if we were 135 * looking for an indirect block and we've found it. 136 */ 137 138 metalbn = xap->in_lbn; 139 if (daddr == 0 && !incore(vp, metalbn) || metalbn == bn) 140 break; 141 /* 142 * If we get here, we've either got the block in the cache 143 * or we have a disk address for it, go fetch it. 144 */ 145 if (bp) 146 brelse(bp); 147 148 xap->in_exists = 1; 149 bp = getblk(vp, metalbn, mp->mnt_stat.f_iosize, 0, 0); 150 if (bp->b_flags & (B_DONE | B_DELWRI)) { 151 trace(TR_BREADHIT, pack(vp, size), metalbn); 152 } 153 #ifdef DIAGNOSTIC 154 else if (!daddr) 155 panic("ufs_bmaparry: indirect block not in cache"); 156 #endif 157 else { 158 trace(TR_BREADMISS, pack(vp, size), metalbn); 159 bp->b_blkno = blkptrtodb(ump, daddr); 160 bp->b_flags |= B_READ; 161 VOP_STRATEGY(bp); 162 curproc->p_stats->p_ru.ru_inblock++; /* XXX */ 163 if (error = biowait(bp)) { 164 brelse(bp); 165 return (error); 166 } 167 } 168 169 daddr = bp->b_un.b_daddr[xap->in_off]; 170 if (num == 1 && daddr && runp) 171 for (bn = xap->in_off + 1; 172 bn < MNINDIR(ump) && *runp < maxrun && 173 is_sequential(ump, bp->b_un.b_daddr[bn - 1], 174 bp->b_un.b_daddr[bn]); 175 ++bn, ++*runp); 176 } 177 if (bp) 178 brelse(bp); 179 180 daddr = blkptrtodb(ump, daddr); 181 *bnp = daddr == 0 ? -1 : daddr; 182 return (0); 183 } 184 185 /* 186 * Create an array of logical block number/offset pairs which represent the 187 * path of indirect blocks required to access a data block. The first "pair" 188 * contains the logical block number of the appropriate single, double or 189 * triple indirect block and the offset into the inode indirect block array. 190 * Note, the logical block number of the inode single/double/triple indirect 191 * block appears twice in the array, once with the offset into the i_ib and 192 * once with the offset into the page itself. 193 */ 194 int 195 ufs_getlbns(vp, bn, ap, nump) 196 struct vnode *vp; 197 register daddr_t bn; 198 struct indir *ap; 199 int *nump; 200 { 201 long metalbn, realbn; 202 struct ufsmount *ump; 203 int j, numlevels, off, sh; 204 205 ump = VFSTOUFS(vp->v_mount); 206 if (nump) 207 *nump = 0; 208 numlevels = 0; 209 realbn = bn; 210 if ((long)bn < 0) 211 bn = -(long)bn; 212 213 /* The first NDADDR blocks are direct blocks. */ 214 if (bn < NDADDR) 215 return (0); 216 217 /* 218 * Determine the number of levels of indirection. After this loop 219 * is done, sh indicates the number of data blocks possible at the 220 * given level of indirection, and NIADDR - j is the number of levels 221 * of indirection needed to locate the requested block. 222 */ 223 bn -= NDADDR; 224 sh = 1; 225 for (j = NIADDR; j > 0; j--) { 226 sh *= MNINDIR(ump); 227 if (bn < sh) 228 break; 229 bn -= sh; 230 } 231 if (j == 0) 232 return (EFBIG); 233 234 /* Calculate the address of the first meta-block. */ 235 if (realbn >= 0) 236 metalbn = -(realbn - bn + NIADDR - j); 237 else 238 metalbn = -(-realbn - bn + NIADDR - j); 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 ++numlevels; 247 ap->in_lbn = metalbn; 248 ap->in_off = off = NIADDR - j; 249 ap->in_exists = 0; 250 ap++; 251 for (; j <= NIADDR; j++) { 252 /* If searching for a meta-data block, quit when found. */ 253 if (metalbn == realbn) 254 break; 255 256 sh /= MNINDIR(ump); 257 off = (bn / sh) % MNINDIR(ump); 258 259 ++numlevels; 260 ap->in_lbn = metalbn; 261 ap->in_off = off; 262 ap->in_exists = 0; 263 ++ap; 264 265 metalbn -= -1 + off * sh; 266 } 267 if (nump) 268 *nump = numlevels; 269 return (0); 270 } 271