1 #include <u.h>
2 #include <libc.h>
3 #include "cformat.h"
4 #include "lru.h"
5 #include "bcache.h"
6 #include "disk.h"
7
8 int icformat(Disk*, ulong);
9
10 /*
11 * read in the disk structures, return -1 if the format
12 * is inconsistent.
13 */
14 int
dinit(Disk * d,char * mc,int psize,char * expname)15 dinit(Disk *d, char *mc, int psize, char *expname)
16 {
17 ulong i;
18 uvlong length;
19 char buf[1024];
20 Bbuf *b;
21 Dalloc *ba;
22
23 /*
24 * get disk size
25 */
26 length = cachesize;
27
28 /*
29 * read first physical block to get logical block size, # of inodes,
30 * and # of allocation blocks
31 */
32 memmove(buf, mc, sizeof buf);
33
34 ba = (Dalloc*)buf;
35 if(ba->bsize <= 0){
36 fprint(2, "dinit: bsize 0x%lux<= 0\n", ba->bsize);
37 return -1;
38 }
39 if((ba->bsize % psize) != 0){
40 fprint(2, "dinit: logical bsize (%lud) not multiple of physical (%ud)\n",
41 ba->bsize, psize);
42 return -1;
43 }
44 d->bsize = ba->bsize;
45 d->nb = length/d->bsize;
46 d->b2b = (d->bsize - sizeof(Dahdr))*8;
47 d->nab = (d->nb+d->b2b-1)/d->b2b;
48 d->p2b = d->bsize/sizeof(Dptr);
49 strncpy(d->name, ba->name, sizeof d->name);
50
51 if (expname != nil && strncmp(d->name, expname, sizeof d->name) != 0) {
52 /* Mismatch with recorded name; fail here to force a format */
53 fprint(2, "%s: name mismatch\n", argv0);
54 return -1;
55 }
56
57 /*
58 * check allocation blocks for consistency
59 */
60 if(bcinit(d, mc, d->bsize) < 0){
61 fprint(2, "%s: dinit: couldn't init block cache\n", argv0);
62 return -1;
63 }
64 for(i = 0; i < d->nab; i++){
65 b = bcread(d, i);
66 if(b == 0){
67 perror("dinit: read");
68 return -1;
69 }
70 ba = (Dalloc*)b->data;
71 if(ba->magic != Amagic){
72 fprint(2, "dinit: bad magic in alloc block %uld\n", i);
73 return -1;
74 }
75 if(d->bsize != ba->bsize){
76 fprint(2, "dinit: bad bsize in alloc block %uld\n", i);
77 return -1;
78 }
79 if(d->nab != ba->nab){
80 fprint(2, "dinit: bad nab in alloc block %uld\n", i);
81 return -1;
82 }
83 if(strncmp(d->name, ba->name, sizeof(d->name))){
84 fprint(2, "dinit: bad name in alloc block %uld\n", i);
85 return -1;
86 }
87 }
88 return 0;
89 }
90
91 /*
92 * format the allocated memory as a cache
93 */
94 int
dformat(Disk * d,char * mc,char * name,ulong bsize,ulong psize)95 dformat(Disk *d, char *mc, char *name, ulong bsize, ulong psize)
96 {
97 int i;
98 uvlong length;
99 Bbuf *b;
100 Dalloc *ba;
101 Dptr dptr;
102
103 fprint(2, "formatting memory\n");
104
105 /*
106 * calculate basic numbers
107 */
108 length = cachesize;
109 d->bsize = bsize;
110 if((d->bsize % psize) != 0){
111 fprint(2, "%s: logical bsize not multiple of physical\n", argv0);
112 return -1;
113 }
114 d->nb = length/d->bsize;
115 d->b2b = (d->bsize - sizeof(Dahdr))*8;
116 d->nab = (d->nb+d->b2b-1)/d->b2b;
117 d->p2b = d->bsize/sizeof(Dptr);
118
119 /*
120 * init allocation blocks
121 */
122 if(bcinit(d, mc, d->bsize) < 0)
123 return -1;
124 for(i = 0; i < d->nab; i++){
125 b = bcalloc(d, i);
126 if(b == 0){
127 perror("cfs: bcalloc");
128 return -1;
129 }
130 memset(b->data, 0, d->bsize);
131 ba = (Dalloc*)b->data;
132 ba->magic = Amagic;
133 ba->bsize = d->bsize;
134 ba->nab = d->nab;
135 strncpy(ba->name, name, sizeof(ba->name));
136 bcmark(d, b);
137 }
138
139 /*
140 * allocate allocation blocks
141 */
142 for(i = 0; i < d->nab; i++)
143 if(dalloc(d, &dptr) == Notabno){
144 fprint(2, "can't allocate allocation blocks\n");
145 return -1;
146 }
147
148 return bcsync(d);
149 }
150
151 /*
152 * allocate a block from a bit vector page
153 *
154 * a return value of Notabno means no blocks left
155 */
156 static ulong
_balloc(Dalloc * ba,ulong max)157 _balloc(Dalloc *ba, ulong max)
158 {
159 int len; /* number of valid words */
160 ulong i; /* bit position in long */
161 ulong m; /* 1<<i */
162 ulong v; /* old value of long */
163 ulong *p, *e;
164
165 /*
166 * find a word with a 0 bit
167 */
168 len = (max+BtoUL-1)/BtoUL;
169 for(p = ba->bits, e = p + len; p < e; p++)
170 if(*p != 0xFFFFFFFF)
171 break;
172 if(p == e)
173 return Notabno;
174
175 /*
176 * find the first 0 bit
177 */
178 v = *p;
179 for(m = 1, i = 0; i < BtoUL; i++, m <<= 1)
180 if((m|v) != v)
181 break;
182
183 /*
184 * calculate block number
185 */
186 i += (p - ba->bits)*BtoUL;
187 if(i >= max)
188 return Notabno;
189
190 /*
191 * set bit to 1
192 */
193 *p = v | m;
194 return i;
195 }
196
197 /*
198 * allocate a block
199 *
200 * return Notabno if none left
201 */
202 ulong
dalloc(Disk * d,Dptr * p)203 dalloc(Disk *d, Dptr *p)
204 {
205 ulong bno, max, rv;
206 Bbuf *b;
207 Dalloc *ba;
208
209 max = d->nb;
210 for(bno = 0; bno < d->nab; bno++){
211 b = bcread(d, bno);
212 ba = (Dalloc*)b->data;
213 rv = _balloc(ba, max > d->b2b ? d->b2b : max);
214 if(rv != Notabno){
215 rv = bno*d->b2b + rv;
216 if(p){
217 p->start = p->end = 0;
218 p->bno = rv;
219 }
220 bcmark(d, b);
221 return rv;
222 }
223 max -= d->b2b;
224 }
225 if(p)
226 p->bno = Notabno;
227 return Notabno;
228 }
229
230 /*
231 * allocate a block of pointers
232 */
233 ulong
dpalloc(Disk * d,Dptr * p)234 dpalloc(Disk *d, Dptr *p)
235 {
236 Bbuf *b;
237 Dptr *sp, *ep;
238
239 if(dalloc(d, p) == Notabno)
240 return Notabno;
241
242 /*
243 * allocate the page and invalidate all the
244 * pointers
245 */
246 b = bcalloc(d, p->bno);
247 if(b == 0)
248 return -1;
249 sp = (Dptr*)b->data;
250 for(ep = sp + d->p2b; sp < ep; sp++){
251 sp->bno = Notabno;
252 sp->start = sp->end = 0;
253 }
254 p->bno |= Indbno;
255 p->start = 0;
256 p->end = d->bsize;
257
258 /*
259 * mark the page as dirty
260 */
261 bcmark(d, b);
262 return 0;
263 }
264
265 /*
266 * free a block
267 */
268 int
_bfree(Disk * d,ulong i)269 _bfree(Disk *d, ulong i)
270 {
271 ulong bno, m;
272 ulong *p;
273 Bbuf *b;
274 Dalloc *ba;
275
276 /*
277 * get correct allocation block
278 */
279 bno = i/d->b2b;
280 if(bno >= d->nab)
281 return -1;
282 b = bcread(d, bno);
283 if(b == 0)
284 return -1;
285 ba = (Dalloc*)b->data;
286
287 /*
288 * change bit
289 */
290 i -= bno*d->b2b;
291 p = ba->bits + (i/BtoUL);
292 m = 1<<(i%BtoUL);
293 *p &= ~m;
294 bcmark(d, b);
295
296 return 0;
297 }
298
299 /*
300 * free a block (or blocks)
301 */
302 int
dfree(Disk * d,Dptr * dp)303 dfree(Disk *d, Dptr *dp)
304 {
305 ulong bno;
306 Dptr *sp, *ep;
307 Bbuf *b;
308
309 bno = dp->bno;
310 dp->bno = Notabno;
311
312 /*
313 * nothing to free
314 */
315 if(bno == Notabno)
316 return 0;
317
318 /*
319 * direct pointer
320 */
321 if((bno & Indbno) == 0)
322 return _bfree(d, bno);
323
324 /*
325 * first indirect page
326 */
327 bno &= ~Indbno;
328 _bfree(d, bno);
329
330 /*
331 * then all the pages it points to
332 *
333 * DANGER: this algorithm may fail if there are more
334 * allocation blocks than block buffers
335 */
336 b = bcread(d, bno);
337 if(b == 0)
338 return -1;
339 sp = (Dptr*)b->data;
340 for(ep = sp + d->p2b; sp < ep; sp++)
341 if(dfree(d, sp) < 0)
342 return -1;
343 return 0;
344 }
345