1 /* $NetBSD: ffs_balloc.c,v 1.23 2023/03/13 22:17:24 christos 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 #if HAVE_NBTOOL_CONFIG_H
36 #include "nbtool_config.h"
37 #endif
38
39 #include <sys/cdefs.h>
40 #if defined(__RCSID) && !defined(__lint)
41 __RCSID("$NetBSD: ffs_balloc.c,v 1.23 2023/03/13 22:17:24 christos Exp $");
42 #endif /* !__lint */
43
44 #include <sys/param.h>
45 #include <sys/time.h>
46
47 #include <assert.h>
48 #include <errno.h>
49 #include <stdio.h>
50 #include <stdlib.h>
51 #include <string.h>
52
53 #include "makefs.h"
54
55 #include <ufs/ufs/dinode.h>
56 #include <ufs/ufs/ufs_bswap.h>
57 #include <ufs/ffs/fs.h>
58
59 #include "ffs/buf.h"
60 #include "ffs/ufs_inode.h"
61 #include "ffs/ffs_extern.h"
62
63 static int ffs_balloc_ufs1(struct inode *, off_t, int, struct buf **);
64 static int ffs_balloc_ufs2(struct inode *, off_t, int, struct buf **);
65
66 /*
67 * Balloc defines the structure of file system storage
68 * by allocating the physical blocks on a device given
69 * the inode and the logical block number in a file.
70 *
71 * Assume: flags == B_SYNC | B_CLRBUF
72 */
73
74 int
ffs_balloc(struct inode * ip,off_t offset,int bufsize,struct buf ** bpp)75 ffs_balloc(struct inode *ip, off_t offset, int bufsize, struct buf **bpp)
76 {
77 if (ip->i_fs->fs_magic == FS_UFS2_MAGIC ||
78 ip->i_fs->fs_magic == FS_UFS2EA_MAGIC)
79 return ffs_balloc_ufs2(ip, offset, bufsize, bpp);
80 else
81 return ffs_balloc_ufs1(ip, offset, bufsize, bpp);
82 }
83
84 static int
ffs_balloc_ufs1(struct inode * ip,off_t offset,int bufsize,struct buf ** bpp)85 ffs_balloc_ufs1(struct inode *ip, off_t offset, int bufsize, struct buf **bpp)
86 {
87 daddr_t lbn, lastlbn;
88 int size;
89 int32_t nb;
90 struct buf *bp, *nbp;
91 struct fs *fs = ip->i_fs;
92 struct indir indirs[UFS_NIADDR + 2];
93 daddr_t newb, pref;
94 int32_t *bap;
95 int osize, nsize, num, i, error;
96 int32_t *allocblk, allociblk[UFS_NIADDR + 1];
97 int32_t *allocib;
98 const int needswap = UFS_FSNEEDSWAP(fs);
99
100 lbn = ffs_lblkno(fs, offset);
101 size = ffs_blkoff(fs, offset) + bufsize;
102 if (bpp != NULL) {
103 *bpp = NULL;
104 }
105
106 assert(size <= fs->fs_bsize);
107 if (lbn < 0)
108 return (EFBIG);
109
110 /*
111 * If the next write will extend the file into a new block,
112 * and the file is currently composed of a fragment
113 * this fragment has to be extended to be a full block.
114 */
115
116 lastlbn = ffs_lblkno(fs, ip->i_ffs1_size);
117 if (lastlbn < UFS_NDADDR && lastlbn < lbn) {
118 nb = lastlbn;
119 osize = ffs_blksize(fs, ip, nb);
120 if (osize < fs->fs_bsize && osize > 0) {
121 warnx("need to ffs_realloccg; not supported!");
122 abort();
123 }
124 }
125
126 /*
127 * The first UFS_NDADDR blocks are direct blocks
128 */
129
130 if (lbn < UFS_NDADDR) {
131 nb = ufs_rw32(ip->i_ffs1_db[lbn], needswap);
132 if (nb != 0 && ip->i_ffs1_size >= ffs_lblktosize(fs, lbn + 1)) {
133
134 /*
135 * The block is an already-allocated direct block
136 * and the file already extends past this block,
137 * thus this must be a whole block.
138 * Just read the block (if requested).
139 */
140
141 if (bpp != NULL) {
142 error = bread(ip->i_devvp, lbn, fs->fs_bsize,
143 0, bpp);
144 if (error) {
145 return (error);
146 }
147 }
148 return (0);
149 }
150 if (nb != 0) {
151
152 /*
153 * Consider need to reallocate a fragment.
154 */
155
156 osize = ffs_fragroundup(fs, ffs_blkoff(fs, ip->i_ffs1_size));
157 nsize = ffs_fragroundup(fs, size);
158 if (nsize <= osize) {
159
160 /*
161 * The existing block is already
162 * at least as big as we want.
163 * Just read the block (if requested).
164 */
165
166 if (bpp != NULL) {
167 error = bread(ip->i_devvp, lbn, osize,
168 0, bpp);
169 if (error) {
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 < ffs_lblktosize(fs, lbn + 1))
186 nsize = ffs_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);
197 bp->b_blkno = FFS_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);
235 bp->b_blkno = FFS_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 0, &bp);
254 if (error) {
255 return error;
256 }
257 bap = (int32_t *)bp->b_data;
258 nb = ufs_rw32(bap[indirs[i].in_off], needswap);
259 if (i == num)
260 break;
261 i++;
262 if (nb != 0) {
263 brelse(bp, 0);
264 continue;
265 }
266 if (pref == 0)
267 pref = ffs_blkpref_ufs1(ip, lbn, 0, (int32_t *)0);
268 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
269 if (error) {
270 brelse(bp, 0);
271 return error;
272 }
273 nb = newb;
274 *allocblk++ = nb;
275 nbp = getblk(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize, 0, 0);
276 nbp->b_blkno = FFS_FSBTODB(fs, nb);
277 clrbuf(nbp);
278 /*
279 * Write synchronously so that indirect blocks
280 * never point at garbage.
281 */
282
283 if ((error = bwrite(nbp)) != 0) {
284 brelse(bp, 0);
285 return error;
286 }
287 bap[indirs[i - 1].in_off] = ufs_rw32(nb, needswap);
288
289 bwrite(bp);
290 }
291
292 /*
293 * Get the data block, allocating if necessary.
294 */
295
296 if (nb == 0) {
297 pref = ffs_blkpref_ufs1(ip, lbn, indirs[num].in_off, &bap[0]);
298 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
299 if (error) {
300 brelse(bp, 0);
301 return error;
302 }
303 nb = newb;
304 *allocblk++ = nb;
305 if (bpp != NULL) {
306 nbp = getblk(ip->i_devvp, lbn, fs->fs_bsize, 0, 0);
307 nbp->b_blkno = FFS_FSBTODB(fs, nb);
308 clrbuf(nbp);
309 *bpp = nbp;
310 }
311 bap[indirs[num].in_off] = ufs_rw32(nb, needswap);
312
313 /*
314 * If required, write synchronously, otherwise use
315 * delayed write.
316 */
317 bwrite(bp);
318 return (0);
319 }
320 brelse(bp, 0);
321 if (bpp != NULL) {
322 error = bread(ip->i_devvp, lbn, (int)fs->fs_bsize, 0, &nbp);
323 if (error) {
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 = ffs_lblkno(fs, offset);
347 size = ffs_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 = ffs_lblkno(fs, ip->i_ffs2_size);
363 if (lastlbn < UFS_NDADDR && lastlbn < lbn) {
364 nb = lastlbn;
365 osize = ffs_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 >= ffs_lblktosize(fs, lbn + 1)) {
379
380 /*
381 * The block is an already-allocated direct block
382 * and the file already extends past this block,
383 * thus this must be a whole block.
384 * Just read the block (if requested).
385 */
386
387 if (bpp != NULL) {
388 error = bread(ip->i_devvp, lbn, fs->fs_bsize,
389 0, bpp);
390 if (error) {
391 return (error);
392 }
393 }
394 return (0);
395 }
396 if (nb != 0) {
397
398 /*
399 * Consider need to reallocate a fragment.
400 */
401
402 osize = ffs_fragroundup(fs, ffs_blkoff(fs, ip->i_ffs2_size));
403 nsize = ffs_fragroundup(fs, size);
404 if (nsize <= osize) {
405
406 /*
407 * The existing block is already
408 * at least as big as we want.
409 * Just read the block (if requested).
410 */
411
412 if (bpp != NULL) {
413 error = bread(ip->i_devvp, lbn, osize,
414 0, bpp);
415 if (error) {
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 < ffs_lblktosize(fs, lbn + 1))
432 nsize = ffs_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_devvp, lbn, nsize, 0, 0);
443 bp->b_blkno = FFS_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_devvp, indirs[1].in_lbn, fs->fs_bsize, 0, 0);
481 bp->b_blkno = FFS_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_devvp, indirs[i].in_lbn, fs->fs_bsize,
499 0, &bp);
500 if (error) {
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(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize, 0, 0);
522 nbp->b_blkno = FFS_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(ip->i_devvp, lbn, fs->fs_bsize, 0, 0);
553 nbp->b_blkno = FFS_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(ip->i_devvp, lbn, (int)fs->fs_bsize, 0,
569 &nbp);
570 if (error) {
571 brelse(nbp, 0);
572 return error;
573 }
574 *bpp = nbp;
575 }
576 return (0);
577 }
578