1 /* $OpenBSD: ffs_subr.c,v 1.6 2022/01/11 05:34:33 jsg Exp $ */
2 /* $NetBSD: ffs_subr.c,v 1.49 2016/05/07 11:59:08 maxv Exp $ */
3
4 /*
5 * Copyright (c) 1982, 1986, 1989, 1993
6 * The Regents of the University of California. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 * @(#)ffs_subr.c 8.5 (Berkeley) 3/21/95
33 */
34
35 #include <sys/param.h> /* setbit clrbit NBBY */
36 #include <sys/types.h>
37 #include <ufs/ufs/dinode.h>
38 #include <ufs/ffs/fs.h>
39
40 #include <limits.h>
41 #include <err.h>
42
43 #include "ffs/ffs_extern.h"
44
45
46 /*
47 * block operations
48 *
49 * check if a block is available
50 * returns true if all the corresponding bits in the free map are 1
51 * returns false if any corresponding bit in the free map is 0
52 */
53 int
ffs_isblock(struct fs * fs,u_char * cp,int32_t h)54 ffs_isblock(struct fs *fs, u_char *cp, int32_t h)
55 {
56 u_char mask;
57
58 switch ((int)fs->fs_fragshift) {
59 case 3:
60 return (cp[h] == 0xff);
61 case 2:
62 mask = 0x0f << ((h & 0x1) << 2);
63 return ((cp[h >> 1] & mask) == mask);
64 case 1:
65 mask = 0x03 << ((h & 0x3) << 1);
66 return ((cp[h >> 2] & mask) == mask);
67 case 0:
68 mask = 0x01 << (h & 0x7);
69 return ((cp[h >> 3] & mask) == mask);
70 default:
71 errx(1, "ffs_isblock: unknown fs_fragshift %d",
72 (int)fs->fs_fragshift);
73 }
74 }
75
76 /*
77 * take a block out of the map
78 */
79 void
ffs_clrblock(struct fs * fs,u_char * cp,int32_t h)80 ffs_clrblock(struct fs *fs, u_char *cp, int32_t h)
81 {
82
83 switch ((int)fs->fs_fragshift) {
84 case 3:
85 cp[h] = 0;
86 return;
87 case 2:
88 cp[h >> 1] &= ~(0x0f << ((h & 0x1) << 2));
89 return;
90 case 1:
91 cp[h >> 2] &= ~(0x03 << ((h & 0x3) << 1));
92 return;
93 case 0:
94 cp[h >> 3] &= ~(0x01 << (h & 0x7));
95 return;
96 default:
97 errx(1, "ffs_clrblock: unknown fs_fragshift %d",
98 (int)fs->fs_fragshift);
99 }
100 }
101
102 /*
103 * put a block into the map
104 */
105 void
ffs_setblock(struct fs * fs,u_char * cp,int32_t h)106 ffs_setblock(struct fs *fs, u_char *cp, int32_t h)
107 {
108
109 switch ((int)fs->fs_fragshift) {
110 case 3:
111 cp[h] = 0xff;
112 return;
113 case 2:
114 cp[h >> 1] |= (0x0f << ((h & 0x1) << 2));
115 return;
116 case 1:
117 cp[h >> 2] |= (0x03 << ((h & 0x3) << 1));
118 return;
119 case 0:
120 cp[h >> 3] |= (0x01 << (h & 0x7));
121 return;
122 default:
123 errx(1, "ffs_setblock: unknown fs_fragshift %d",
124 (int)fs->fs_fragshift);
125 }
126 }
127
128 /*
129 * Update the cluster map because of an allocation or free.
130 *
131 * Cnt == 1 means free; cnt == -1 means allocating.
132 */
133 void
ffs_clusteracct(struct fs * fs,struct cg * cgp,int32_t blkno,int cnt)134 ffs_clusteracct(struct fs *fs, struct cg *cgp, int32_t blkno, int cnt)
135 {
136 int32_t *sump;
137 int32_t *lp;
138 u_char *freemapp, *mapp;
139 int i, start, end, forw, back, map, bit;
140
141 /* KASSERT(mutex_owned(&ump->um_lock)); */
142
143 if (fs->fs_contigsumsize <= 0)
144 return;
145 freemapp = cg_clustersfree(cgp);
146 sump = cg_clustersum(cgp);
147 /*
148 * Allocate or clear the actual block.
149 */
150 if (cnt > 0)
151 setbit(freemapp, blkno);
152 else
153 clrbit(freemapp, blkno);
154 /*
155 * Find the size of the cluster going forward.
156 */
157 start = blkno + 1;
158 end = start + fs->fs_contigsumsize;
159 if ((uint32_t)end >= cgp->cg_nclusterblks)
160 end = cgp->cg_nclusterblks;
161 mapp = &freemapp[start / NBBY];
162 map = *mapp++;
163 bit = 1 << (start % NBBY);
164 for (i = start; i < end; i++) {
165 if ((map & bit) == 0)
166 break;
167 if ((i & (NBBY - 1)) != (NBBY - 1)) {
168 bit <<= 1;
169 } else {
170 map = *mapp++;
171 bit = 1;
172 }
173 }
174 forw = i - start;
175 /*
176 * Find the size of the cluster going backward.
177 */
178 start = blkno - 1;
179 end = start - fs->fs_contigsumsize;
180 if (end < 0)
181 end = -1;
182 mapp = &freemapp[start / NBBY];
183 map = *mapp--;
184 bit = 1 << (start % NBBY);
185 for (i = start; i > end; i--) {
186 if ((map & bit) == 0)
187 break;
188 if ((i & (NBBY - 1)) != 0) {
189 bit >>= 1;
190 } else {
191 map = *mapp--;
192 bit = 1 << (NBBY - 1);
193 }
194 }
195 back = start - i;
196 /*
197 * Account for old cluster and the possibly new forward and
198 * back clusters.
199 */
200 i = back + forw + 1;
201 if (i > fs->fs_contigsumsize)
202 i = fs->fs_contigsumsize;
203 sump[i] += cnt;
204 if (back > 0)
205 sump[back] -= cnt;
206 if (forw > 0)
207 sump[forw] -= cnt;
208
209 /*
210 * Update cluster summary information.
211 */
212 lp = &sump[fs->fs_contigsumsize];
213 for (i = fs->fs_contigsumsize; i > 0; i--)
214 if (*lp-- > 0)
215 break;
216 }
217