1 /* 2 * Copyright (c) 1989, 1991 Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 * 7 * @(#)lfs_balloc.c 7.23 (Berkeley) 12/06/91 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/specdev.h> 17 #include <sys/trace.h> 18 19 #include <ufs/ufs/quota.h> 20 #include <ufs/ufs/inode.h> 21 #include <ufs/ufs/ufsmount.h> 22 23 #include <ufs/lfs/lfs.h> 24 #include <ufs/lfs/lfs_extern.h> 25 26 static int lfs_getlbns __P((struct vnode *, daddr_t, INDIR *, int *)); 27 28 /* 29 * Bmap converts a the logical block number of a file to its physical block 30 * number on the disk. The conversion is done by using the logical block 31 * number to index into the array of block pointers described by the dinode. 32 */ 33 int 34 lfs_bmap(vp, bn, vpp, bnp) 35 struct vnode *vp; 36 register daddr_t bn; 37 struct vnode **vpp; 38 daddr_t *bnp; 39 { 40 #ifdef VERBOSE 41 printf("lfs_bmap\n"); 42 #endif 43 /* 44 * Check for underlying vnode requests and ensure that logical 45 * to physical mapping is requested. 46 */ 47 if (vpp != NULL) 48 *vpp = VTOI(vp)->i_devvp; 49 if (bnp == NULL) 50 return (0); 51 52 return (lfs_bmaparray(vp, bn, bnp, NULL, NULL)); 53 } 54 55 /* 56 * LFS has a different version of bmap from FFS because of a naming conflict. 57 * In FFS, meta blocks are given real disk addresses at allocation time, and 58 * are linked into the device vnode, using a logical block number which is 59 * the same as the physical block number. This can't be done by LFS because 60 * blocks aren't given disk addresses until they're written, so there's no 61 * way to distinguish the meta-data blocks for one file from any other file. 62 * This means that meta-data blocks have to be on the vnode for the file so 63 * they can be found, and have to have "names" different from the standard 64 * data blocks. To do this, we divide the name space into positive and 65 * negative block numbers, and give the meta-data blocks negative logical 66 * numbers. Indirect blocks are addressed by the negative address of the 67 * first data block to which they point. Double indirect blocks are addressed 68 * by one less than the address of the first indirect block to which they 69 * point. Triple indirect blocks are addressed by one less than the address 70 * of the first double indirect block to which they point. 71 */ 72 int 73 lfs_bmaparray(vp, bn, bnp, ap, nump) 74 struct vnode *vp; 75 register daddr_t bn; 76 daddr_t *bnp; 77 INDIR *ap; 78 int *nump; 79 { 80 register struct inode *ip; 81 struct buf *bp; 82 struct lfs *fs; 83 struct vnode *devvp; 84 INDIR a[NIADDR], *xap; 85 daddr_t *bap, daddr; 86 long metalbn; 87 int error, num, off; 88 89 90 ip = VTOI(vp); 91 #ifdef VERBOSE 92 printf("lfs_bmap: block number %d, inode %d\n", bn, ip->i_number); 93 #endif 94 #ifdef DIAGNOSTIC 95 if (ap != NULL && nump == NULL || ap == NULL && nump != NULL) 96 panic("lfs_bmaparray: invalid arguments"); 97 #endif 98 99 xap = ap == NULL ? a : ap; 100 if (error = lfs_getlbns(vp, bn, xap, nump)) 101 return (error); 102 103 num = *nump; 104 fs = ip->i_lfs; 105 if (num == 0) { 106 *bnp = ip->i_db[bn]; 107 if (*bnp == 0) 108 *bnp = UNASSIGNED; 109 return (0); 110 } 111 112 /* Fetch through the indirect blocks. */ 113 bp = NULL; 114 devvp = VFSTOUFS(vp->v_mount)->um_devvp; 115 for (bap = ip->i_ib; num--; off = xap->in_off, ++xap) { 116 off = xap->in_off; 117 metalbn = xap->in_lbn; 118 119 /* 120 * In LFS, it's possible to have a block appended to a file 121 * for which the meta-blocks have not yet been allocated. 122 * This is a win if the file never gets written or if the 123 * file's growing. 124 */ 125 if ((daddr = bap[off]) == 0) { 126 daddr = UNASSIGNED; 127 break; 128 } 129 130 /* If searching for a meta-data block, quit when found. */ 131 if (metalbn == bn) 132 break; 133 134 /* 135 * Read in the appropriate indirect block. LFS can't do a 136 * bread because bread knows that FFS will hand it the device 137 * vnode, not the file vnode, so the b_dev and b_blkno would 138 * be wrong. 139 * 140 * XXX 141 * This REALLY needs to be fixed, at the very least it needs 142 * to be rethought when the buffer cache goes away. When it's 143 * fixed, change lfs_bmaparray and lfs_getlbns to take an ip, 144 * not a vp. 145 */ 146 if (bp) 147 brelse(bp); 148 bp = getblk(vp, metalbn, fs->lfs_bsize); 149 if (bp->b_flags & (B_DONE | B_DELWRI)) { 150 trace(TR_BREADHIT, pack(vp, size), metalbn); 151 } else { 152 trace(TR_BREADMISS, pack(vp, size), metalbn); 153 bp->b_blkno = daddr; 154 bp->b_flags |= B_READ; 155 bp->b_dev = devvp->v_rdev; 156 (devvp->v_op->vop_strategy)(bp); 157 curproc->p_stats->p_ru.ru_inblock++; /* XXX */ 158 if (error = biowait(bp)) { 159 brelse(bp); 160 return (error); 161 } 162 } 163 bap = bp->b_un.b_daddr; 164 } 165 if (bp) 166 brelse(bp); 167 168 *bnp = daddr; 169 return (0); 170 } 171 172 /* 173 * Create an array of logical block number/offset pairs which represent the 174 * path of indirect blocks required to access a data block. The first "pair" 175 * contains the logical block number of the appropriate single, double or 176 * triple indirect block and the offset into the inode indirect block array. 177 * Note, the logical block number of the inode single/double/triple indirect 178 * block appears twice in the array, once with the offset into the i_ib and 179 * once with the offset into the page itself. 180 */ 181 int 182 lfs_getlbns(vp, bn, ap, nump) 183 struct vnode *vp; 184 register daddr_t bn; 185 INDIR *ap; 186 int *nump; 187 { 188 struct lfs *fs; 189 long metalbn, realbn; 190 int j, off, sh; 191 192 #ifdef VERBOSE 193 printf("lfs_getlbns: bn %d, inode %d\n", bn, VTOI(vp)->i_number); 194 #endif 195 *nump = 0; 196 realbn = bn; 197 if ((long)bn < 0) 198 bn = -(long)bn; 199 200 /* The first NDADDR blocks are direct blocks. */ 201 if (bn < NDADDR) 202 return(0); 203 204 /* 205 * Determine the number of levels of indirection. After this loop 206 * is done, sh indicates the number of data blocks possible at the 207 * given level of indirection, and NIADDR - j is the number of levels 208 * of indirection needed to locate the requested block. 209 */ 210 bn -= NDADDR; 211 fs = VTOI(vp)->i_lfs; 212 sh = 1; 213 for (j = NIADDR; j > 0; j--) { 214 sh *= NINDIR(fs); 215 if (bn < sh) 216 break; 217 bn -= sh; 218 } 219 if (j == 0) 220 return (EFBIG); 221 222 /* Calculate the address of the first meta-block. */ 223 if (realbn >= 0) 224 metalbn = -(realbn - bn + NIADDR - j); 225 else 226 metalbn = -(-realbn - bn + NIADDR - j); 227 228 /* 229 * At each iteration, off is the offset into the bap array which is 230 * an array of disk addresses at the current level of indirection. 231 * The logical block number and the offset in that block are stored 232 * into the argument array. 233 */ 234 ++*nump; 235 ap->in_lbn = metalbn; 236 ap->in_off = off = NIADDR - j; 237 ap++; 238 for (; j <= NIADDR; j++) { 239 /* If searching for a meta-data block, quit when found. */ 240 if (metalbn == realbn) 241 break; 242 243 sh /= NINDIR(fs); 244 off = (bn / sh) % NINDIR(fs); 245 246 ++*nump; 247 ap->in_lbn = metalbn; 248 ap->in_off = off; 249 ++ap; 250 251 metalbn -= -1 + off * sh; 252 } 253 return (0); 254 } 255