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: stable/10/usr.sbin/makefs/ffs/ffs_balloc.c 186334 2008-12-19 18:45:43Z sam $");
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
93 lbn = lblkno(fs, offset);
94 size = blkoff(fs, offset) + bufsize;
95 if (bpp != NULL) {
96 *bpp = NULL;
97 }
98
99 assert(size <= fs->fs_bsize);
100 if (lbn < 0)
101 return (EFBIG);
102
103 /*
104 * If the next write will extend the file into a new block,
105 * and the file is currently composed of a fragment
106 * this fragment has to be extended to be a full block.
107 */
108
109 lastlbn = lblkno(fs, ip->i_ffs1_size);
110 if (lastlbn < NDADDR && lastlbn < lbn) {
111 nb = lastlbn;
112 osize = blksize(fs, ip, nb);
113 if (osize < fs->fs_bsize && osize > 0) {
114 warnx("need to ffs_realloccg; not supported!");
115 abort();
116 }
117 }
118
119 /*
120 * The first NDADDR blocks are direct blocks
121 */
122
123 if (lbn < NDADDR) {
124 nb = ufs_rw32(ip->i_ffs1_db[lbn], needswap);
125 if (nb != 0 && ip->i_ffs1_size >= lblktosize(fs, lbn + 1)) {
126
127 /*
128 * The block is an already-allocated direct block
129 * and the file already extends past this block,
130 * thus this must be a whole block.
131 * Just read the block (if requested).
132 */
133
134 if (bpp != NULL) {
135 error = bread(ip->i_fd, ip->i_fs, lbn,
136 fs->fs_bsize, bpp);
137 if (error) {
138 brelse(*bpp);
139 return (error);
140 }
141 }
142 return (0);
143 }
144 if (nb != 0) {
145
146 /*
147 * Consider need to reallocate a fragment.
148 */
149
150 osize = fragroundup(fs, blkoff(fs, ip->i_ffs1_size));
151 nsize = fragroundup(fs, size);
152 if (nsize <= osize) {
153
154 /*
155 * The existing block is already
156 * at least as big as we want.
157 * Just read the block (if requested).
158 */
159
160 if (bpp != NULL) {
161 error = bread(ip->i_fd, ip->i_fs, lbn,
162 osize, bpp);
163 if (error) {
164 brelse(*bpp);
165 return (error);
166 }
167 }
168 return 0;
169 } else {
170 warnx("need to ffs_realloccg; not supported!");
171 abort();
172 }
173 } else {
174
175 /*
176 * the block was not previously allocated,
177 * allocate a new block or fragment.
178 */
179
180 if (ip->i_ffs1_size < lblktosize(fs, lbn + 1))
181 nsize = fragroundup(fs, size);
182 else
183 nsize = fs->fs_bsize;
184 error = ffs_alloc(ip, lbn,
185 ffs_blkpref_ufs1(ip, lbn, (int)lbn,
186 &ip->i_ffs1_db[0]),
187 nsize, &newb);
188 if (error)
189 return (error);
190 if (bpp != NULL) {
191 bp = getblk(ip->i_fd, ip->i_fs, lbn, nsize);
192 bp->b_blkno = fsbtodb(fs, newb);
193 clrbuf(bp);
194 *bpp = bp;
195 }
196 }
197 ip->i_ffs1_db[lbn] = ufs_rw32((int32_t)newb, needswap);
198 return (0);
199 }
200
201 /*
202 * Determine the number of levels of indirection.
203 */
204
205 pref = 0;
206 if ((error = ufs_getlbns(ip, lbn, indirs, &num)) != 0)
207 return (error);
208
209 if (num < 1) {
210 warnx("ffs_balloc: ufs_getlbns returned indirect block");
211 abort();
212 }
213
214 /*
215 * Fetch the first indirect block allocating if necessary.
216 */
217
218 --num;
219 nb = ufs_rw32(ip->i_ffs1_ib[indirs[0].in_off], needswap);
220 allocib = NULL;
221 allocblk = allociblk;
222 if (nb == 0) {
223 pref = ffs_blkpref_ufs1(ip, lbn, 0, (int32_t *)0);
224 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
225 if (error)
226 return error;
227 nb = newb;
228 *allocblk++ = nb;
229 bp = getblk(ip->i_fd, ip->i_fs, indirs[1].in_lbn, fs->fs_bsize);
230 bp->b_blkno = fsbtodb(fs, nb);
231 clrbuf(bp);
232 /*
233 * Write synchronously so that indirect blocks
234 * never point at garbage.
235 */
236 if ((error = bwrite(bp)) != 0)
237 return error;
238 allocib = &ip->i_ffs1_ib[indirs[0].in_off];
239 *allocib = ufs_rw32((int32_t)nb, needswap);
240 }
241
242 /*
243 * Fetch through the indirect blocks, allocating as necessary.
244 */
245
246 for (i = 1;;) {
247 error = bread(ip->i_fd, ip->i_fs, indirs[i].in_lbn,
248 fs->fs_bsize, &bp);
249 if (error) {
250 brelse(bp);
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);
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);
267 return error;
268 }
269 nb = newb;
270 *allocblk++ = nb;
271 nbp = getblk(ip->i_fd, ip->i_fs, indirs[i].in_lbn,
272 fs->fs_bsize);
273 nbp->b_blkno = fsbtodb(fs, nb);
274 clrbuf(nbp);
275 /*
276 * Write synchronously so that indirect blocks
277 * never point at garbage.
278 */
279
280 if ((error = bwrite(nbp)) != 0) {
281 brelse(bp);
282 return error;
283 }
284 bap[indirs[i - 1].in_off] = ufs_rw32(nb, needswap);
285
286 bwrite(bp);
287 }
288
289 /*
290 * Get the data block, allocating if necessary.
291 */
292
293 if (nb == 0) {
294 pref = ffs_blkpref_ufs1(ip, lbn, indirs[num].in_off, &bap[0]);
295 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
296 if (error) {
297 brelse(bp);
298 return error;
299 }
300 nb = newb;
301 *allocblk++ = nb;
302 if (bpp != NULL) {
303 nbp = getblk(ip->i_fd, ip->i_fs, lbn, fs->fs_bsize);
304 nbp->b_blkno = fsbtodb(fs, nb);
305 clrbuf(nbp);
306 *bpp = nbp;
307 }
308 bap[indirs[num].in_off] = ufs_rw32(nb, needswap);
309
310 /*
311 * If required, write synchronously, otherwise use
312 * delayed write.
313 */
314 bwrite(bp);
315 return (0);
316 }
317 brelse(bp);
318 if (bpp != NULL) {
319 error = bread(ip->i_fd, ip->i_fs, lbn, (int)fs->fs_bsize, &nbp);
320 if (error) {
321 brelse(nbp);
322 return error;
323 }
324 *bpp = nbp;
325 }
326 return (0);
327 }
328
329 static int
ffs_balloc_ufs2(struct inode * ip,off_t offset,int bufsize,struct buf ** bpp)330 ffs_balloc_ufs2(struct inode *ip, off_t offset, int bufsize, struct buf **bpp)
331 {
332 daddr_t lbn, lastlbn;
333 int size;
334 struct buf *bp, *nbp;
335 struct fs *fs = ip->i_fs;
336 struct indir indirs[NIADDR + 2];
337 daddr_t newb, pref, nb;
338 int64_t *bap;
339 int osize, nsize, num, i, error;
340 int64_t *allocblk, allociblk[NIADDR + 1];
341 int64_t *allocib;
342 const int needswap = UFS_FSNEEDSWAP(fs);
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(ip->i_fd, ip->i_fs, lbn,
387 fs->fs_bsize, bpp);
388 if (error) {
389 brelse(*bpp);
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(ip->i_fd, ip->i_fs, lbn,
413 osize, bpp);
414 if (error) {
415 brelse(*bpp);
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(ip->i_fd, ip->i_fs, lbn, nsize);
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(ip->i_fd, ip->i_fs, indirs[1].in_lbn, fs->fs_bsize);
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(ip->i_fd, ip->i_fs, indirs[i].in_lbn,
499 fs->fs_bsize, &bp);
500 if (error) {
501 brelse(bp);
502 return error;
503 }
504 bap = (int64_t *)bp->b_data;
505 nb = ufs_rw64(bap[indirs[i].in_off], needswap);
506 if (i == num)
507 break;
508 i++;
509 if (nb != 0) {
510 brelse(bp);
511 continue;
512 }
513 if (pref == 0)
514 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0);
515 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
516 if (error) {
517 brelse(bp);
518 return error;
519 }
520 nb = newb;
521 *allocblk++ = nb;
522 nbp = getblk(ip->i_fd, ip->i_fs, indirs[i].in_lbn,
523 fs->fs_bsize);
524 nbp->b_blkno = fsbtodb(fs, nb);
525 clrbuf(nbp);
526 /*
527 * Write synchronously so that indirect blocks
528 * never point at garbage.
529 */
530
531 if ((error = bwrite(nbp)) != 0) {
532 brelse(bp);
533 return error;
534 }
535 bap[indirs[i - 1].in_off] = ufs_rw64(nb, needswap);
536
537 bwrite(bp);
538 }
539
540 /*
541 * Get the data block, allocating if necessary.
542 */
543
544 if (nb == 0) {
545 pref = ffs_blkpref_ufs2(ip, lbn, indirs[num].in_off, &bap[0]);
546 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
547 if (error) {
548 brelse(bp);
549 return error;
550 }
551 nb = newb;
552 *allocblk++ = nb;
553 if (bpp != NULL) {
554 nbp = getblk(ip->i_fd, ip->i_fs, lbn, fs->fs_bsize);
555 nbp->b_blkno = fsbtodb(fs, nb);
556 clrbuf(nbp);
557 *bpp = nbp;
558 }
559 bap[indirs[num].in_off] = ufs_rw64(nb, needswap);
560
561 /*
562 * If required, write synchronously, otherwise use
563 * delayed write.
564 */
565 bwrite(bp);
566 return (0);
567 }
568 brelse(bp);
569 if (bpp != NULL) {
570 error = bread(ip->i_fd, ip->i_fs, lbn, (int)fs->fs_bsize, &nbp);
571 if (error) {
572 brelse(nbp);
573 return error;
574 }
575 *bpp = nbp;
576 }
577 return (0);
578 }
579