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