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 * $FreeBSD: head/usr.sbin/makefs/ffs/ffs_balloc.c 336736 2018-07-26 13:33:10Z emaste $
36 */
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 <vfs/ufs/dinode.h>
50 #include <vfs/ufs/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 m_buf **);
58 #ifndef __DragonFly__ /* XXX UFS2 */
59 static int ffs_balloc_ufs2(struct inode *, off_t, int, struct m_buf **);
60 #endif
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 m_buf ** bpp)71 ffs_balloc(struct inode *ip, off_t offset, int bufsize, struct m_buf **bpp)
72 {
73 #ifndef __DragonFly__ /* XXX UFS2 */
74 if (ip->i_fs->fs_magic == FS_UFS2_MAGIC)
75 return ffs_balloc_ufs2(ip, offset, bufsize, bpp);
76 else
77 #endif
78 return ffs_balloc_ufs1(ip, offset, bufsize, bpp);
79 }
80
81 static int
ffs_balloc_ufs1(struct inode * ip,off_t offset,int bufsize,struct m_buf ** bpp)82 ffs_balloc_ufs1(struct inode *ip, off_t offset, int bufsize, struct m_buf **bpp)
83 {
84 makefs_daddr_t lbn, lastlbn;
85 int size;
86 int32_t nb;
87 struct m_buf *bp, *nbp;
88 struct fs *fs = ip->i_fs;
89 struct indir indirs[UFS_NIADDR + 2];
90 makefs_daddr_t newb, pref;
91 int32_t *bap;
92 int osize, nsize, num, i, error;
93 int32_t *allocblk, allociblk[UFS_NIADDR + 1];
94 int32_t *allocib;
95 const int needswap = UFS_FSNEEDSWAP(fs);
96
97 lbn = lblkno(fs, offset);
98 size = blkoff(fs, offset) + bufsize;
99 if (bpp != NULL) {
100 *bpp = NULL;
101 }
102
103 assert(size <= fs->fs_bsize);
104 if (lbn < 0)
105 return (EFBIG);
106
107 /*
108 * If the next write will extend the file into a new block,
109 * and the file is currently composed of a fragment
110 * this fragment has to be extended to be a full block.
111 */
112
113 lastlbn = lblkno(fs, ip->i_ffs1_size);
114 if (lastlbn < UFS_NDADDR && lastlbn < lbn) {
115 nb = lastlbn;
116 osize = blksize(fs, ip, nb);
117 if (osize < fs->fs_bsize && osize > 0) {
118 warnx("need to ffs_realloccg; not supported!");
119 abort();
120 }
121 }
122
123 /*
124 * The first UFS_NDADDR blocks are direct blocks
125 */
126
127 if (lbn < UFS_NDADDR) {
128 nb = ufs_rw32(ip->i_ffs1_db[lbn], needswap);
129 if (nb != 0 && ip->i_ffs1_size >=
130 (uint64_t)lblktosize(fs, lbn + 1)) {
131
132 /*
133 * The block is an already-allocated direct block
134 * and the file already extends past this block,
135 * thus this must be a whole block.
136 * Just read the block (if requested).
137 */
138
139 if (bpp != NULL) {
140 error = bread(ip->i_devvp, lbn, fs->fs_bsize,
141 NULL, bpp);
142 if (error) {
143 brelse(*bpp);
144 return (error);
145 }
146 }
147 return (0);
148 }
149 if (nb != 0) {
150
151 /*
152 * Consider need to reallocate a fragment.
153 */
154
155 osize = fragroundup(fs, blkoff(fs, ip->i_ffs1_size));
156 nsize = fragroundup(fs, size);
157 if (nsize <= osize) {
158
159 /*
160 * The existing block is already
161 * at least as big as we want.
162 * Just read the block (if requested).
163 */
164
165 if (bpp != NULL) {
166 error = bread(ip->i_devvp, lbn, osize,
167 NULL, bpp);
168 if (error) {
169 brelse(*bpp);
170 return (error);
171 }
172 }
173 return 0;
174 } else {
175 warnx("need to ffs_realloccg; not supported!");
176 abort();
177 }
178 } else {
179
180 /*
181 * the block was not previously allocated,
182 * allocate a new block or fragment.
183 */
184
185 if (ip->i_ffs1_size < (uint64_t)lblktosize(fs, lbn + 1))
186 nsize = fragroundup(fs, size);
187 else
188 nsize = fs->fs_bsize;
189 error = ffs_alloc(ip, lbn,
190 ffs_blkpref_ufs1(ip, lbn, (int)lbn,
191 &ip->i_ffs1_db[0]),
192 nsize, &newb);
193 if (error)
194 return (error);
195 if (bpp != NULL) {
196 bp = getblk(ip->i_devvp, lbn, nsize, 0, 0, 0);
197 bp->b_blkno = fsbtodb(fs, newb);
198 clrbuf(bp);
199 *bpp = bp;
200 }
201 }
202 ip->i_ffs1_db[lbn] = ufs_rw32((int32_t)newb, needswap);
203 return (0);
204 }
205
206 /*
207 * Determine the number of levels of indirection.
208 */
209
210 pref = 0;
211 if ((error = ufs_getlbns(ip, lbn, indirs, &num)) != 0)
212 return (error);
213
214 if (num < 1) {
215 warnx("ffs_balloc: ufs_getlbns returned indirect block");
216 abort();
217 }
218
219 /*
220 * Fetch the first indirect block allocating if necessary.
221 */
222
223 --num;
224 nb = ufs_rw32(ip->i_ffs1_ib[indirs[0].in_off], needswap);
225 allocib = NULL;
226 allocblk = allociblk;
227 if (nb == 0) {
228 pref = ffs_blkpref_ufs1(ip, lbn, 0, (int32_t *)0);
229 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
230 if (error)
231 return error;
232 nb = newb;
233 *allocblk++ = nb;
234 bp = getblk(ip->i_devvp, indirs[1].in_lbn, fs->fs_bsize, 0, 0, 0);
235 bp->b_blkno = fsbtodb(fs, nb);
236 clrbuf(bp);
237 /*
238 * Write synchronously so that indirect blocks
239 * never point at garbage.
240 */
241 if ((error = bwrite(bp)) != 0)
242 return error;
243 allocib = &ip->i_ffs1_ib[indirs[0].in_off];
244 *allocib = ufs_rw32((int32_t)nb, needswap);
245 }
246
247 /*
248 * Fetch through the indirect blocks, allocating as necessary.
249 */
250
251 for (i = 1;;) {
252 error = bread(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize,
253 NULL, &bp);
254 if (error) {
255 brelse(bp);
256 return error;
257 }
258 bap = (int32_t *)bp->b_data;
259 nb = ufs_rw32(bap[indirs[i].in_off], needswap);
260 if (i == num)
261 break;
262 i++;
263 if (nb != 0) {
264 brelse(bp);
265 continue;
266 }
267 if (pref == 0)
268 pref = ffs_blkpref_ufs1(ip, lbn, 0, (int32_t *)0);
269 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
270 if (error) {
271 brelse(bp);
272 return error;
273 }
274 nb = newb;
275 *allocblk++ = nb;
276 nbp = getblk(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize, 0, 0, 0);
277 nbp->b_blkno = fsbtodb(fs, nb);
278 clrbuf(nbp);
279 /*
280 * Write synchronously so that indirect blocks
281 * never point at garbage.
282 */
283
284 if ((error = bwrite(nbp)) != 0) {
285 brelse(bp);
286 return error;
287 }
288 bap[indirs[i - 1].in_off] = ufs_rw32(nb, needswap);
289
290 bwrite(bp);
291 }
292
293 /*
294 * Get the data block, allocating if necessary.
295 */
296
297 if (nb == 0) {
298 pref = ffs_blkpref_ufs1(ip, lbn, indirs[num].in_off, &bap[0]);
299 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
300 if (error) {
301 brelse(bp);
302 return error;
303 }
304 nb = newb;
305 *allocblk++ = nb;
306 if (bpp != NULL) {
307 nbp = getblk(ip->i_devvp, lbn, fs->fs_bsize, 0, 0, 0);
308 nbp->b_blkno = fsbtodb(fs, nb);
309 clrbuf(nbp);
310 *bpp = nbp;
311 }
312 bap[indirs[num].in_off] = ufs_rw32(nb, needswap);
313
314 /*
315 * If required, write synchronously, otherwise use
316 * delayed write.
317 */
318 bwrite(bp);
319 return (0);
320 }
321 brelse(bp);
322 if (bpp != NULL) {
323 error = bread(ip->i_devvp, lbn, (int)fs->fs_bsize, NULL, &nbp);
324 if (error) {
325 brelse(nbp);
326 return error;
327 }
328 *bpp = nbp;
329 }
330 return (0);
331 }
332
333 #ifndef __DragonFly__ /* XXX UFS2 */
334 static int
ffs_balloc_ufs2(struct inode * ip,off_t offset,int bufsize,struct m_buf ** bpp)335 ffs_balloc_ufs2(struct inode *ip, off_t offset, int bufsize, struct m_buf **bpp)
336 {
337 daddr_t lbn, lastlbn;
338 int size;
339 struct m_buf *bp, *nbp;
340 struct fs *fs = ip->i_fs;
341 struct indir indirs[UFS_NIADDR + 2];
342 daddr_t newb, pref, nb;
343 int64_t *bap;
344 int osize, nsize, num, i, error;
345 int64_t *allocblk, allociblk[UFS_NIADDR + 1];
346 int64_t *allocib;
347 const int needswap = UFS_FSNEEDSWAP(fs);
348
349 lbn = lblkno(fs, offset);
350 size = blkoff(fs, offset) + bufsize;
351 if (bpp != NULL) {
352 *bpp = NULL;
353 }
354
355 assert(size <= fs->fs_bsize);
356 if (lbn < 0)
357 return (EFBIG);
358
359 /*
360 * If the next write will extend the file into a new block,
361 * and the file is currently composed of a fragment
362 * this fragment has to be extended to be a full block.
363 */
364
365 lastlbn = lblkno(fs, ip->i_ffs2_size);
366 if (lastlbn < UFS_NDADDR && lastlbn < lbn) {
367 nb = lastlbn;
368 osize = blksize(fs, ip, nb);
369 if (osize < fs->fs_bsize && osize > 0) {
370 warnx("need to ffs_realloccg; not supported!");
371 abort();
372 }
373 }
374
375 /*
376 * The first UFS_NDADDR blocks are direct blocks
377 */
378
379 if (lbn < UFS_NDADDR) {
380 nb = ufs_rw64(ip->i_ffs2_db[lbn], needswap);
381 if (nb != 0 && ip->i_ffs2_size >=
382 (uint64_t)lblktosize(fs, lbn + 1)) {
383
384 /*
385 * The block is an already-allocated direct block
386 * and the file already extends past this block,
387 * thus this must be a whole block.
388 * Just read the block (if requested).
389 */
390
391 if (bpp != NULL) {
392 error = bread(ip->i_devvp, lbn, fs->fs_bsize,
393 NULL, bpp);
394 if (error) {
395 brelse(*bpp);
396 return (error);
397 }
398 }
399 return (0);
400 }
401 if (nb != 0) {
402
403 /*
404 * Consider need to reallocate a fragment.
405 */
406
407 osize = fragroundup(fs, blkoff(fs, ip->i_ffs2_size));
408 nsize = fragroundup(fs, size);
409 if (nsize <= osize) {
410
411 /*
412 * The existing block is already
413 * at least as big as we want.
414 * Just read the block (if requested).
415 */
416
417 if (bpp != NULL) {
418 error = bread(ip->i_devvp, lbn, osize,
419 NULL, bpp);
420 if (error) {
421 brelse(*bpp);
422 return (error);
423 }
424 }
425 return 0;
426 } else {
427 warnx("need to ffs_realloccg; not supported!");
428 abort();
429 }
430 } else {
431
432 /*
433 * the block was not previously allocated,
434 * allocate a new block or fragment.
435 */
436
437 if (ip->i_ffs2_size < (uint64_t)lblktosize(fs, lbn + 1))
438 nsize = fragroundup(fs, size);
439 else
440 nsize = fs->fs_bsize;
441 error = ffs_alloc(ip, lbn,
442 ffs_blkpref_ufs2(ip, lbn, (int)lbn,
443 &ip->i_ffs2_db[0]),
444 nsize, &newb);
445 if (error)
446 return (error);
447 if (bpp != NULL) {
448 bp = getblk(ip->i_devvp, lbn, nsize, 0, 0, 0);
449 bp->b_blkno = fsbtodb(fs, newb);
450 clrbuf(bp);
451 *bpp = bp;
452 }
453 }
454 ip->i_ffs2_db[lbn] = ufs_rw64(newb, needswap);
455 return (0);
456 }
457
458 /*
459 * Determine the number of levels of indirection.
460 */
461
462 pref = 0;
463 if ((error = ufs_getlbns(ip, lbn, indirs, &num)) != 0)
464 return (error);
465
466 if (num < 1) {
467 warnx("ffs_balloc: ufs_getlbns returned indirect block");
468 abort();
469 }
470
471 /*
472 * Fetch the first indirect block allocating if necessary.
473 */
474
475 --num;
476 nb = ufs_rw64(ip->i_ffs2_ib[indirs[0].in_off], needswap);
477 allocib = NULL;
478 allocblk = allociblk;
479 if (nb == 0) {
480 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0);
481 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
482 if (error)
483 return error;
484 nb = newb;
485 *allocblk++ = nb;
486 bp = getblk(ip->i_devvp, indirs[1].in_lbn, fs->fs_bsize, 0, 0, 0);
487 bp->b_blkno = fsbtodb(fs, nb);
488 clrbuf(bp);
489 /*
490 * Write synchronously so that indirect blocks
491 * never point at garbage.
492 */
493 if ((error = bwrite(bp)) != 0)
494 return error;
495 allocib = &ip->i_ffs2_ib[indirs[0].in_off];
496 *allocib = ufs_rw64(nb, needswap);
497 }
498
499 /*
500 * Fetch through the indirect blocks, allocating as necessary.
501 */
502
503 for (i = 1;;) {
504 error = bread(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize,
505 NULL, &bp);
506 if (error) {
507 brelse(bp);
508 return error;
509 }
510 bap = (int64_t *)bp->b_data;
511 nb = ufs_rw64(bap[indirs[i].in_off], needswap);
512 if (i == num)
513 break;
514 i++;
515 if (nb != 0) {
516 brelse(bp);
517 continue;
518 }
519 if (pref == 0)
520 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0);
521 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
522 if (error) {
523 brelse(bp);
524 return error;
525 }
526 nb = newb;
527 *allocblk++ = nb;
528 nbp = getblk(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize, 0, 0, 0);
529 nbp->b_blkno = fsbtodb(fs, nb);
530 clrbuf(nbp);
531 /*
532 * Write synchronously so that indirect blocks
533 * never point at garbage.
534 */
535
536 if ((error = bwrite(nbp)) != 0) {
537 brelse(bp);
538 return error;
539 }
540 bap[indirs[i - 1].in_off] = ufs_rw64(nb, needswap);
541
542 bwrite(bp);
543 }
544
545 /*
546 * Get the data block, allocating if necessary.
547 */
548
549 if (nb == 0) {
550 pref = ffs_blkpref_ufs2(ip, lbn, indirs[num].in_off, &bap[0]);
551 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
552 if (error) {
553 brelse(bp);
554 return error;
555 }
556 nb = newb;
557 *allocblk++ = nb;
558 if (bpp != NULL) {
559 nbp = getblk(ip->i_devvp, lbn, fs->fs_bsize, 0, 0, 0);
560 nbp->b_blkno = fsbtodb(fs, nb);
561 clrbuf(nbp);
562 *bpp = nbp;
563 }
564 bap[indirs[num].in_off] = ufs_rw64(nb, needswap);
565
566 /*
567 * If required, write synchronously, otherwise use
568 * delayed write.
569 */
570 bwrite(bp);
571 return (0);
572 }
573 brelse(bp);
574 if (bpp != NULL) {
575 error = bread(ip->i_devvp, lbn, (int)fs->fs_bsize, NULL, &nbp);
576 if (error) {
577 brelse(nbp);
578 return error;
579 }
580 *bpp = nbp;
581 }
582 return (0);
583 }
584 #endif
585