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