1 /* This files manages blocks allocation and deallocation.
2 *
3 * The entry points into this file are:
4 * discard_preallocated_blocks: Discard preallocated blocks.
5 * alloc_block: somebody wants to allocate a block; find one.
6 * free_block: indicate that a block is available for new allocation.
7 *
8 * Created:
9 * June 2010 (Evgeniy Ivanov)
10 */
11
12 #include "fs.h"
13 #include <string.h>
14 #include <stdlib.h>
15 #include <minix/com.h>
16 #include <minix/u64.h>
17 #include "buf.h"
18 #include "inode.h"
19 #include "super.h"
20 #include "const.h"
21
22
23 static block_t alloc_block_bit(struct super_block *sp, block_t origin,
24 struct inode *rip);
25
26 /*===========================================================================*
27 * discard_preallocated_blocks *
28 *===========================================================================*/
discard_preallocated_blocks(struct inode * rip)29 void discard_preallocated_blocks(struct inode *rip)
30 {
31 /* When called for rip, discard (free) blocks preallocated for rip,
32 * otherwise discard all preallocated blocks.
33 * Normally it should be called in following situations:
34 * 1. File is closed.
35 * 2. File is truncated.
36 * 3. Non-sequential write.
37 * 4. inode is "unloaded" from the memory.
38 * 5. No free blocks left (discard all preallocated blocks).
39 */
40 int i;
41
42 if (rip) {
43 rip->i_prealloc_count = rip->i_prealloc_index = 0;
44 for (i = 0; i < EXT2_PREALLOC_BLOCKS; i++) {
45 if (rip->i_prealloc_blocks[i] != NO_BLOCK) {
46 free_block(rip->i_sp, rip->i_prealloc_blocks[i]);
47 rip->i_prealloc_blocks[i] = NO_BLOCK;
48 }
49 }
50 return;
51 }
52
53 /* Discard all allocated blocks.
54 * Probably there are just few blocks on the disc, so forbid preallocation.*/
55 for(rip = &inode[0]; rip < &inode[NR_INODES]; rip++) {
56 rip->i_prealloc_count = rip->i_prealloc_index = 0;
57 rip->i_preallocation = 0; /* forbid preallocation */
58 for (i = 0; i < EXT2_PREALLOC_BLOCKS; i++) {
59 if (rip->i_prealloc_blocks[i] != NO_BLOCK) {
60 free_block(rip->i_sp, rip->i_prealloc_blocks[i]);
61 rip->i_prealloc_blocks[i] = NO_BLOCK;
62 }
63 }
64 }
65 }
66
67
68 /*===========================================================================*
69 * alloc_block *
70 *===========================================================================*/
alloc_block(struct inode * rip,block_t block)71 block_t alloc_block(struct inode *rip, block_t block)
72 {
73 /* Allocate a block for inode. If block is provided, then use it as a goal:
74 * try to allocate this block or his neghbors.
75 * If block is not provided then goal is group, where inode lives.
76 */
77 block_t goal;
78 block_t b;
79 struct super_block *sp = rip->i_sp;
80
81 if (sp->s_rd_only)
82 panic("can't alloc block on read-only filesys.");
83
84 /* Check for free blocks. First time discard preallocation,
85 * next time return NO_BLOCK
86 */
87 if (!opt.use_reserved_blocks &&
88 sp->s_free_blocks_count <= sp->s_r_blocks_count) {
89 discard_preallocated_blocks(NULL);
90 } else if (sp->s_free_blocks_count <= EXT2_PREALLOC_BLOCKS) {
91 discard_preallocated_blocks(NULL);
92 }
93
94 if (!opt.use_reserved_blocks &&
95 sp->s_free_blocks_count <= sp->s_r_blocks_count) {
96 return(NO_BLOCK);
97 } else if (sp->s_free_blocks_count == 0) {
98 return(NO_BLOCK);
99 }
100
101 if (block != NO_BLOCK) {
102 goal = block;
103 if (rip->i_preallocation && rip->i_prealloc_count > 0) {
104 /* check if goal is preallocated */
105 b = rip->i_prealloc_blocks[rip->i_prealloc_index];
106 if (block == b || (block + 1) == b) {
107 /* use preallocated block */
108 rip->i_prealloc_blocks[rip->i_prealloc_index] = NO_BLOCK;
109 rip->i_prealloc_count--;
110 rip->i_prealloc_index++;
111 if (rip->i_prealloc_index >= EXT2_PREALLOC_BLOCKS) {
112 rip->i_prealloc_index = 0;
113 ASSERT(rip->i_prealloc_count == 0);
114 }
115 rip->i_bsearch = b;
116 return b;
117 } else {
118 /* probably non-sequential write operation,
119 * disable preallocation for this inode.
120 */
121 rip->i_preallocation = 0;
122 discard_preallocated_blocks(rip);
123 }
124 }
125 } else {
126 int group = (rip->i_num - 1) / sp->s_inodes_per_group;
127 goal = sp->s_blocks_per_group*group + sp->s_first_data_block;
128 }
129
130 if (rip->i_preallocation && rip->i_prealloc_count) {
131 ext2_debug("There're preallocated blocks, but they're\
132 neither used or freed!");
133 }
134
135 b = alloc_block_bit(sp, goal, rip);
136
137 if (b != NO_BLOCK)
138 rip->i_bsearch = b;
139
140 return b;
141 }
142
143
144 static void check_block_number(block_t block, struct super_block *sp,
145 struct group_desc *gd);
146
147 /*===========================================================================*
148 * alloc_block_bit *
149 *===========================================================================*/
alloc_block_bit(sp,goal,rip)150 static block_t alloc_block_bit(sp, goal, rip)
151 struct super_block *sp; /* the filesystem to allocate from */
152 block_t goal; /* try to allocate near this block */
153 struct inode *rip; /* used for preallocation */
154 {
155 block_t block = NO_BLOCK; /* allocated block */
156 int word; /* word in block bitmap */
157 bit_t bit = -1;
158 int group;
159 char update_bsearch = FALSE;
160 int i;
161
162 if (goal >= sp->s_blocks_count ||
163 (goal < sp->s_first_data_block && goal != 0)) {
164 goal = sp->s_bsearch;
165 }
166
167 if (goal <= sp->s_bsearch) {
168 /* No reason to search in a place with no free blocks */
169 goal = sp->s_bsearch;
170 update_bsearch = TRUE;
171 }
172
173 /* Figure out where to start the bit search. */
174 word = ((goal - sp->s_first_data_block) % sp->s_blocks_per_group)
175 / FS_BITCHUNK_BITS;
176
177 /* Try to allocate block at any group starting from the goal's group.
178 * First time goal's group is checked from the word=goal, after all
179 * groups checked, it's checked again from word=0, that's why "i <=".
180 */
181 group = (goal - sp->s_first_data_block) / sp->s_blocks_per_group;
182 for (i = 0; i <= sp->s_groups_count; i++, group++) {
183 struct buf *bp;
184 struct group_desc *gd;
185
186 if (group >= sp->s_groups_count)
187 group = 0;
188
189 gd = get_group_desc(group);
190 if (gd == NULL)
191 panic("can't get group_desc to alloc block");
192
193 if (gd->free_blocks_count == 0) {
194 word = 0;
195 continue;
196 }
197
198 bp = get_block(sp->s_dev, gd->block_bitmap, NORMAL);
199
200 if (rip->i_preallocation &&
201 gd->free_blocks_count >= (EXT2_PREALLOC_BLOCKS * 4) ) {
202 /* Try to preallocate blocks */
203 if (rip->i_prealloc_count != 0) {
204 /* kind of glitch... */
205 discard_preallocated_blocks(rip);
206 ext2_debug("warning, discarding previously preallocated\
207 blocks! It had to be done by another code.");
208 }
209 ASSERT(rip->i_prealloc_count == 0);
210 /* we preallocate bytes only */
211 ASSERT(EXT2_PREALLOC_BLOCKS == sizeof(char)*CHAR_BIT);
212
213 bit = setbyte(b_bitmap(bp), sp->s_blocks_per_group);
214 if (bit != -1) {
215 block = bit + sp->s_first_data_block +
216 group * sp->s_blocks_per_group;
217 check_block_number(block, sp, gd);
218
219 /* We preallocate a byte starting from block.
220 * First preallocated block will be returned as
221 * normally allocated block.
222 */
223 for (i = 1; i < EXT2_PREALLOC_BLOCKS; i++) {
224 check_block_number(block + i, sp, gd);
225 rip->i_prealloc_blocks[i-1] = block + i;
226 }
227 rip->i_prealloc_index = 0;
228 rip->i_prealloc_count = EXT2_PREALLOC_BLOCKS - 1;
229
230 lmfs_markdirty(bp);
231 put_block(bp);
232
233 gd->free_blocks_count -= EXT2_PREALLOC_BLOCKS;
234 sp->s_free_blocks_count -= EXT2_PREALLOC_BLOCKS;
235 lmfs_change_blockusage(EXT2_PREALLOC_BLOCKS);
236 group_descriptors_dirty = 1;
237 return block;
238 }
239 }
240
241 bit = setbit(b_bitmap(bp), sp->s_blocks_per_group, word);
242 if (bit == -1) {
243 if (word == 0) {
244 panic("ext2: allocator failed to allocate a bit in bitmap\
245 with free bits.");
246 } else {
247 word = 0;
248 continue;
249 }
250 }
251
252 block = sp->s_first_data_block + group * sp->s_blocks_per_group + bit;
253 check_block_number(block, sp, gd);
254
255 lmfs_markdirty(bp);
256 put_block(bp);
257
258 gd->free_blocks_count--;
259 sp->s_free_blocks_count--;
260 lmfs_change_blockusage(1);
261 group_descriptors_dirty = 1;
262
263 if (update_bsearch && block != -1 && block != NO_BLOCK) {
264 /* We searched from the beginning, update bsearch. */
265 sp->s_bsearch = block;
266 }
267
268 return block;
269 }
270
271 return block;
272 }
273
274
275 /*===========================================================================*
276 * free_block *
277 *===========================================================================*/
free_block(struct super_block * sp,bit_t bit_returned)278 void free_block(struct super_block *sp, bit_t bit_returned)
279 {
280 /* Return a block by turning off its bitmap bit. */
281 int group; /* group number of bit_returned */
282 int bit; /* bit_returned number within its group */
283 struct buf *bp;
284 struct group_desc *gd;
285
286 if (sp->s_rd_only)
287 panic("can't free bit on read-only filesys.");
288
289 if (bit_returned >= sp->s_blocks_count ||
290 bit_returned < sp->s_first_data_block)
291 panic("trying to free block %d beyond blocks scope.",
292 bit_returned);
293
294 /* At first search group, to which bit_returned belongs to
295 * and figure out in what word bit is stored.
296 */
297 group = (bit_returned - sp->s_first_data_block) / sp->s_blocks_per_group;
298 bit = (bit_returned - sp->s_first_data_block) % sp->s_blocks_per_group;
299
300 gd = get_group_desc(group);
301 if (gd == NULL)
302 panic("can't get group_desc to alloc block");
303
304 /* We might be buggy (No way! :P), so check if we deallocate
305 * data block, but not control (system) block.
306 * This should never happen.
307 */
308 if (bit_returned == gd->inode_bitmap || bit_returned == gd->block_bitmap
309 || (bit_returned >= gd->inode_table
310 && bit_returned < (gd->inode_table + sp->s_itb_per_group))) {
311 ext2_debug("ext2: freeing non-data block %d\n", bit_returned);
312 panic("trying to deallocate \
313 system/control block, hardly poke author.");
314 }
315
316 bp = get_block(sp->s_dev, gd->block_bitmap, NORMAL);
317
318 if (unsetbit(b_bitmap(bp), bit))
319 panic("Tried to free unused block %d", bit_returned);
320
321 lmfs_markdirty(bp);
322 put_block(bp);
323
324 gd->free_blocks_count++;
325 sp->s_free_blocks_count++;
326 lmfs_change_blockusage(-1);
327
328 group_descriptors_dirty = 1;
329
330 if (bit_returned < sp->s_bsearch)
331 sp->s_bsearch = bit_returned;
332
333 /* Also tell libminixfs, so that 1) if it has this block in its cache, it can
334 * mark it as clean, thus reducing useless writes, and 2) it can tell VM that
335 * any previous inode association is to be broken for this block, so that the
336 * block will not be mapped in erroneously later on.
337 */
338 lmfs_free_block(sp->s_dev, (block_t)bit_returned);
339 }
340
341
check_block_number(block_t block,struct super_block * sp,struct group_desc * gd)342 static void check_block_number(block_t block, struct super_block *sp,
343 struct group_desc *gd)
344 {
345
346 /* Check if we allocated a data block, but not control (system) block.
347 * Only major bug can cause us to allocate wrong block. If it happens,
348 * we panic (and don't bloat filesystem's bitmap).
349 */
350 if (block == gd->inode_bitmap || block == gd->block_bitmap ||
351 (block >= gd->inode_table
352 && block < (gd->inode_table + sp->s_itb_per_group))) {
353 ext2_debug("ext2: allocating non-data block %d\n", block);
354 panic("ext2: block allocator tryed to return \
355 system/control block, poke author.\n");
356 }
357
358 if (block >= sp->s_blocks_count) {
359 panic("ext2: allocator returned blocknum greater, than \
360 total number of blocks.\n");
361 }
362 }
363