GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/makefs/ffs/ffs_alloc.c Lines: 0 180 0.0 %
Date: 2017-11-13 Branches: 0 132 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: ffs_alloc.c,v 1.13 2016/12/17 16:26:46 krw Exp $	*/
2
/*	$NetBSD: ffs_alloc.c,v 1.29 2016/06/24 19:24:11 christos Exp $	*/
3
/* From: NetBSD: ffs_alloc.c,v 1.50 2001/09/06 02:16:01 lukem Exp */
4
5
/*
6
 * Copyright (c) 2002 Networks Associates Technology, Inc.
7
 * All rights reserved.
8
 *
9
 * This software was developed for the FreeBSD Project by Marshall
10
 * Kirk McKusick and Network Associates Laboratories, the Security
11
 * Research Division of Network Associates, Inc. under DARPA/SPAWAR
12
 * contract N66001-01-C-8035 ("CBOSS"), as part of the DARPA CHATS
13
 * research program
14
 *
15
 * Copyright (c) 1982, 1986, 1989, 1993
16
 *	The Regents of the University of California.  All rights reserved.
17
 *
18
 * Redistribution and use in source and binary forms, with or without
19
 * modification, are permitted provided that the following conditions
20
 * are met:
21
 * 1. Redistributions of source code must retain the above copyright
22
 *    notice, this list of conditions and the following disclaimer.
23
 * 2. Redistributions in binary form must reproduce the above copyright
24
 *    notice, this list of conditions and the following disclaimer in the
25
 *    documentation and/or other materials provided with the distribution.
26
 * 3. Neither the name of the University nor the names of its contributors
27
 *    may be used to endorse or promote products derived from this software
28
 *    without specific prior written permission.
29
 *
30
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
31
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
32
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
34
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
36
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
39
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
40
 * SUCH DAMAGE.
41
 *
42
 *	@(#)ffs_alloc.c	8.19 (Berkeley) 7/13/95
43
 */
44
45
#include <sys/param.h>
46
47
#include <errno.h>
48
49
#include <ufs/ufs/dinode.h>
50
#include <ufs/ffs/fs.h>
51
52
#include "ffs/buf.h"
53
#include "ffs/ufs_inode.h"
54
#include "ffs/ffs_extern.h"
55
56
57
static int scanc(u_int, const u_char *, const u_char *, int);
58
59
static daddr_t ffs_alloccg(struct inode *, int, daddr_t, int);
60
static daddr_t ffs_alloccgblk(struct inode *, struct mkfsbuf *, daddr_t);
61
static daddr_t ffs_hashalloc(struct inode *, int, daddr_t, int,
62
		     daddr_t (*)(struct inode *, int, daddr_t, int));
63
static int32_t ffs_mapsearch(struct fs *, struct cg *, daddr_t, int);
64
65
/*
66
 * Allocate a block in the file system.
67
 *
68
 * The size of the requested block is given, which must be some
69
 * multiple of fs_fsize and <= fs_bsize.
70
 * A preference may be optionally specified. If a preference is given
71
 * the following hierarchy is used to allocate a block:
72
 *   1) allocate the requested block.
73
 *   2) allocate a rotationally optimal block in the same cylinder.
74
 *   3) allocate a block in the same cylinder group.
75
 *   4) quadradically rehash into other cylinder groups, until an
76
 *      available block is located.
77
 * If no block preference is given the following hierarchy is used
78
 * to allocate a block:
79
 *   1) allocate a block in the cylinder group that contains the
80
 *      inode for the file.
81
 *   2) quadradically rehash into other cylinder groups, until an
82
 *      available block is located.
83
 */
84
int
85
ffs_alloc(struct inode *ip, daddr_t lbn __unused, daddr_t bpref, int size,
86
    daddr_t *bnp)
87
{
88
	struct fs *fs = ip->i_fs;
89
	daddr_t bno;
90
	int cg;
91
92
	*bnp = 0;
93
	if (size > fs->fs_bsize || fragoff(fs, size) != 0) {
94
		errx(1, "%s: bad size: bsize %d size %d", __func__,
95
		    fs->fs_bsize, size);
96
	}
97
	if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0)
98
		goto nospace;
99
	if (bpref >= fs->fs_size)
100
		bpref = 0;
101
	if (bpref == 0)
102
		cg = ino_to_cg(fs, ip->i_number);
103
	else
104
		cg = dtog(fs, bpref);
105
	bno = ffs_hashalloc(ip, cg, bpref, size, ffs_alloccg);
106
	if (bno > 0) {
107
		DIP_ADD(ip, blocks, size / DEV_BSIZE);
108
		*bnp = bno;
109
		return (0);
110
	}
