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