1 /* $OpenBSD: ffs_alloc.c,v 1.15 2022/01/11 05:34:33 jsg 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> /* DEV_BSIZE setbit clrbit NBBY howmany */
46 #include <sys/types.h>
47
48 #include <ufs/ufs/dinode.h>
49 #include <ufs/ffs/fs.h>
50
51 #include "ffs/buf.h"
52 #include "ffs/ufs_inode.h"
53 #include "ffs/ffs_extern.h"
54
55 #include <errno.h>
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) quadratically 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) quadratically rehash into other cylinder groups, until an
82 * available block is located.
83 */
84 int
ffs_alloc(struct inode * ip,daddr_t lbn __unused,daddr_t bpref,int size,daddr_t * bnp)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
ffs_blkpref_ufs1(struct inode * ip,daddr_t lbn,int indx,int32_t * bap)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
ffs_blkpref_ufs2(struct inode * ip,daddr_t lbn,int indx,int64_t * bap)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) quadratically 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
ffs_hashalloc(struct inode * ip,int cg,daddr_t pref,int size,daddr_t (* allocator)(struct inode *,int,daddr_t,int))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
ffs_alloccg(struct inode * ip,int cg,daddr_t bpref,int size)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
ffs_alloccgblk(struct inode * ip,struct mkfsbuf * bp,daddr_t bpref)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
scanc(u_int size,const u_char * cp,const u_char table[],int mask)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
ffs_mapsearch(struct fs * fs,struct cg * cgp,daddr_t bpref,int allocsiz)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 }
479