1 /* This files manages inodes allocation and deallocation.
2 *
3 * The entry points into this file are:
4 * alloc_inode: allocate a new, unused inode.
5 * free_inode: mark an inode as available for a new file.
6 *
7 * Created (alloc_inode/free_inode/wipe_inode are from MFS):
8 * June 2010 (Evgeniy Ivanov)
9 */
10
11 #include "fs.h"
12 #include <string.h>
13 #include <stdlib.h>
14 #include <minix/com.h>
15 #include <minix/u64.h>
16 #include "buf.h"
17 #include "inode.h"
18 #include "super.h"
19 #include "const.h"
20
21
22 static bit_t alloc_inode_bit(struct super_block *sp, struct inode
23 *parent, int is_dir);
24 static void free_inode_bit(struct super_block *sp, bit_t bit_returned,
25 int is_dir);
26 static void wipe_inode(struct inode *rip);
27
28
29 /*===========================================================================*
30 * alloc_inode *
31 *===========================================================================*/
alloc_inode(struct inode * parent,mode_t bits,uid_t uid,gid_t gid)32 struct inode *alloc_inode(struct inode *parent, mode_t bits, uid_t uid,
33 gid_t gid)
34 {
35 /* Allocate a free inode on parent's dev, and return a pointer to it. */
36
37 register struct inode *rip;
38 register struct super_block *sp;
39 int inumb;
40 bit_t b;
41 static int print_oos_msg = 1;
42
43 sp = get_super(parent->i_dev); /* get pointer to super_block */
44 if (sp->s_rd_only) { /* can't allocate an inode on a read only device. */
45 err_code = EROFS;
46 return(NULL);
47 }
48
49 /* Acquire an inode from the bit map. */
50 b = alloc_inode_bit(sp, parent, (bits & I_TYPE) == I_DIRECTORY);
51 if (b == NO_BIT) {
52 err_code = ENOSPC;
53 if (print_oos_msg)
54 ext2_debug("Out of i-nodes on device %d/%d\n",
55 major(sp->s_dev), minor(sp->s_dev));
56 print_oos_msg = 0; /* Don't repeat message */
57 return(NULL);
58 }
59 print_oos_msg = 1;
60
61 inumb = (int) b; /* be careful not to pass unshort as param */
62
63 /* Try to acquire a slot in the inode table. */
64 if ((rip = get_inode(NO_DEV, inumb)) == NULL) {
65 /* No inode table slots available. Free the inode just allocated. */
66 free_inode_bit(sp, b, (bits & I_TYPE) == I_DIRECTORY);
67 } else {
68 /* An inode slot is available. Put the inode just allocated into it. */
69 rip->i_mode = bits; /* set up RWX bits */
70 rip->i_links_count = NO_LINK; /* initial no links */
71 rip->i_uid = uid; /* file's uid is owner's */
72 rip->i_gid = gid; /* ditto group id */
73 rip->i_dev = parent->i_dev; /* mark which device it is on */
74 rip->i_sp = sp; /* pointer to super block */
75
76 /* Fields not cleared already are cleared in wipe_inode(). They have
77 * been put there because truncate() needs to clear the same fields if
78 * the file happens to be open while being truncated. It saves space
79 * not to repeat the code twice.
80 */
81 wipe_inode(rip);
82 }
83
84 return(rip);
85 }
86
87
88 /*===========================================================================*
89 * free_inode *
90 *===========================================================================*/
free_inode(register struct inode * rip)91 void free_inode(
92 register struct inode *rip /* inode to free */
93 )
94 {
95 /* Return an inode to the pool of unallocated inodes. */
96 register struct super_block *sp;
97 dev_t dev = rip->i_dev;
98 bit_t b = rip->i_num;
99 u16_t mode = rip->i_mode;
100
101 /* Locate the appropriate super_block. */
102 sp = get_super(dev);
103
104 if (b <= NO_ENTRY || b > sp->s_inodes_count)
105 return;
106 free_inode_bit(sp, b, (mode & I_TYPE) == I_DIRECTORY);
107
108 rip->i_mode = I_NOT_ALLOC; /* clear I_TYPE field */
109 }
110
111
112 static int find_group_dir(struct super_block *sp);
113 static int find_group_hashalloc(struct super_block *sp, struct inode
114 *parent);
115 static int find_group_any(struct super_block *sp);
116 static int find_group_orlov(struct super_block *sp, struct inode
117 *parent);
118
119
120 /*===========================================================================*
121 * alloc_inode_bit *
122 *===========================================================================*/
alloc_inode_bit(sp,parent,is_dir)123 static bit_t alloc_inode_bit(sp, parent, is_dir)
124 struct super_block *sp; /* the filesystem to allocate from */
125 struct inode *parent; /* parent of newly allocated inode */
126 int is_dir; /* inode will be a directory if it is TRUE */
127 {
128 int group;
129 ino_t inumber = NO_BIT;
130 bit_t bit;
131 struct buf *bp;
132 struct group_desc *gd;
133
134 if (sp->s_rd_only)
135 panic("can't alloc inode on read-only filesys.");
136
137 if (opt.mfsalloc) {
138 group = find_group_any(sp);
139 } else {
140 if (is_dir) {
141 if (opt.use_orlov) {
142 group = find_group_orlov(sp, parent);
143 } else {
144 group = find_group_dir(sp);
145 }
146 } else {
147 group = find_group_hashalloc(sp, parent);
148 }
149 }
150 /* Check if we have a group where to allocate an inode */
151 if (group == -1)
152 return(NO_BIT); /* no bit could be allocated */
153
154 gd = get_group_desc(group);
155 if (gd == NULL)
156 panic("can't get group_desc to alloc block");
157
158 /* find_group_* should always return either a group with
159 * a free inode slot or -1, which we checked earlier.
160 */
161 ASSERT(gd->free_inodes_count);
162
163 bp = get_block(sp->s_dev, gd->inode_bitmap, NORMAL);
164 bit = setbit(b_bitmap(bp), sp->s_inodes_per_group, 0);
165 ASSERT(bit != -1); /* group definitly contains free inode */
166
167 inumber = group * sp->s_inodes_per_group + bit + 1;
168
169 /* Extra checks before real allocation.
170 * Only major bug can cause problems. Since setbit changed
171 * bp->b_bitmap there is no way to recover from this bug.
172 * Should never happen.
173 */
174 if (inumber > sp->s_inodes_count) {
175 panic("ext2: allocator returned inum greater, than\
176 total number of inodes.\n");
177 }
178
179 if (inumber < EXT2_FIRST_INO(sp)) {
180 panic("ext2: allocator tryed to use reserved inode.\n");
181 }
182
183 lmfs_markdirty(bp);
184 put_block(bp);
185
186 gd->free_inodes_count--;
187 sp->s_free_inodes_count--;
188 if (is_dir) {
189 gd->used_dirs_count++;
190 sp->s_dirs_counter++;
191 }
192
193 group_descriptors_dirty = 1;
194
195 /* Almost the same as previous 'group' ASSERT */
196 ASSERT(inumber != NO_BIT);
197 return inumber;
198 }
199
200
201 /*===========================================================================*
202 * free_inode_bit *
203 *===========================================================================*/
free_inode_bit(struct super_block * sp,bit_t bit_returned,int is_dir)204 static void free_inode_bit(struct super_block *sp, bit_t bit_returned,
205 int is_dir)
206 {
207 /* Return an inode by turning off its bitmap bit. */
208 int group; /* group number of bit_returned */
209 int bit; /* bit_returned number within its group */
210 struct buf *bp;
211 struct group_desc *gd;
212
213 if (sp->s_rd_only)
214 panic("can't free bit on read-only filesys.");
215
216 /* At first search group, to which bit_returned belongs to
217 * and figure out in what word bit is stored.
218 */
219 if (bit_returned > sp->s_inodes_count ||
220 bit_returned < EXT2_FIRST_INO(sp))
221 panic("trying to free inode %d beyond inodes scope.", bit_returned);
222
223 group = (bit_returned - 1) / sp->s_inodes_per_group;
224 bit = (bit_returned - 1) % sp->s_inodes_per_group; /* index in bitmap */
225
226 gd = get_group_desc(group);
227 if (gd == NULL)
228 panic("can't get group_desc to alloc block");
229
230 bp = get_block(sp->s_dev, gd->inode_bitmap, NORMAL);
231
232 if (unsetbit(b_bitmap(bp), bit))
233 panic("Tried to free unused inode %d", bit_returned);
234
235 lmfs_markdirty(bp);
236 put_block(bp);
237
238 gd->free_inodes_count++;
239 sp->s_free_inodes_count++;
240
241 if (is_dir) {
242 gd->used_dirs_count--;
243 sp->s_dirs_counter--;
244 }
245
246 group_descriptors_dirty = 1;
247
248 if (group < sp->s_igsearch)
249 sp->s_igsearch = group;
250 }
251
252
253 /* it's implemented very close to the linux' find_group_dir() */
find_group_dir(struct super_block * sp)254 static int find_group_dir(struct super_block *sp)
255 {
256 int avefreei = sp->s_free_inodes_count / sp->s_groups_count;
257 struct group_desc *gd, *best_gd = NULL;
258 int group, best_group = -1;
259
260 for (group = 0; group < sp->s_groups_count; ++group) {
261 gd = get_group_desc(group);
262 if (gd == NULL)
263 panic("can't get group_desc to alloc inode");
264 if (gd->free_inodes_count == 0)
265 continue;
266 if (gd->free_inodes_count < avefreei)
267 continue;
268 if (!best_gd ||
269 gd->free_blocks_count > best_gd->free_blocks_count) {
270 best_gd = gd;
271 best_group = group;
272 }
273 }
274
275 return best_group; /* group or -1 */
276 }
277
278
279 /* Analog of ffs_hashalloc() from *BSD.
280 * 1) Check parent's for free inodes and blocks.
281 * 2) Quadradically rehash on the group number.
282 * 3) Make a linear search for free inode.
283 */
find_group_hashalloc(struct super_block * sp,struct inode * parent)284 static int find_group_hashalloc(struct super_block *sp, struct inode *parent)
285 {
286 int ngroups = sp->s_groups_count;
287 struct group_desc *gd;
288 int group, i;
289 int parent_group = (parent->i_num - 1) / sp->s_inodes_per_group;
290
291 /* Try to place new inode in its parent group */
292 gd = get_group_desc(parent_group);
293 if (gd == NULL)
294 panic("can't get group_desc to alloc inode");
295 if (gd->free_inodes_count && gd->free_blocks_count)
296 return parent_group;
297
298 /* We can't allocate inode in the parent's group.
299 * Now we will try to place it in another blockgroup.
300 * The main idea is still to keep files from the same
301 * directory together and use different blockgroups for
302 * files from another directory, which lives in the same
303 * blockgroup as our parent.
304 * Thus we will spread things on the disk.
305 */
306 group = (parent_group + parent->i_num) % ngroups;
307
308 /* Make quadratic probing to find a group with free inodes and blocks. */
309 for (i = 1; i < ngroups; i <<= 1) {
310 group += i;
311 if (group >= ngroups)
312 group -= ngroups;
313 gd = get_group_desc(group);
314 if (gd == NULL)
315 panic("can't get group_desc to alloc inode");
316 if (gd->free_inodes_count && gd->free_blocks_count)
317 return group;
318 }
319
320 /* Still no group for new inode, try linear search.
321 * Also check parent again (but for free inodes only).
322 */
323 group = parent_group;
324 for (i = 0; i < ngroups; i++, group++) {
325 if (group >= ngroups)
326 group = 0;
327 gd = get_group_desc(group);
328 if (gd == NULL)
329 panic("can't get group_desc to alloc inode");
330 if (gd->free_inodes_count)
331 return group;
332 }
333
334 return -1;
335 }
336
337
338 /* Find first group which has free inode slot.
339 * This is similar to what MFS does.
340 */
find_group_any(struct super_block * sp)341 static int find_group_any(struct super_block *sp)
342 {
343 int ngroups = sp->s_groups_count;
344 struct group_desc *gd;
345 int group = sp->s_igsearch;
346
347 for (; group < ngroups; group++) {
348 gd = get_group_desc(group);
349 if (gd == NULL)
350 panic("can't get group_desc to alloc inode");
351 if (gd->free_inodes_count) {
352 sp->s_igsearch = group;
353 return group;
354 }
355 }
356
357 return -1;
358 }
359
360
361 /* We try to spread first-level directories (i.e. directories in the root
362 * or in the directory marked as TOPDIR).
363 * If there are blockgroups with counts for blocks and inodes less than average
364 * we return a group with lowest directory count. Otherwise we either
365 * return a group with good free inodes and blocks counts or just a group
366 * with free inode.
367 *
368 * For other directories we try to find a 'good' group, we consider a group as
369 * a 'good' if it has enough blocks and inodes (greater than min_blocks and
370 * min_inodes).
371 *
372 */
find_group_orlov(struct super_block * sp,struct inode * parent)373 static int find_group_orlov(struct super_block *sp, struct inode *parent)
374 {
375 int avefreei = sp->s_free_inodes_count / sp->s_groups_count;
376 int avefreeb = sp->s_free_blocks_count / sp->s_groups_count;
377
378 int group = -1;
379 int fallback_group = -1; /* Group with at least 1 free inode */
380 struct group_desc *gd;
381 int i;
382
383 if (parent->i_num == ROOT_INODE ||
384 parent->i_flags & EXT2_TOPDIR_FL) {
385 int best_group = -1;
386 int best_avefree_group = -1; /* Best value of avefreei/avefreeb */
387 int best_ndir = sp->s_inodes_per_group;
388
389 group = (unsigned int)random();
390 for (i = 0; i < sp->s_groups_count; i++, group++) {
391 if (group >= sp->s_groups_count)
392 group = 0;
393 gd = get_group_desc(group);
394 if (gd == NULL)
395 panic("can't get group_desc to alloc inode");
396 if (gd->free_inodes_count == 0)
397 continue;
398
399 fallback_group = group;
400
401 if (gd->free_inodes_count < avefreei ||
402 gd->free_blocks_count < avefreeb)
403 continue;
404
405 best_avefree_group = group;
406
407 if (gd->used_dirs_count >= best_ndir)
408 continue;
409 best_ndir = gd->used_dirs_count;
410 best_group = group;
411 }
412 if (best_group >= 0)
413 return best_group;
414 if (best_avefree_group >= 0)
415 return best_avefree_group;
416 return fallback_group;
417 } else {
418 int parent_group = (parent->i_num - 1) / sp->s_inodes_per_group;
419 /* 2 is kind of random thing for now,
420 * but performance results are still good.
421 */
422 int min_blocks = avefreeb / 2;
423 int min_inodes = avefreei / 2;
424
425 group = parent_group;
426 for (i = 0; i < sp->s_groups_count; i++, group++) {
427 if (group >= sp->s_groups_count)
428 group = 0;
429 gd = get_group_desc(group);
430 if (gd == NULL)
431 panic("can't get group_desc to alloc inode");
432 if (gd->free_inodes_count == 0)
433 continue;
434
435 fallback_group = group;
436
437 if (gd->free_inodes_count >= min_inodes &&
438 gd->free_blocks_count >= min_blocks)
439 return group;
440 }
441 return fallback_group;
442 }
443
444 return -1;
445 }
446
447
448 /*===========================================================================*
449 * wipe_inode *
450 *===========================================================================*/
wipe_inode(register struct inode * rip)451 static void wipe_inode(
452 register struct inode *rip /* the inode to be erased */
453 )
454 {
455 /* Erase some fields in the inode. This function is called from alloc_inode()
456 * when a new inode is to be allocated, and from truncate(), when an existing
457 * inode is to be truncated.
458 */
459
460 register int i;
461
462 rip->i_size = 0;
463 rip->i_update = ATIME | CTIME | MTIME; /* update all times later */
464 rip->i_blocks = 0;
465 rip->i_flags = 0;
466 rip->i_generation = 0;
467 rip->i_file_acl = 0;
468 rip->i_dir_acl = 0;
469 rip->i_faddr = 0;
470
471 for (i = 0; i < EXT2_N_BLOCKS; i++)
472 rip->i_block[i] = NO_BLOCK;
473 rip->i_block[0] = NO_BLOCK;
474
475 rip->i_dirt = IN_DIRTY;
476 }
477