111
nospace:
112
	return (ENOSPC);
113
}
114
115
/*
116
 * Select the desired position for the next block in a file.  The file is
117
 * logically divided into sections. The first section is composed of the
118
 * direct blocks. Each additional section contains fs_maxbpg blocks.
119
 *
120
 * If no blocks have been allocated in the first section, the policy is to
121
 * request a block in the same cylinder group as the inode that describes
122
 * the file. If no blocks have been allocated in any other section, the
123
 * policy is to place the section in a cylinder group with a greater than
124
 * average number of free blocks.  An appropriate cylinder group is found
125
 * by using a rotor that sweeps the cylinder groups. When a new group of
126
 * blocks is needed, the sweep begins in the cylinder group following the
127
 * cylinder group from which the previous allocation was made. The sweep
128
 * continues until a cylinder group with greater than the average number
129
 * of free blocks is found. If the allocation is for the first block in an
130
 * indirect block, the information on the previous allocation is unavailable;
131
 * here a best guess is made based upon the logical block number being
132
 * allocated.
133
 *
134
 * If a section is already partially allocated, the policy is to
135
 * contiguously allocate fs_maxcontig blocks.  The end of one of these
136
 * contiguous blocks and the beginning of the next is physically separated
137
 * so that the disk head will be in transit between them for at least
138
 * fs_rotdelay milliseconds.  This is to allow time for the processor to
139
 * schedule another I/O transfer.
140
 */
141
/* XXX ondisk32 */
142
daddr_t
143
ffs_blkpref_ufs1(struct inode *ip, daddr_t lbn, int indx, int32_t *bap)
144
{
145
	struct fs *fs;
146
	int cg;
147
	int avgbfree, startcg;
148
149
	fs = ip->i_fs;
150
	if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) {
151
		if (lbn < NDADDR + NINDIR(fs)) {
152
			cg = ino_to_cg(fs, ip->i_number);
153
			return (fs->fs_fpg * cg + fs->fs_frag);
154
		}
155
		/*
156
		 * Find a cylinder with greater than average number of
157
		 * unused data blocks.
158
		 */
159
		if (indx == 0 || bap[indx - 1] == 0)
160
			startcg =
161
			    ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg;
162
		else
163
			startcg = dtog(fs, bap[indx - 1] + 1);
164
		startcg %= fs->fs_ncg;
165
		avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
166
		for (cg = startcg; cg < fs->fs_ncg; cg++)
167
			if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree)
168
				return (fs->fs_fpg * cg + fs->fs_frag);
169
		for (cg = 0; cg <= startcg; cg++)
170
			if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree)
171
				return (fs->fs_fpg * cg + fs->fs_frag);
172
		return (0);
173
	}
174
	/*
175
	 * We just always try to lay things out contiguously.
176
	 */
177
	return bap[indx - 1] + fs->fs_frag;
178
}
179
180
daddr_t
181
ffs_blkpref_ufs2(struct inode *ip, daddr_t lbn, int indx, int64_t *bap)
182
{
183
	struct fs *fs;
184
	int cg;
185
	int avgbfree, startcg;
186
187
	fs = ip->i_fs;
188
	if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) {
189
		if (lbn < NDADDR + NINDIR(fs)) {
190
			cg = ino_to_cg(fs, ip->i_number);
191
			return (fs->fs_fpg * cg + fs->fs_frag);
192
		}
193
		/*
194
		 * Find a cylinder with greater than average number of
195
		 * unused data blocks.
196
		 */
197
		if (indx == 0 || bap[indx - 1] == 0)
198
			startcg =
199
			    ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg;
200
		else
201
			startcg = dtog(fs, bap[indx - 1] + 1);
202
		startcg %= fs->fs_ncg;
203
		avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
204
		for (cg = startcg; cg < fs->fs_ncg; cg++)
205
			if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
206
				return (fs->fs_fpg * cg + fs->fs_frag);
207
			}
208
		for (cg = 0; cg < startcg; cg++)
209
			if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
210
				return (fs->fs_fpg * cg + fs->fs_frag);
211
			}
212
		return (0);
213
	}
214
	/*
215
	 * We just always try to lay things out contiguously.
216
	 */
217
	return bap[indx - 1] + fs->fs_frag;
218
}
219
220
/*
221
 * Implement the cylinder overflow algorithm.
222
 *
223
 * The policy implemented by this algorithm is:
224
 *   1) allocate the block in its requested cylinder group.
225
 *   2) quadradically rehash on the cylinder group number.
226
 *   3) brute force search for a free block.
227
 *
228
 * `size':	size for data blocks, mode for inodes
229
 */
