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