1 /*
2 ext2_buffer.c -- ext2 buffer cache
3 Copyright (C) 1998-2000, 2007 Free Software Foundation, Inc.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include <config.h>
20
21 #ifndef DISCOVER_ONLY
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include "ext2.h"
27
28 /* pseudo-header */
29
30 static __inline__ int ext2_block_hash(blk_t block)
31 {
32 unsigned long x;
33
34 x = block ^ (block >> 8) ^ (block >> 16) ^ (block >> 24);
35 return x & ((1 << ext2_hash_bits) - 1);
36 }
37
38 static struct ext2_buffer_head *ext2_bh_alloc (struct ext2_buffer_cache *, blk_t);
39 static void ext2_bh_dealloc (struct ext2_buffer_head *);
40 static struct ext2_buffer_head *ext2_bh_find (struct ext2_buffer_cache *, blk_t);
41 static int ext2_bh_do_read (struct ext2_buffer_head *);
42 static int ext2_bh_do_write(struct ext2_buffer_head *);
43 static void ext2_bh_hash (struct ext2_buffer_head *);
44 static void ext2_bh_unhash (struct ext2_buffer_head *);
45
46
47
48 static int try_to_flush(struct ext2_buffer_cache *bc)
49 {
50 int i;
51
52 for (i=0;i<bc->size;i++)
53 {
54 struct ext2_buffer_head *bh;
55
56 bh = &bc->heads[i];
57
58 if (bh->alloc && !bh->usecount && !bh->dirty)
59 {
60 ext2_bh_dealloc(bh);
61 return 1;
62 }
63 }
64
65 for (i=0;i<bc->size;i++)
66 {
67 struct ext2_buffer_head *bh;
68
69 bh = &bc->heads[i];
70
71 if (bh->alloc && !bh->usecount && bh->dirty)
72 {
73 ext2_bh_do_write(bh);
74 ext2_bh_dealloc(bh);
75 return 1;
76 }
77 }
78
79 if (ped_exception_throw (PED_EXCEPTION_ERROR,
80 PED_EXCEPTION_IGNORE_CANCEL,
81 _("Couldn't flush buffer cache!"))
82 != PED_EXCEPTION_IGNORE)
83 return 0;
84 return 1;
85 }
86
87
88
89
90
91 static struct ext2_buffer_head *ext2_bh_alloc(struct ext2_buffer_cache *bc, blk_t block)
92 {
93 struct ext2_buffer_head *bh;
94 int i;
95
96 bh = NULL;
97
98 tryagain:
99 for (i=0;i<bc->size;i++)
100 {
101 bh = &bc->heads[i];
102
103 if (!bh->alloc)
104 break;
105 }
106
107 if (i == bc->size)
108 {
109 try_to_flush(bc);
110 goto tryagain;
111 }
112
113 bh = &bc->heads[i];
114
115 bh->next = NULL;
116 bh->prev = NULL;
117 bh->block = block;
118 bh->usecount = 0;
119 bh->dirty = 0;
120 bh->alloc = 1;
121 bc->numalloc++;
122
123 ext2_bh_hash(bh);
124
125 return bh;
126 }
127
128 static void ext2_bh_dealloc(struct ext2_buffer_head *bh)
129 {
130 if (bh->dirty)
131 ped_exception_throw (PED_EXCEPTION_BUG, PED_EXCEPTION_IGNORE,
132 "deallocing() a dirty buffer! %i\n", bh->block);
133
134 ext2_bh_unhash(bh);
135 bh->alloc = 0;
136 bh->bc->numalloc--;
137 }
138
139 static struct ext2_buffer_head *ext2_bh_find(struct ext2_buffer_cache *bc, blk_t block)
140 {
141 struct ext2_buffer_head *a;
142 struct ext2_buffer_head *b;
143 int hash;
144
145 hash = ext2_block_hash(block);
146 a = bc->hash[hash];
147
148 if (a != NULL)
149 {
150 b = a;
151 do
152 {
153 if (a->block == block)
154 return a;
155
156 a = a->next;
157 } while (a != b);
158 }
159
160 return NULL;
161 }
162
163 static int ext2_bh_do_read(struct ext2_buffer_head *bh)
164 {
165 return ext2_read_blocks(bh->bc->fs, bh->data, bh->block, 1);
166 }
167
168 static int ext2_bh_do_write(struct ext2_buffer_head *bh)
169 {
170 if (!bh->alloc) {
171 ped_exception_throw (PED_EXCEPTION_BUG, PED_EXCEPTION_CANCEL,
172 "Attempt to write unallocated buffer.");
173 return 0;
174 }
175
176 ext2_write_blocks(bh->bc->fs, bh->data, bh->block, 1);
177 bh->dirty = 0;
178 return 1;
179 }
180
181 static void ext2_bh_hash(struct ext2_buffer_head *bh)
182 {
183 int hash;
184
185 hash = ext2_block_hash(bh->block);
186 if (bh->bc->hash[hash] != NULL)
187 {
188 bh->next = bh->bc->hash[hash];
189 bh->prev = bh->next->prev;
190 bh->next->prev = bh;
191 bh->prev->next = bh;
192 return;
193 }
194
195 bh->bc->hash[hash] = bh;
196 bh->next = bh->prev = bh;
197 }
198
199 static void ext2_bh_unhash(struct ext2_buffer_head *bh)
200 {
201 int hash;
202
203 hash = ext2_block_hash(bh->block);
204
205 bh->prev->next = bh->next;
206 bh->next->prev = bh->prev;
207
208 if (bh->bc->hash[hash] == bh)
209 {
210 if (bh->next != bh)
211 bh->bc->hash[hash] = bh->next;
212 else
213 bh->bc->hash[hash] = NULL;
214 }
215
216 bh->next = NULL;
217 bh->prev = NULL;
218 }
219
220
221
222
223
224
225
226 static int breadimmhits = 0;
227 static int breadindhits = 0;
228 static int breadmisses = 0;
229
230 void ext2_bcache_deinit(struct ext2_fs *fs)
231 {
232 ext2_bcache_sync(fs);
233 ped_free(fs->bc->buffermem);
234 ped_free(fs->bc->hash);
235 ped_free(fs->bc->heads);
236 ped_free(fs->bc);
237
238 if (fs->opt_verbose)
239 fprintf(stderr,
240 "direct hits: %i, indirect hits: %i, misses: %i\n",
241 breadimmhits,
242 breadindhits,
243 breadmisses);
244 }
245
246 void ext2_bcache_dump(struct ext2_fs *fs)
247 {
248 int i;
249
250 fputs ("buffer cache dump:\n", stderr);
251
252 for (i=0;i<(1<<ext2_hash_bits);i++)
253 if (fs->bc->hash[i] != NULL)
254 {
255 struct ext2_buffer_head *a;
256 struct ext2_buffer_head *b;
257
258 fprintf(stderr, "%i: ", i);
259
260 a = b = fs->bc->hash[i];
261 do
262 {
263 fprintf(stderr, "%i ", a->block);
264 a = a->next;
265 } while (a != b);
266
267 fputc ('\n', stderr);
268 }
269 }
270
271 int ext2_bcache_flush(struct ext2_fs *fs, blk_t block)
272 {
273 struct ext2_buffer_head *bh;
274
275 if ((bh = ext2_bh_find(fs->bc, block)) == NULL)
276 return 1;
277
278 if (bh->usecount) {
279 ped_exception_throw (PED_EXCEPTION_BUG, PED_EXCEPTION_CANCEL,
280 "Attempt to flush a buffer that's in use! [%i,%i]",
281 bh->block, bh->usecount);
282 return 0;
283 }
284
285 if (bh->dirty) {
286 if (!ext2_bh_do_write(bh))
287 return 0;
288 }
289
290 ext2_bh_dealloc(bh);
291 return 1;
292 }
293
294 int ext2_bcache_flush_range(struct ext2_fs *fs, blk_t block, blk_t num)
295 {
296 blk_t end = block + num;
297
298 for (; block < end; block++) {
299 if (!ext2_bcache_flush(fs, block))
300 return 0;
301 }
302 return 1;
303 }
304
305 int ext2_bcache_init(struct ext2_fs *fs)
306 {
307 struct ext2_buffer_cache *bc;
308 int i;
309 int size;
310
311 size = ext2_buffer_cache_pool_size >> (fs->logsize - 10);
312
313 if ((bc = (struct ext2_buffer_cache *) ped_malloc(sizeof(struct ext2_buffer_cache))) == NULL)
314 return 0;
315
316 if ((bc->heads = (struct ext2_buffer_head *) ped_malloc(size * sizeof(struct ext2_buffer_head))) == NULL)
317 return 0;
318
319 if ((bc->hash = (struct ext2_buffer_head **) ped_malloc(sizeof(struct ext2_buffer_head *) << ext2_hash_bits)) == NULL)
320 {
321 ped_free(bc->heads);
322 ped_free(bc);
323 return 0;
324 }
325
326 if ((bc->buffermem = (unsigned char *) ped_malloc(ext2_buffer_cache_pool_size << 10)) == NULL)
327 {
328 ped_free(bc->hash);
329 ped_free(bc->heads);
330 ped_free(bc);
331 return 0;
332 }
333
334 bc->cache = &bc->heads[0];
335 bc->fs = fs;
336 bc->size = size;
337 bc->numalloc = 0;
338
339 for (i=0;i<size;i++)
340 {
341 bc->heads[i].data = bc->buffermem + (i << fs->logsize);
342 bc->heads[i].bc = bc;
343 bc->heads[i].alloc = 0;
344 }
345
346 for (i=0;i<(1<<ext2_hash_bits);i++)
347 bc->hash[i] = NULL;
348
349 fs->bc = bc;
350
351 return 1;
352 }
353
354 int ext2_bcache_sync(struct ext2_fs *fs)
355 {
356 int i;
357
358 for (i=0;i<fs->bc->size;i++)
359 {
360 struct ext2_buffer_head *bh;
361
362 bh = &fs->bc->heads[i];
363
364 if (bh->alloc && bh->dirty) {
365 if (!ext2_bh_do_write(bh))
366 return 0;
367 }
368 }
369 return 1;
370 }
371
372
373
374
375
376
377
378
379 struct ext2_buffer_head *ext2_bcreate(struct ext2_fs *fs, blk_t block)
380 {
381 struct ext2_buffer_head *bh;
382
383 if ((bh = ext2_bh_find(fs->bc, block)) != NULL)
384 {
385 bh->usecount++;
386 }
387 else
388 {
389 bh = ext2_bh_alloc(fs->bc, block);
390 bh->usecount = 1;
391 }
392
393 memset(bh->data, 0, fs->blocksize);
394 bh->dirty = 1;
395
396 return bh;
397 }
398
399 struct ext2_buffer_head *ext2_bread(struct ext2_fs *fs, blk_t block)
400 {
401 struct ext2_buffer_head *bh;
402
403 if ((bh = fs->bc->cache)->block == block)
404 {
405 breadimmhits++;
406 bh->usecount++;
407 return bh;
408 }
409
410 if ((bh = ext2_bh_find(fs->bc, block)) != NULL)
411 {
412 fs->bc->cache = bh;
413 breadindhits++;
414 bh->usecount++;
415 return bh;
416 }
417
418 breadmisses++;
419
420 bh = ext2_bh_alloc(fs->bc, block);
421 fs->bc->cache = bh;
422 bh->usecount = 1;
423 if (!ext2_bh_do_read(bh)) {
424 ext2_bh_dealloc(bh);
425 return NULL;
426 }
427
428 return bh;
429 }
430
431 int ext2_brelse(struct ext2_buffer_head *bh, int forget)
432 {
433 if (bh->usecount-- == 1 && forget)
434 {
435 if (bh->dirty) {
436 if (!ext2_bh_do_write(bh))
437 return 0;
438 }
439
440 ext2_bh_dealloc(bh);
441 }
442 return 1;
443 }
444
445 #endif /* !DISCOVER_ONLY */
446