230
/*VARARGS5*/
231
static daddr_t
232
ffs_hashalloc(struct inode *ip, int cg, daddr_t pref, int size,
233
    daddr_t (*allocator)(struct inode *, int, daddr_t, int))
234
{
235
	struct fs *fs;
236
	daddr_t result;
237
	int i, icg = cg;
238
239
	fs = ip->i_fs;
240
	/*
241
	 * 1: preferred cylinder group
242
	 */
243
	result = (*allocator)(ip, cg, pref, size);
244
	if (result)
245
		return (result);
246
	/*
247
	 * 2: quadratic rehash
248
	 */
249
	for (i = 1; i < fs->fs_ncg; i *= 2) {
250
		cg += i;
251
		if (cg >= fs->fs_ncg)
252
			cg -= fs->fs_ncg;
253
		result = (*allocator)(ip, cg, 0, size);
254
		if (result)
255
			return (result);
256
	}
257
	/*
258
	 * 3: brute force search
259
	 * Note that we start at i == 2, since 0 was checked initially,
260
	 * and 1 is always checked in the quadratic rehash.
261
	 */
262
	cg = (icg + 2) % fs->fs_ncg;
263
	for (i = 2; i < fs->fs_ncg; i++) {
264
		result = (*allocator)(ip, cg, 0, size);
265
		if (result)
266
			return (result);
267
		cg++;
268
		if (cg == fs->fs_ncg)
269
			cg = 0;
270
	}
271
	return (0);
272
}
273
274
/*
275
 * Determine whether a block can be allocated.
276
 *
277
 * Check to see if a block of the appropriate size is available,
278
 * and if it is, allocate it.
279
 */
280
static daddr_t
281
ffs_alloccg(struct inode *ip, int cg, daddr_t bpref, int size)
282
{
283
	struct cg *cgp;
284
	struct mkfsbuf *bp;
285
	daddr_t bno, blkno;
286
	int error, frags, allocsiz, i;
287
	struct fs *fs = ip->i_fs;
288
289
	if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize)
290
		return (0);
291
	error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
292
	    (int)fs->fs_cgsize, 0, &bp);
293
	if (error) {
294
		return (0);
295
	}
296
	cgp = (struct cg *)bp->b_data;
297
	if (!cg_chkmagic(cgp) ||
298
	    (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) {
299
		brelse(bp, 0);
300
		return (0);
301
	}
302
	if (size == fs->fs_bsize) {
303
		bno = ffs_alloccgblk(ip, bp, bpref);
304
		bwrite(bp);
305
		return (bno);
306
	}
307
	/*
308
	 * check to see if any fragments are already available
309
	 * allocsiz is the size which will be allocated, hacking
310
	 * it down to a smaller size if necessary
311
	 */
312
	frags = numfrags(fs, size);
313
	for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++)
314
		if (cgp->cg_frsum[allocsiz] != 0)
315
			break;
316
	if (allocsiz == fs->fs_frag) {
317
		/*
318
		 * no fragments were available, so a block will be
319
		 * allocated, and hacked up
320
		 */
321
		if (cgp->cg_cs.cs_nbfree == 0) {
322
			brelse(bp, 0);
323
			return (0);
324
		}
325
		bno = ffs_alloccgblk(ip, bp, bpref);
326
		bpref = dtogd(fs, bno);
327
		for (i = frags; i < fs->fs_frag; i++)
328
			setbit(cg_blksfree(cgp), bpref + i);
329
		i = fs->fs_frag - frags;
330
		cgp->cg_cs.cs_nffree += i;
331
		fs->fs_cstotal.cs_nffree += i;
332
		fs->fs_cs(fs, cg).cs_nffree += i;
333
		fs->fs_fmod = 1;
334
		cgp->cg_frsum[i] += 1;
335
		bdwrite(bp);
336
		return (bno);
337
	}
338
	bno = ffs_mapsearch(fs, cgp, bpref, allocsiz);
339
	for (i = 0; i < frags; i++)
340
		clrbit(cg_blksfree(cgp), bno + i);
341
	cgp->cg_cs.cs_nffree -= frags;
342
	fs->fs_cstotal.cs_nffree -= frags;
343
	fs->fs_cs(fs, cg).cs_nffree -= frags;
344
	fs->fs_fmod = 1;
345
	cgp->cg_frsum[allocsiz] -= 1;
346
	if (frags != allocsiz)
347
		cgp->cg_frsum[allocsiz - frags] += 1;
348
	blkno = cg * fs->fs_fpg + bno;
349
	bdwrite(bp);
350
	return blkno;
