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 * @(#)ffs_balloc.c 7.3 (Berkeley) 05/09/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, &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 } 120 121 /* 122 * calculate read-ahead. 123 */ 124 if (rablockp && rasizep) { 125 if (i < NINDIR(fs) - 1) { 126 *rablockp = fsbtodb(fs, bap[i + 1]); 127 *rasizep = fs->fs_bsize; 128 } else { 129 *rablockp = 0; 130 *rasizep = 0; 131 } 132 } 133 *bnp = fsbtodb(fs, nb); 134 brelse(bp); 135 return (0); 136 } 137 138 /* 139 * Balloc defines the structure of file system storage 140 * by returning the physical block number on a device given the 141 * inode and the logical block number in a file. 142 * When unallocated entries are found, new physical blocks 143 * are allocated. 144 */ 145 balloc(ip, bn, size, bnp, flags) 146 register struct inode *ip; 147 register daddr_t bn; 148 int size; 149 daddr_t *bnp; 150 int flags; 151 { 152 register struct fs *fs; 153 register daddr_t nb; 154 struct buf *bp, *nbp; 155 int osize, nsize, i, j, sh, error; 156 daddr_t lbn, *bap, pref, blkpref(); 157 158 if (bn < 0) 159 return (EFBIG); 160 fs = ip->i_fs; 161 162 /* 163 * If the next write will extend the file into a new block, 164 * and the file is currently composed of a fragment 165 * this fragment has to be extended to be a full block. 166 */ 167 nb = lblkno(fs, ip->i_size); 168 if (nb < NDADDR && nb < bn) { 169 osize = blksize(fs, ip, nb); 170 if (osize < fs->fs_bsize && osize > 0) { 171 error = realloccg(ip, ip->i_db[nb], 172 blkpref(ip, nb, (int)nb, &ip->i_db[0]), 173 osize, (int)fs->fs_bsize, &bp); 174 if (error) { 175 *bnp = (daddr_t)-1; 176 return (error); 177 } 178 ip->i_size = (nb + 1) * fs->fs_bsize; 179 ip->i_db[nb] = dbtofsb(fs, bp->b_blkno); 180 ip->i_flag |= IUPD|ICHG; 181 bdwrite(bp); 182 } 183 } 184 /* 185 * The first NDADDR blocks are direct blocks 186 */ 187 if (bn < NDADDR) { 188 nb = ip->i_db[bn]; 189 if (nb == 0 || ip->i_size < (bn + 1) * fs->fs_bsize) { 190 if (nb != 0) { 191 /* consider need to reallocate a frag */ 192 osize = fragroundup(fs, blkoff(fs, ip->i_size)); 193 nsize = fragroundup(fs, size); 194 if (nsize <= osize) 195 goto gotit; 196 error = realloccg(ip, nb, 197 blkpref(ip, bn, (int)bn, &ip->i_db[0]), 198 osize, nsize, &bp); 199 } else { 200 if (ip->i_size < (bn + 1) * fs->fs_bsize) 201 nsize = fragroundup(fs, size); 202 else 203 nsize = fs->fs_bsize; 204 error = alloc(ip, 205 blkpref(ip, bn, (int)bn, &ip->i_db[0]), 206 nsize, &bp, flags); 207 } 208 if (error) { 209 *bnp = (daddr_t)-1; 210 return (error); 211 } 212 nb = dbtofsb(fs, bp->b_blkno); 213 if ((ip->i_mode & IFMT) == IFDIR) 214 /* 215 * Write directory blocks synchronously 216 * so they never appear with garbage in 217 * them on the disk. 218 * 219 * NB: Should free space and return error 220 * if bwrite returns an error. 221 */ 222 error = bwrite(bp); 223 else 224 bdwrite(bp); 225 ip->i_db[bn] = nb; 226 ip->i_flag |= IUPD|ICHG; 227 } 228 gotit: 229 *bnp = fsbtodb(fs, nb); 230 return (0); 231 } 232 233 /* 234 * Determine how many levels of indirection. 235 */ 236 pref = 0; 237 sh = 1; 238 lbn = bn; 239 bn -= NDADDR; 240 for (j = NIADDR; j > 0; j--) { 241 sh *= NINDIR(fs); 242 if (bn < sh) 243 break; 244 bn -= sh; 245 } 246 if (j == 0) 247 return (EFBIG); 248 249 /* 250 * fetch the first indirect block 251 */ 252 nb = ip->i_ib[NIADDR - j]; 253 if (nb == 0) { 254 pref = blkpref(ip, lbn, 0, (daddr_t *)0); 255 error = alloc(ip, pref, (int)fs->fs_bsize, &bp, B_CLRBUF); 256 if (error) { 257 *bnp = (daddr_t)-1; 258 return (error); 259 } 260 nb = dbtofsb(fs, bp->b_blkno); 261 /* 262 * Write synchronously so that indirect blocks 263 * never point at garbage. 264 * 265 * NB: Should free space and return error 266 * if bwrite returns an error. 267 */ 268 error = bwrite(bp); 269 ip->i_ib[NIADDR - j] = nb; 270 ip->i_flag |= IUPD|ICHG; 271 } 272 273 /* 274 * fetch through the indirect blocks 275 */ 276 for (; j <= NIADDR; j++) { 277 if (error = bread(ip->i_devvp, fsbtodb(fs, nb), 278 (int)fs->fs_bsize, &bp)) { 279 brelse(bp); 280 return (error); 281 } 282 bap = bp->b_un.b_daddr; 283 sh /= NINDIR(fs); 284 i = (bn / sh) % NINDIR(fs); 285 nb = bap[i]; 286 if (nb == 0) { 287 if (pref == 0) 288 if (j < NIADDR) 289 pref = blkpref(ip, lbn, 0, 290 (daddr_t *)0); 291 else 292 pref = blkpref(ip, lbn, i, &bap[0]); 293 error = alloc(ip, pref, (int)fs->fs_bsize, &nbp, 294 (j < NIADDR) ? B_CLRBUF : flags); 295 if (error) { 296 brelse(bp); 297 *bnp = (daddr_t)-1; 298 return (error); 299 } 300 nb = dbtofsb(fs, nbp->b_blkno); 301 if (j < NIADDR || (ip->i_mode & IFMT) == IFDIR) 302 /* 303 * Write synchronously so indirect blocks 304 * never point at garbage and blocks 305 * in directories never contain garbage. 306 * 307 * NB: Should free space and return error 308 * if bwrite returns an error. 309 */ 310 error = bwrite(nbp); 311 else 312 bdwrite(nbp); 313 bap[i] = nb; 314 bdwrite(bp); 315 } else 316 brelse(bp); 317 } 318 319 *bnp = fsbtodb(fs, nb); 320 return (0); 321 } 322