1 /* 2 * Copyright (c) 1982, 1986, 1989 Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms are permitted 6 * provided that the above copyright notice and this paragraph are 7 * duplicated in all such forms and that any documentation, 8 * advertising materials, and other materials related to such 9 * distribution and use acknowledge that the software was developed 10 * by the University of California, Berkeley. The name of the 11 * University may not be used to endorse or promote products derived 12 * from this software without specific prior written permission. 13 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 14 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 15 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 16 * 17 * @(#)lfs_balloc.c 7.5 (Berkeley) 08/26/89 18 */ 19 20 #include "param.h" 21 #include "systm.h" 22 #include "user.h" 23 #include "buf.h" 24 #include "proc.h" 25 #include "file.h" 26 #include "vnode.h" 27 #include "../ufs/inode.h" 28 #include "../ufs/fs.h" 29 30 /* 31 * Bmap defines the structure of file system storage 32 * by returning the physical block number on a device given the 33 * inode and the logical block number in a file. 34 * When convenient, it also leaves the physical 35 * block number of the next block of the file in rablock 36 * for use in read-ahead. 37 */ 38 bmap(ip, bn, bnp, rablockp, rasizep) 39 register struct inode *ip; 40 register daddr_t bn; 41 daddr_t *bnp; 42 daddr_t *rablockp; 43 int *rasizep; 44 { 45 register struct fs *fs; 46 register daddr_t nb; 47 struct buf *bp; 48 daddr_t *bap; 49 int i, j, sh; 50 int error; 51 52 if (bn < 0) 53 return (EFBIG); 54 fs = ip->i_fs; 55 56 /* 57 * The first NDADDR blocks are direct blocks 58 */ 59 if (bn < NDADDR) { 60 nb = ip->i_db[bn]; 61 if (nb == 0) { 62 *bnp = (daddr_t)-1; 63 return (0); 64 } 65 if (rablockp && rasizep) { 66 if (bn < NDADDR - 1) { 67 *rablockp = fsbtodb(fs, ip->i_db[bn + 1]); 68 *rasizep = blksize(fs, ip, bn + 1); 69 } else { 70 *rablockp = 0; 71 *rasizep = 0; 72 } 73 } 74 *bnp = fsbtodb(fs, nb); 75 return (0); 76 } 77 78 /* 79 * Determine how many levels of indirection. 80 */ 81 sh = 1; 82 bn -= NDADDR; 83 for (j = NIADDR; j > 0; j--) { 84 sh *= NINDIR(fs); 85 if (bn < sh) 86 break; 87 bn -= sh; 88 } 89 if (j == 0) 90 return (EFBIG); 91 92 /* 93 * fetch the first indirect block 94 */ 95 nb = ip->i_ib[NIADDR - j]; 96 if (nb == 0) { 97 *bnp = (daddr_t)-1; 98 return (0); 99 } 100 101 /* 102 * fetch through the indirect blocks 103 */ 104 for (; j <= NIADDR; j++) { 105 if (error = bread(ip->i_devvp, fsbtodb(fs, nb), 106 (int)fs->fs_bsize, NOCRED, &bp)) { 107 brelse(bp); 108 return (error); 109 } 110 bap = bp->b_un.b_daddr; 111 sh /= NINDIR(fs); 112 i = (bn / sh) % NINDIR(fs); 113 nb = bap[i]; 114 if (nb == 0) { 115 *bnp = (daddr_t)-1; 116 brelse(bp); 117 return (0); 118 } 119 if (j < NIADDR) 120 brelse(bp); 121 } 122 123 /* 124 * calculate read-ahead. 125 */ 126 if (rablockp && rasizep) { 127 if (i < NINDIR(fs) - 1) { 128 *rablockp = fsbtodb(fs, bap[i + 1]); 129 *rasizep = fs->fs_bsize; 130 } else { 131 *rablockp = 0; 132 *rasizep = 0; 133 } 134 } 135 *bnp = fsbtodb(fs, nb); 136 brelse(bp); 137 return (0); 138 } 139 140 /* 141 * Balloc defines the structure of file system storage 142 * by returning the physical block number on a device given the 143 * inode and the logical block number in a file. 144 * When unallocated entries are found, new physical blocks 145 * are allocated. 146 */ 147 balloc(ip, bn, size, bnp, flags) 148 register struct inode *ip; 149 register daddr_t bn; 150 int size; 151 daddr_t *bnp; 152 int flags; 153 { 154 register struct fs *fs; 155 register daddr_t nb; 156 struct buf *bp, *nbp; 157 int osize, nsize, i, j, sh, error; 158 daddr_t lbn, *bap, pref, blkpref(); 159 160 if (bn < 0) 161 return (EFBIG); 162 fs = ip->i_fs; 163 164 /* 165 * If the next write will extend the file into a new block, 166 * and the file is currently composed of a fragment 167 * this fragment has to be extended to be a full block. 168 */ 169 nb = lblkno(fs, ip->i_size); 170 if (nb < NDADDR && nb < bn) { 171 osize = blksize(fs, ip, nb); 172 if (osize < fs->fs_bsize && osize > 0) { 173 error = realloccg(ip, ip->i_db[nb], 174 blkpref(ip, nb, (int)nb, &ip->i_db[0]), 175 osize, (int)fs->fs_bsize, &bp); 176 if (error) { 177 *bnp = (daddr_t)-1; 178 return (error); 179 } 180 ip->i_size = (nb + 1) * fs->fs_bsize; 181 ip->i_db[nb] = dbtofsb(fs, bp->b_blkno); 182 ip->i_flag |= IUPD|ICHG; 183 bdwrite(bp); 184 } 185 } 186 /* 187 * The first NDADDR blocks are direct blocks 188 */ 189 if (bn < NDADDR) { 190 nb = ip->i_db[bn]; 191 if (nb == 0 || ip->i_size < (bn + 1) * fs->fs_bsize) { 192 if (nb != 0) { 193 /* consider need to reallocate a frag */ 194 osize = fragroundup(fs, blkoff(fs, ip->i_size)); 195 nsize = fragroundup(fs, size); 196 if (nsize <= osize) 197 goto gotit; 198 error = realloccg(ip, nb, 199 blkpref(ip, bn, (int)bn, &ip->i_db[0]), 200 osize, nsize, &bp); 201 } else { 202 if (ip->i_size < (bn + 1) * fs->fs_bsize) 203 nsize = fragroundup(fs, size); 204 else 205 nsize = fs->fs_bsize; 206 error = alloc(ip, 207 blkpref(ip, bn, (int)bn, &ip->i_db[0]), 208 nsize, &bp, flags); 209 } 210 if (error) { 211 *bnp = (daddr_t)-1; 212 return (error); 213 } 214 nb = dbtofsb(fs, bp->b_blkno); 215 if ((ip->i_mode & IFMT) == IFDIR) 216 /* 217 * Write directory blocks synchronously 218 * so they never appear with garbage in 219 * them on the disk. 220 * 221 * NB: Should free space and return error 222 * if bwrite returns an error. 223 */ 224 error = bwrite(bp); 225 else 226 bdwrite(bp); 227 ip->i_db[bn] = nb; 228 ip->i_flag |= IUPD|ICHG; 229 } 230 gotit: 231 *bnp = fsbtodb(fs, nb); 232 return (0); 233 } 234 235 /* 236 * Determine how many levels of indirection. 237 */ 238 pref = 0; 239 sh = 1; 240 lbn = bn; 241 bn -= NDADDR; 242 for (j = NIADDR; j > 0; j--) { 243 sh *= NINDIR(fs); 244 if (bn < sh) 245 break; 246 bn -= sh; 247 } 248 if (j == 0) 249 return (EFBIG); 250 251 /* 252 * fetch the first indirect block 253 */ 254 nb = ip->i_ib[NIADDR - j]; 255 if (nb == 0) { 256 pref = blkpref(ip, lbn, 0, (daddr_t *)0); 257 error = alloc(ip, pref, (int)fs->fs_bsize, &bp, B_CLRBUF); 258 if (error) { 259 *bnp = (daddr_t)-1; 260 return (error); 261 } 262 nb = dbtofsb(fs, bp->b_blkno); 263 /* 264 * Write synchronously so that indirect blocks 265 * never point at garbage. 266 * 267 * NB: Should free space and return error 268 * if bwrite returns an error. 269 */ 270 error = bwrite(bp); 271 ip->i_ib[NIADDR - j] = nb; 272 ip->i_flag |= IUPD|ICHG; 273 } 274 275 /* 276 * fetch through the indirect blocks 277 */ 278 for (; j <= NIADDR; j++) { 279 if (error = bread(ip->i_devvp, fsbtodb(fs, nb), 280 (int)fs->fs_bsize, NOCRED, &bp)) { 281 brelse(bp); 282 return (error); 283 } 284 bap = bp->b_un.b_daddr; 285 sh /= NINDIR(fs); 286 i = (bn / sh) % NINDIR(fs); 287 nb = bap[i]; 288 if (nb == 0) { 289 if (pref == 0) 290 if (j < NIADDR) 291 pref = blkpref(ip, lbn, 0, 292 (daddr_t *)0); 293 else 294 pref = blkpref(ip, lbn, i, &bap[0]); 295 error = alloc(ip, pref, (int)fs->fs_bsize, &nbp, 296 (j < NIADDR) ? B_CLRBUF : flags); 297 if (error) { 298 brelse(bp); 299 *bnp = (daddr_t)-1; 300 return (error); 301 } 302 nb = dbtofsb(fs, nbp->b_blkno); 303 if (j < NIADDR || (ip->i_mode & IFMT) == IFDIR) 304 /* 305 * Write synchronously so indirect blocks 306 * never point at garbage and blocks 307 * in directories never contain garbage. 308 * 309 * NB: Should free space and return error 310 * if bwrite returns an error. 311 */ 312 error = bwrite(nbp); 313 else 314 bdwrite(nbp); 315 bap[i] = nb; 316 bdwrite(bp); 317 } else 318 brelse(bp); 319 } 320 321 *bnp = fsbtodb(fs, nb); 322 return (0); 323 } 324