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
35 #include <sys/param.h>
36 #include <sys/time.h>
37
38 #include <assert.h>
39 #include <errno.h>
40 #include <stdio.h>
41 #include <stdlib.h>
42 #include <string.h>
43
44 #include "makefs.h"
45
46 #include <ufs/ufs/dinode.h>
47 #include <ufs/ffs/fs.h>
48
49 #include "ffs/ufs_bswap.h"
50 #include "ffs/buf.h"
51 #include "ffs/ufs_inode.h"
52 #include "ffs/ffs_extern.h"
53
54 static int ffs_balloc_ufs1(struct inode *, off_t, int, struct m_buf **);
55 static int ffs_balloc_ufs2(struct inode *, off_t, int, struct m_buf **);
56
57 /*
58 * Balloc defines the structure of file system storage
59 * by allocating the physical blocks on a device given
60 * the inode and the logical block number in a file.
61 *
62 * Assume: flags == B_SYNC | B_CLRBUF
63 */
64
65 int
ffs_balloc(struct inode * ip,off_t offset,int bufsize,struct m_buf ** bpp)66 ffs_balloc(struct inode *ip, off_t offset, int bufsize, struct m_buf **bpp)
67 {
68 if (ip->i_fs->fs_magic == FS_UFS2_MAGIC)
69 return ffs_balloc_ufs2(ip, offset, bufsize, bpp);
70 else
71 return ffs_balloc_ufs1(ip, offset, bufsize, bpp);
72 }
73
74 static int
ffs_balloc_ufs1(struct inode * ip,off_t offset,int bufsize,struct m_buf ** bpp)75 ffs_balloc_ufs1(struct inode *ip, off_t offset, int bufsize,
76 struct m_buf **bpp)
77 {
78 daddr_t lbn, lastlbn;
79 int size;
80 int32_t nb;
81 struct m_buf *bp, *nbp;
82 struct fs *fs = ip->i_fs;
83 struct indir indirs[UFS_NIADDR + 2];
84 daddr_t newb, pref;
85 int32_t *bap;
86 int osize, nsize, num, i, error;
87 int32_t *allocblk, allociblk[UFS_NIADDR + 1];
88 int32_t *allocib;
89 const int needswap = UFS_FSNEEDSWAP(fs);
90
91 lbn = lblkno(fs, offset);
92 size = blkoff(fs, offset) + bufsize;
93 if (bpp != NULL) {
94 *bpp = NULL;
95 }
96
97 assert(size <= fs->fs_bsize);
98 if (lbn < 0)
99 return (EFBIG);
100
101 /*
102 * If the next write will extend the file into a new block,
103 * and the file is currently composed of a fragment
104 * this fragment has to be extended to be a full block.
105 */
106
107 lastlbn = lblkno(fs, ip->i_ffs1_size);
108 if (lastlbn < UFS_NDADDR && lastlbn < lbn) {
109 nb = lastlbn;
110 osize = blksize(fs, ip, nb);
111 if (osize < fs->fs_bsize && osize > 0) {
112 warnx("need to ffs_realloccg; not supported!");
113 abort();
114 }
115 }
116
117 /*
118 * The first UFS_NDADDR blocks are direct blocks
119 */
120
121 if (lbn < UFS_NDADDR) {
122 nb = ufs_rw32(ip->i_ffs1_db[lbn], needswap);
123 if (nb != 0 && ip->i_ffs1_size >=
124 (uint64_t)lblktosize(fs, lbn + 1)) {
125
126 /*
127 * The block is an already-allocated direct block
128 * and the file already extends past this block,
129 * thus this must be a whole block.
130 * Just read the block (if requested).
131 */
132
133 if (bpp != NULL) {
134 error = bread((void *)ip->i_devvp, lbn,
135 fs->fs_bsize, NULL, bpp);
136 if (error) {
137 brelse(*bpp);
138 return (error);
139 }
140 }
141 return (0);
142 }
143 if (nb != 0) {
144
145 /*
146 * Consider need to reallocate a fragment.
147 */
148
149 osize = fragroundup(fs, blkoff(fs, ip->i_ffs1_size));
150 nsize = fragroundup(fs, size);
151 if (nsize <= osize) {
152
153 /*
154 * The existing block is already
155 * at least as big as we want.
156 * Just read the block (if requested).
157 */
158
159 if (bpp != NULL) {
160 error = bread((void *)ip->i_devvp, lbn,
161 osize, NULL, bpp);
162 if (error) {
163 brelse(*bpp);
164 return (error);
165 }
166 }
167 return 0;
168 } else {
169 warnx("need to ffs_realloccg; not supported!");
170 abort();
171 }
172 } else {
173
174 /*
175 * the block was not previously allocated,
176 * allocate a new block or fragment.
177 */
178
179 if (ip->i_ffs1_size < (uint64_t)lblktosize(fs, lbn + 1))
180 nsize = fragroundup(fs, size);
181 else
182 nsize = fs->fs_bsize;
183 error = ffs_alloc(ip, lbn,
184 ffs_blkpref_ufs1(ip, lbn, (int)lbn,
185 &ip->i_ffs1_db[0]),
186 nsize, &newb);
187 if (error)
188 return (error);
189 if (bpp != NULL) {
190 bp = getblk((void *)ip->i_devvp, lbn, nsize,
191 0, 0, 0);
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((void *)ip->i_devvp, indirs[1].in_lbn,
230 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((void *)ip->i_devvp, indirs[i].in_lbn,
249 fs->fs_bsize, NULL, &bp);
250 if (error) {
251 brelse(bp);
252 return error;
253 }
254 bap = (int32_t *)bp->b_data;
255 nb = ufs_rw32(bap[indirs[i].in_off], needswap);
256 if (i == num)
257 break;
258 i++;
259 if (nb != 0) {
260 brelse(bp);
261 continue;
262 }
263 if (pref == 0)
264 pref = ffs_blkpref_ufs1(ip, lbn, 0, (int32_t *)0);
265 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
266 if (error) {
267 brelse(bp);
268 return error;
269 }
270 nb = newb;
271 *allocblk++ = nb;
272 nbp = getblk((void *)ip->i_devvp, indirs[i].in_lbn,
273 fs->fs_bsize, 0, 0, 0);
274 nbp->b_blkno = fsbtodb(fs, nb);
275 clrbuf(nbp);
276 /*
277 * Write synchronously so that indirect blocks
278 * never point at garbage.
279 */
280
281 if ((error = bwrite(nbp)) != 0) {
282 brelse(bp);
283 return error;
284 }
285 bap[indirs[i - 1].in_off] = ufs_rw32(nb, needswap);
286
287 bwrite(bp);
288 }
289
290 /*
291 * Get the data block, allocating if necessary.
292 */
293
294 if (nb == 0) {
295 pref = ffs_blkpref_ufs1(ip, lbn, indirs[num].in_off, &bap[0]);
296 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
297 if (error) {
298 brelse(bp);
299 return error;
300 }
301 nb = newb;
302 *allocblk++ = nb;
303 if (bpp != NULL) {
304 nbp = getblk((void *)ip->i_devvp, lbn, fs->fs_bsize,
305 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((void *)ip->i_devvp, lbn, (int)fs->fs_bsize,
322 NULL, &nbp);
323 if (error) {
324 brelse(nbp);
325 return error;
326 }
327 *bpp = nbp;
328 }
329 return (0);
330 }
331
332 static int
ffs_balloc_ufs2(struct inode * ip,off_t offset,int bufsize,struct m_buf ** bpp)333 ffs_balloc_ufs2(struct inode *ip, off_t offset, int bufsize,
334 struct m_buf **bpp)
335 {
336 daddr_t lbn, lastlbn;
337 int size;
338 struct m_buf *bp, *nbp;
339 struct fs *fs = ip->i_fs;
340 struct indir indirs[UFS_NIADDR + 2];
341 daddr_t newb, pref, nb;
342 int64_t *bap;
343 int osize, nsize, num, i, error;
344 int64_t *allocblk, allociblk[UFS_NIADDR + 1];
345 int64_t *allocib;
346 const int needswap = UFS_FSNEEDSWAP(fs);
347
348 lbn = lblkno(fs, offset);
349 size = blkoff(fs, offset) + bufsize;
350 if (bpp != NULL) {
351 *bpp = NULL;
352 }
353
354 assert(size <= fs->fs_bsize);
355 if (lbn < 0)
356 return (EFBIG);
357
358 /*
359 * If the next write will extend the file into a new block,
360 * and the file is currently composed of a fragment
361 * this fragment has to be extended to be a full block.
362 */
363
364 lastlbn = lblkno(fs, ip->i_ffs2_size);
365 if (lastlbn < UFS_NDADDR && lastlbn < lbn) {
366 nb = lastlbn;
367 osize = blksize(fs, ip, nb);
368 if (osize < fs->fs_bsize && osize > 0) {
369 warnx("need to ffs_realloccg; not supported!");
370 abort();
371 }
372 }
373
374 /*
375 * The first UFS_NDADDR blocks are direct blocks
376 */
377
378 if (lbn < UFS_NDADDR) {
379 nb = ufs_rw64(ip->i_ffs2_db[lbn], needswap);
380 if (nb != 0 && ip->i_ffs2_size >=
381 (uint64_t)lblktosize(fs, lbn + 1)) {
382
383 /*
384 * The block is an already-allocated direct block
385 * and the file already extends past this block,
386 * thus this must be a whole block.
387 * Just read the block (if requested).
388 */
389
390 if (bpp != NULL) {
391 error = bread((void *)ip->i_devvp, lbn,
392 fs->fs_bsize, NULL, bpp);
393 if (error) {
394 brelse(*bpp);
395 return (error);
396 }
397 }
398 return (0);
399 }
400 if (nb != 0) {
401
402 /*
403 * Consider need to reallocate a fragment.
404 */
405
406 osize = fragroundup(fs, blkoff(fs, ip->i_ffs2_size));
407 nsize = fragroundup(fs, size);
408 if (nsize <= osize) {
409
410 /*
411 * The existing block is already
412 * at least as big as we want.
413 * Just read the block (if requested).
414 */
415
416 if (bpp != NULL) {
417 error = bread((void *)ip->i_devvp, lbn,
418 osize, NULL, bpp);
419 if (error) {
420 brelse(*bpp);
421 return (error);
422 }
423 }
424 return 0;
425 } else {
426 warnx("need to ffs_realloccg; not supported!");
427 abort();
428 }
429 } else {
430
431 /*
432 * the block was not previously allocated,
433 * allocate a new block or fragment.
434 */
435
436 if (ip->i_ffs2_size < (uint64_t)lblktosize(fs, lbn + 1))
437 nsize = fragroundup(fs, size);
438 else
439 nsize = fs->fs_bsize;
440 error = ffs_alloc(ip, lbn,
441 ffs_blkpref_ufs2(ip, lbn, (int)lbn,
442 &ip->i_ffs2_db[0]),
443 nsize, &newb);
444 if (error)
445 return (error);
446 if (bpp != NULL) {
447 bp = getblk((void *)ip->i_devvp, lbn, nsize,
448 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((void *)ip->i_devvp, indirs[1].in_lbn,
487 fs->fs_bsize, 0, 0, 0);
488 bp->b_blkno = fsbtodb(fs, nb);
489 clrbuf(bp);
490 /*
491 * Write synchronously so that indirect blocks
492 * never point at garbage.
493 */
494 if ((error = bwrite(bp)) != 0)
495 return error;
496 allocib = &ip->i_ffs2_ib[indirs[0].in_off];
497 *allocib = ufs_rw64(nb, needswap);
498 }
499
500 /*
501 * Fetch through the indirect blocks, allocating as necessary.
502 */
503
504 for (i = 1;;) {
505 error = bread((void *)ip->i_devvp, indirs[i].in_lbn,
506 fs->fs_bsize, NULL, &bp);
507 if (error) {
508 brelse(bp);
509 return error;
510 }
511 bap = (int64_t *)bp->b_data;
512 nb = ufs_rw64(bap[indirs[i].in_off], needswap);
513 if (i == num)
514 break;
515 i++;
516 if (nb != 0) {
517 brelse(bp);
518 continue;
519 }
520 if (pref == 0)
521 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0);
522 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
523 if (error) {
524 brelse(bp);
525 return error;
526 }
527 nb = newb;
528 *allocblk++ = nb;
529 nbp = getblk((void *)ip->i_devvp, indirs[i].in_lbn,
530 fs->fs_bsize, 0, 0, 0);
531 nbp->b_blkno = fsbtodb(fs, nb);
532 clrbuf(nbp);
533 /*
534 * Write synchronously so that indirect blocks
535 * never point at garbage.
536 */
537
538 if ((error = bwrite(nbp)) != 0) {
539 brelse(bp);
540 return error;
541 }
542 bap[indirs[i - 1].in_off] = ufs_rw64(nb, needswap);
543
544 bwrite(bp);
545 }
546
547 /*
548 * Get the data block, allocating if necessary.
549 */
550
551 if (nb == 0) {
552 pref = ffs_blkpref_ufs2(ip, lbn, indirs[num].in_off, &bap[0]);
553 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
554 if (error) {
555 brelse(bp);
556 return error;
557 }
558 nb = newb;
559 *allocblk++ = nb;
560 if (bpp != NULL) {
561 nbp = getblk((void *)ip->i_devvp, lbn, fs->fs_bsize,
562 0, 0, 0);
563 nbp->b_blkno = fsbtodb(fs, nb);
564 clrbuf(nbp);
565 *bpp = nbp;
566 }
567 bap[indirs[num].in_off] = ufs_rw64(nb, needswap);
568
569 /*
570 * If required, write synchronously, otherwise use
571 * delayed write.
572 */
573 bwrite(bp);
574 return (0);
575 }
576 brelse(bp);
577 if (bpp != NULL) {
578 error = bread((void *)ip->i_devvp, lbn, (int)fs->fs_bsize,
579 NULL, &nbp);
580 if (error) {
581 brelse(nbp);
582 return error;
583 }
584 *bpp = nbp;
585 }
586 return (0);
587 }
588