351
}
352
353
/*
354
 * Allocate a block in a cylinder group.
355
 *
356
 * This algorithm implements the following policy:
357
 *   1) allocate the requested block.
358
 *   2) allocate a rotationally optimal block in the same cylinder.
359
 *   3) allocate the next available block on the block rotor for the
360
 *      specified cylinder group.
361
 * Note that this routine only allocates fs_bsize blocks; these
362
 * blocks may be fragmented by the routine that allocates them.
363
 */
364
static daddr_t
365
ffs_alloccgblk(struct inode *ip, struct mkfsbuf *bp, daddr_t bpref)
366
{
367
	struct cg *cgp;
368
	daddr_t blkno;
369
	int32_t bno;
370
	struct fs *fs = ip->i_fs;
371
	u_int8_t *blksfree;
372
373
	cgp = (struct cg *)bp->b_data;
374
	blksfree = cg_blksfree(cgp);
375
	if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) {
376
		bpref = cgp->cg_rotor;
377
	} else {
378
		bpref = blknum(fs, bpref);
379
		bno = dtogd(fs, bpref);
380
		/*
381
		 * if the requested block is available, use it
382
		 */
383
		if (ffs_isblock(fs, blksfree, fragstoblks(fs, bno)))
384
			goto gotit;
385
	}
386
	/*
387
	 * Take the next available one in this cylinder group.
388
	 */
389
	bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag);
390
	if (bno < 0)
391
		return (0);
392
	cgp->cg_rotor = bno;
393
gotit:
394
	blkno = fragstoblks(fs, bno);
395
	ffs_clrblock(fs, blksfree, (long)blkno);
396
	ffs_clusteracct(fs, cgp, blkno, -1);
397
	cgp->cg_cs.cs_nbfree -= 1;
398
	fs->fs_cstotal.cs_nbfree--;
399
	fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--;
400
	fs->fs_fmod = 1;
401
	blkno = cgp->cg_cgx * fs->fs_fpg + bno;
402
	return (blkno);
403
}
404
405
static int
406
scanc(u_int size, const u_char *cp, const u_char table[], int mask)
407
{
408
	const u_char *end = &cp[size];
409
410
	while (cp < end && (table[*cp] & mask) == 0)
411
		cp++;
412
	return (end - cp);
413
}
414
415
/*
416
 * Find a block of the specified size in the specified cylinder group.
417
 *
418
 * It is a panic if a request is made to find a block if none are
419
 * available.
420
 */
421
static int32_t
422
ffs_mapsearch(struct fs *fs, struct cg *cgp, daddr_t bpref, int allocsiz)
423
{
424
	int32_t bno;
425
	int start, len, loc, i;
426
	int blk, field, subfield, pos;
427
	int ostart, olen;
428
429
	/*
430
	 * find the fragment by searching through the free block
431
	 * map for an appropriate bit pattern
432
	 */
433
	if (bpref)
434
		start = dtogd(fs, bpref) / NBBY;
435
	else
436
		start = cgp->cg_frotor / NBBY;
437
	len = howmany(fs->fs_fpg, NBBY) - start;
438
	ostart = start;
439
	olen = len;
440
	loc = scanc((u_int)len,
441
		(const u_char *)&cg_blksfree(cgp)[start],
442
		(const u_char *)fragtbl[fs->fs_frag],
443
		(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
444
	if (loc == 0) {
445
		len = start + 1;
446
		start = 0;
447
		loc = scanc((u_int)len,
448
			(const u_char *)&cg_blksfree(cgp)[0],
449
			(const u_char *)fragtbl[fs->fs_frag],
450
			(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
451
		if (loc == 0) {
452
			errx(1, "%s: map corrupted: start %d "
453
			    "len %d offset %d %ld", __func__, ostart, olen,
454
			    cgp->cg_freeoff,
455
			    (long)cg_blksfree(cgp) - (long)cgp);
456
		}
457
	}
458
	bno = (start + len - loc) * NBBY;
459
	cgp->cg_frotor = bno;
460
	/*
461
	 * found the byte in the map
462
	 * sift through the bits to find the selected frag
463
	 */
464
	for (i = bno + NBBY; bno < i; bno += fs->fs_frag) {
465
		blk = blkmap(fs, cg_blksfree(cgp), bno);
466
		blk <<= 1;
467
		field = around[allocsiz];
468
		subfield = inside[allocsiz];
469
		for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) {
470
			if ((blk & field) == subfield)
471
				return (bno + pos);
472
			field <<= 1;
473
			subfield <<= 1;
474
		}
475
	}
476
	errx(1, "%s: block not in map: bno %lld", __func__, (long long)bno);
477
	return (-1);
478
}