1 /* $NetBSD: ffs_balloc.c,v 1.13 2004/06/20 22:20:18 jmc Exp $ */
2 /* From NetBSD: ffs_balloc.c,v 1.25 2001/08/08 08:36:36 lukem Exp */
3
4 /*
5 * Copyright (c) 1982, 1986, 1989, 1993
6 * The Regents of the University of California. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 * @(#)ffs_balloc.c 8.8 (Berkeley) 6/16/95
33 */
34
35 #include <sys/cdefs.h>
36 __FBSDID("$FreeBSD$");
37
38 #include <sys/param.h>
39 #include <sys/time.h>
40
41 #include <assert.h>
42 #include <errno.h>
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <string.h>
46
47 #include "makefs.h"
48
49 #include <ufs/ufs/dinode.h>
50 #include <ufs/ffs/fs.h>
51
52 #include "ffs/ufs_bswap.h"
53 #include "ffs/buf.h"
54 #include "ffs/ufs_inode.h"
55 #include "ffs/ffs_extern.h"
56
57 static int ffs_balloc_ufs1(struct inode *, off_t, int, struct buf **);
58 static int ffs_balloc_ufs2(struct inode *, off_t, int, struct buf **);
59
60 /*
61 * Balloc defines the structure of file system storage
62 * by allocating the physical blocks on a device given
63 * the inode and the logical block number in a file.
64 *
65 * Assume: flags == B_SYNC | B_CLRBUF
66 */
67
68 int
ffs_balloc(struct inode * ip,off_t offset,int bufsize,struct buf ** bpp)69 ffs_balloc(struct inode *ip, off_t offset, int bufsize, struct buf **bpp)
70 {
71 if (ip->i_fs->fs_magic == FS_UFS2_MAGIC)
72 return ffs_balloc_ufs2(ip, offset, bufsize, bpp);
73 else
74 return ffs_balloc_ufs1(ip, offset, bufsize, bpp);
75 }
76
77 static int
ffs_balloc_ufs1(struct inode * ip,off_t offset,int bufsize,struct buf ** bpp)78 ffs_balloc_ufs1(struct inode *ip, off_t offset, int bufsize, struct buf **bpp)
79 {
80 daddr_t lbn, lastlbn;
81 int size;
82 int32_t nb;
83 struct buf *bp, *nbp;
84 struct fs *fs = ip->i_fs;
85 struct indir indirs[NIADDR + 2];
86 daddr_t newb, pref;
87 int32_t *bap;
88 int osize, nsize, num, i, error;
89 int32_t *allocblk, allociblk[NIADDR + 1];
90 int32_t *allocib;
91 const int needswap = UFS_FSNEEDSWAP(fs);
92 struct vnode vp = { ip->i_fd, ip->i_fs, NULL, 0 };
93
94 lbn = lblkno(fs, offset);
95 size = blkoff(fs, offset) + bufsize;
96 if (bpp != NULL) {
97 *bpp = NULL;
98 }
99
100 assert(size <= fs->fs_bsize);
101 if (lbn < 0)
102 return (EFBIG);
103
104 /*
105 * If the next write will extend the file into a new block,
106 * and the file is currently composed of a fragment
107 * this fragment has to be extended to be a full block.
108 */
109
110 lastlbn = lblkno(fs, ip->i_ffs1_size);
111 if (lastlbn < NDADDR && lastlbn < lbn) {
112 nb = lastlbn;
113 osize = blksize(fs, ip, nb);
114 if (osize < fs->fs_bsize && osize > 0) {
115 warnx("need to ffs_realloccg; not supported!");
116 abort();
117 }
118 }
119
120 /*
121 * The first NDADDR blocks are direct blocks
122 */
123
124 if (lbn < NDADDR) {
125 nb = ufs_rw32(ip->i_ffs1_db[lbn], needswap);
126 if (nb != 0 && ip->i_ffs1_size >= lblktosize(fs, lbn + 1)) {
127
128 /*
129 * The block is an already-allocated direct block
130 * and the file already extends past this block,
131 * thus this must be a whole block.
132 * Just read the block (if requested).
133 */
134
135 if (bpp != NULL) {
136 error = bread(&vp, lbn, fs->fs_bsize, NULL,
137 bpp);
138 if (error) {
139 brelse(*bpp, 0);
140 return (error);
141 }
142 }
143 return (0);
144 }
145 if (nb != 0) {
146
147 /*
148 * Consider need to reallocate a fragment.
149 */
150
151 osize = fragroundup(fs, blkoff(fs, ip->i_ffs1_size));
152 nsize = fragroundup(fs, size);
153 if (nsize <= osize) {
154
155 /*
156 * The existing block is already
157 * at least as big as we want.
158 * Just read the block (if requested).
159 */
160
161 if (bpp != NULL) {
162 error = bread(&vp, lbn, osize, NULL,
163 bpp);
164 if (error) {
165 brelse(*bpp, 0);
166 return (error);
167 }
168 }
169 return 0;
170 } else {
171 warnx("need to ffs_realloccg; not supported!");
172 abort();
173 }
174 } else {
175
176 /*
177 * the block was not previously allocated,
178 * allocate a new block or fragment.
179 */
180
181 if (ip->i_ffs1_size < lblktosize(fs, lbn + 1))
182 nsize = fragroundup(fs, size);
183 else
184 nsize = fs->fs_bsize;
185 error = ffs_alloc(ip, lbn,
186 ffs_blkpref_ufs1(ip, lbn, (int)lbn,
187 &ip->i_ffs1_db[0]),
188 nsize, &newb);
189 if (error)
190 return (error);
191 if (bpp != NULL) {
192 bp = getblk(&vp, lbn, nsize, 0, 0, 0);
193 bp->b_blkno = fsbtodb(fs, newb);
194 clrbuf(bp);
195 *bpp = bp;
196 }
197 }
198 ip->i_ffs1_db[lbn] = ufs_rw32((int32_t)newb, needswap);
199 return (0);
200 }
201
202 /*
203 * Determine the number of levels of indirection.
204 */
205
206 pref = 0;
207 if ((error = ufs_getlbns(ip, lbn, indirs, &num)) != 0)
208 return (error);
209
210 if (num < 1) {
211 warnx("ffs_balloc: ufs_getlbns returned indirect block");
212 abort();
213 }
214
215 /*
216 * Fetch the first indirect block allocating if necessary.
217 */
218
219 --num;
220 nb = ufs_rw32(ip->i_ffs1_ib[indirs[0].in_off], needswap);
221 allocib = NULL;
222 allocblk = allociblk;
223 if (nb == 0) {
224 pref = ffs_blkpref_ufs1(ip, lbn, 0, (int32_t *)0);
225 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
226 if (error)
227 return error;
228 nb = newb;
229 *allocblk++ = nb;
230 bp = getblk(&vp, indirs[1].in_lbn, fs->fs_bsize, 0, 0, 0);
231 bp->b_blkno = fsbtodb(fs, nb);
232 clrbuf(bp);
233 /*
234 * Write synchronously so that indirect blocks
235 * never point at garbage.
236 */
237 if ((error = bwrite(bp)) != 0)
238 return error;
239 allocib = &ip->i_ffs1_ib[indirs[0].in_off];
240 *allocib = ufs_rw32((int32_t)nb, needswap);
241 }
242
243 /*
244 * Fetch through the indirect blocks, allocating as necessary.
245 */
246
247 for (i = 1;;) {
248 error = bread(&vp, indirs[i].in_lbn, fs->fs_bsize, NULL, &bp);
249 if (error) {
250 brelse(bp, 0);
251 return error;
252 }
253 bap = (int32_t *)bp->b_data;
254 nb = ufs_rw32(bap[indirs[i].in_off], needswap);
255 if (i == num)
256 break;
257 i++;
258 if (nb != 0) {
259 brelse(bp, 0);
260 continue;
261 }
262 if (pref == 0)
263 pref = ffs_blkpref_ufs1(ip, lbn, 0, (int32_t *)0);
264 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
265 if (error) {
266 brelse(bp, 0);
267 return error;
268 }
269 nb = newb;
270 *allocblk++ = nb;
271 nbp = getblk(&vp, indirs[i].in_lbn, fs->fs_bsize, 0, 0, 0);
272 nbp->b_blkno = fsbtodb(fs, nb);
273 clrbuf(nbp);
274 /*
275 * Write synchronously so that indirect blocks
276 * never point at garbage.
277 */
278
279 if ((error = bwrite(nbp)) != 0) {
280 brelse(bp, 0);
281 return error;
282 }
283 bap[indirs[i - 1].in_off] = ufs_rw32(nb, needswap);
284
285 bwrite(bp);
286 }
287
288 /*
289 * Get the data block, allocating if necessary.
290 */
291
292 if (nb == 0) {
293 pref = ffs_blkpref_ufs1(ip, lbn, indirs[num].in_off, &bap[0]);
294 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
295 if (error) {
296 brelse(bp, 0);
297 return error;
298 }
299 nb = newb;
300 *allocblk++ = nb;
301 if (bpp != NULL) {
302 nbp = getblk(&vp, lbn, fs->fs_bsize, 0, 0, 0);
303 nbp->b_blkno = fsbtodb(fs, nb);
304 clrbuf(nbp);
305 *bpp = nbp;
306 }
307 bap[indirs[num].in_off] = ufs_rw32(nb, needswap);
308
309 /*
310 * If required, write synchronously, otherwise use
311 * delayed write.
312 */
313 bwrite(bp);
314 return (0);
315 }
316 brelse(bp, 0);
317 if (bpp != NULL) {
318 error = bread(&vp, lbn, (int)fs->fs_bsize, NULL, &nbp);
319 if (error) {
320 brelse(nbp, 0);
321 return error;
322 }
323 *bpp = nbp;
324 }
325 return (0);
326 }
327
328 static int
ffs_balloc_ufs2(struct inode * ip,off_t offset,int bufsize,struct buf ** bpp)329 ffs_balloc_ufs2(struct inode *ip, off_t offset, int bufsize, struct buf **bpp)
330 {
331 daddr_t lbn, lastlbn;
332 int size;
333 struct buf *bp, *nbp;
334 struct fs *fs = ip->i_fs;
335 struct indir indirs[NIADDR + 2];
336 daddr_t newb, pref, nb;
337 int64_t *bap;
338 int osize, nsize, num, i, error;
339 int64_t *allocblk, allociblk[NIADDR + 1];
340 int64_t *allocib;
341 const int needswap = UFS_FSNEEDSWAP(fs);
342 struct vnode vp = { ip->i_fd, ip->i_fs, NULL, 0 };
343
344 lbn = lblkno(fs, offset);
345 size = blkoff(fs, offset) + bufsize;
346 if (bpp != NULL) {
347 *bpp = NULL;
348 }
349
350 assert(size <= fs->fs_bsize);
351 if (lbn < 0)
352 return (EFBIG);
353
354 /*
355 * If the next write will extend the file into a new block,
356 * and the file is currently composed of a fragment
357 * this fragment has to be extended to be a full block.
358 */
359
360 lastlbn = lblkno(fs, ip->i_ffs2_size);
361 if (lastlbn < NDADDR && lastlbn < lbn) {
362 nb = lastlbn;
363 osize = blksize(fs, ip, nb);
364 if (osize < fs->fs_bsize && osize > 0) {
365 warnx("need to ffs_realloccg; not supported!");
366 abort();
367 }
368 }
369
370 /*
371 * The first NDADDR blocks are direct blocks
372 */
373
374 if (lbn < NDADDR) {
375 nb = ufs_rw64(ip->i_ffs2_db[lbn], needswap);
376 if (nb != 0 && ip->i_ffs2_size >= lblktosize(fs, lbn + 1)) {
377
378 /*
379 * The block is an already-allocated direct block
380 * and the file already extends past this block,
381 * thus this must be a whole block.
382 * Just read the block (if requested).
383 */
384
385 if (bpp != NULL) {
386 error = bread(&vp, lbn, fs->fs_bsize, NULL,
387 bpp);
388 if (error) {
389 brelse(*bpp, 0);
390 return (error);
391 }
392 }
393 return (0);
394 }
395 if (nb != 0) {
396
397 /*
398 * Consider need to reallocate a fragment.
399 */
400
401 osize = fragroundup(fs, blkoff(fs, ip->i_ffs2_size));
402 nsize = fragroundup(fs, size);
403 if (nsize <= osize) {
404
405 /*
406 * The existing block is already
407 * at least as big as we want.
408 * Just read the block (if requested).
409 */
410
411 if (bpp != NULL) {
412 error = bread(&vp, lbn, osize, NULL,
413 bpp);
414 if (error) {
415 brelse(*bpp, 0);
416 return (error);
417 }
418 }
419 return 0;
420 } else {
421 warnx("need to ffs_realloccg; not supported!");
422 abort();
423 }
424 } else {
425
426 /*
427 * the block was not previously allocated,
428 * allocate a new block or fragment.
429 */
430
431 if (ip->i_ffs2_size < lblktosize(fs, lbn + 1))
432 nsize = fragroundup(fs, size);
433 else
434 nsize = fs->fs_bsize;
435 error = ffs_alloc(ip, lbn,
436 ffs_blkpref_ufs2(ip, lbn, (int)lbn,
437 &ip->i_ffs2_db[0]),
438 nsize, &newb);
439 if (error)
440 return (error);
441 if (bpp != NULL) {
442 bp = getblk(&vp, lbn, nsize, 0, 0, 0);
443 bp->b_blkno = fsbtodb(fs, newb);
444 clrbuf(bp);
445 *bpp = bp;
446 }
447 }
448 ip->i_ffs2_db[lbn] = ufs_rw64(newb, needswap);
449 return (0);
450 }
451
452 /*
453 * Determine the number of levels of indirection.
454 */
455
456 pref = 0;
457 if ((error = ufs_getlbns(ip, lbn, indirs, &num)) != 0)
458 return (error);
459
460 if (num < 1) {
461 warnx("ffs_balloc: ufs_getlbns returned indirect block");
462 abort();
463 }
464
465 /*
466 * Fetch the first indirect block allocating if necessary.
467 */
468
469 --num;
470 nb = ufs_rw64(ip->i_ffs2_ib[indirs[0].in_off], needswap);
471 allocib = NULL;
472 allocblk = allociblk;
473 if (nb == 0) {
474 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0);
475 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
476 if (error)
477 return error;
478 nb = newb;
479 *allocblk++ = nb;
480 bp = getblk(&vp, indirs[1].in_lbn, fs->fs_bsize, 0, 0, 0);
481 bp->b_blkno = fsbtodb(fs, nb);
482 clrbuf(bp);
483 /*
484 * Write synchronously so that indirect blocks
485 * never point at garbage.
486 */
487 if ((error = bwrite(bp)) != 0)
488 return error;
489 allocib = &ip->i_ffs2_ib[indirs[0].in_off];
490 *allocib = ufs_rw64(nb, needswap);
491 }
492
493 /*
494 * Fetch through the indirect blocks, allocating as necessary.
495 */
496
497 for (i = 1;;) {
498 error = bread(&vp, indirs[i].in_lbn, fs->fs_bsize, NULL, &bp);
499 if (error) {
500 brelse(bp, 0);
501 return error;
502 }
503 bap = (int64_t *)bp->b_data;
504 nb = ufs_rw64(bap[indirs[i].in_off], needswap);
505 if (i == num)
506 break;
507 i++;
508 if (nb != 0) {
509 brelse(bp, 0);
510 continue;
511 }
512 if (pref == 0)
513 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0);
514 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
515 if (error) {
516 brelse(bp, 0);
517 return error;
518 }
519 nb = newb;
520 *allocblk++ = nb;
521 nbp = getblk(&vp, indirs[i].in_lbn, fs->fs_bsize, 0, 0, 0);
522 nbp->b_blkno = fsbtodb(fs, nb);
523 clrbuf(nbp);
524 /*
525 * Write synchronously so that indirect blocks
526 * never point at garbage.
527 */
528
529 if ((error = bwrite(nbp)) != 0) {
530 brelse(bp, 0);
531 return error;
532 }
533 bap[indirs[i - 1].in_off] = ufs_rw64(nb, needswap);
534
535 bwrite(bp);
536 }
537
538 /*
539 * Get the data block, allocating if necessary.
540 */
541
542 if (nb == 0) {
543 pref = ffs_blkpref_ufs2(ip, lbn, indirs[num].in_off, &bap[0]);
544 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
545 if (error) {
546 brelse(bp, 0);
547 return error;
548 }
549 nb = newb;
550 *allocblk++ = nb;
551 if (bpp != NULL) {
552 nbp = getblk(&vp, lbn, fs->fs_bsize, 0, 0, 0);
553 nbp->b_blkno = fsbtodb(fs, nb);
554 clrbuf(nbp);
555 *bpp = nbp;
556 }
557 bap[indirs[num].in_off] = ufs_rw64(nb, needswap);
558
559 /*
560 * If required, write synchronously, otherwise use
561 * delayed write.
562 */
563 bwrite(bp);
564 return (0);
565 }
566 brelse(bp, 0);
567 if (bpp != NULL) {
568 error = bread(&vp, lbn, (int)fs->fs_bsize, NULL, &nbp);
569 if (error) {
570 brelse(nbp, 0);
571 return error;
572 }
573 *bpp = nbp;
574 }
575 return (0);
576 }
577