xref: /minix3/minix/fs/ext2/ialloc.c (revision 0314acfb2d68447dfa1b0b33aa4c25b1cbfa85d3)
1433d6423SLionel Sambuc /* This files manages inodes allocation and deallocation.
2433d6423SLionel Sambuc  *
3433d6423SLionel Sambuc  * The entry points into this file are:
4433d6423SLionel Sambuc  *   alloc_inode:  allocate a new, unused inode.
5433d6423SLionel Sambuc  *   free_inode:   mark an inode as available for a new file.
6433d6423SLionel Sambuc  *
7433d6423SLionel Sambuc  * Created (alloc_inode/free_inode/wipe_inode are from MFS):
8433d6423SLionel Sambuc  *   June 2010 (Evgeniy Ivanov)
9433d6423SLionel Sambuc  */
10433d6423SLionel Sambuc 
11433d6423SLionel Sambuc #include "fs.h"
12433d6423SLionel Sambuc #include <string.h>
13433d6423SLionel Sambuc #include <stdlib.h>
14433d6423SLionel Sambuc #include <minix/com.h>
15433d6423SLionel Sambuc #include <minix/u64.h>
16433d6423SLionel Sambuc #include "buf.h"
17433d6423SLionel Sambuc #include "inode.h"
18433d6423SLionel Sambuc #include "super.h"
19433d6423SLionel Sambuc #include "const.h"
20433d6423SLionel Sambuc 
21433d6423SLionel Sambuc 
22433d6423SLionel Sambuc static bit_t alloc_inode_bit(struct super_block *sp, struct inode
23433d6423SLionel Sambuc 	*parent, int is_dir);
24433d6423SLionel Sambuc static void free_inode_bit(struct super_block *sp, bit_t bit_returned,
25433d6423SLionel Sambuc 	int is_dir);
26433d6423SLionel Sambuc static void wipe_inode(struct inode *rip);
27433d6423SLionel Sambuc 
28433d6423SLionel Sambuc 
29433d6423SLionel Sambuc /*===========================================================================*
30433d6423SLionel Sambuc  *                alloc_inode                                                *
31433d6423SLionel Sambuc  *===========================================================================*/
alloc_inode(struct inode * parent,mode_t bits,uid_t uid,gid_t gid)32970d95ecSDavid van Moolenbroek struct inode *alloc_inode(struct inode *parent, mode_t bits, uid_t uid,
33970d95ecSDavid van Moolenbroek 	gid_t gid)
34433d6423SLionel Sambuc {
35433d6423SLionel Sambuc /* Allocate a free inode on parent's dev, and return a pointer to it. */
36433d6423SLionel Sambuc 
37433d6423SLionel Sambuc   register struct inode *rip;
38433d6423SLionel Sambuc   register struct super_block *sp;
39433d6423SLionel Sambuc   int inumb;
40433d6423SLionel Sambuc   bit_t b;
41433d6423SLionel Sambuc   static int print_oos_msg = 1;
42433d6423SLionel Sambuc 
43433d6423SLionel Sambuc   sp = get_super(parent->i_dev);    /* get pointer to super_block */
44433d6423SLionel Sambuc   if (sp->s_rd_only) {    /* can't allocate an inode on a read only device. */
45433d6423SLionel Sambuc 	err_code = EROFS;
46433d6423SLionel Sambuc 	return(NULL);
47433d6423SLionel Sambuc   }
48433d6423SLionel Sambuc 
49433d6423SLionel Sambuc   /* Acquire an inode from the bit map. */
50433d6423SLionel Sambuc   b = alloc_inode_bit(sp, parent, (bits & I_TYPE) == I_DIRECTORY);
51433d6423SLionel Sambuc   if (b == NO_BIT) {
52433d6423SLionel Sambuc 	err_code = ENOSPC;
53433d6423SLionel Sambuc 	if (print_oos_msg)
54433d6423SLionel Sambuc 		ext2_debug("Out of i-nodes on device %d/%d\n",
55433d6423SLionel Sambuc 			   major(sp->s_dev), minor(sp->s_dev));
56433d6423SLionel Sambuc 	print_oos_msg = 0;	/* Don't repeat message */
57433d6423SLionel Sambuc 	return(NULL);
58433d6423SLionel Sambuc   }
59433d6423SLionel Sambuc   print_oos_msg = 1;
60433d6423SLionel Sambuc 
61433d6423SLionel Sambuc   inumb = (int) b;        /* be careful not to pass unshort as param */
62433d6423SLionel Sambuc 
63433d6423SLionel Sambuc   /* Try to acquire a slot in the inode table. */
64433d6423SLionel Sambuc   if ((rip = get_inode(NO_DEV, inumb)) == NULL) {
65433d6423SLionel Sambuc 	/* No inode table slots available.  Free the inode just allocated. */
66433d6423SLionel Sambuc 	free_inode_bit(sp, b, (bits & I_TYPE) == I_DIRECTORY);
67433d6423SLionel Sambuc   } else {
68433d6423SLionel Sambuc 	/* An inode slot is available. Put the inode just allocated into it. */
69433d6423SLionel Sambuc 	rip->i_mode = bits;         /* set up RWX bits */
70433d6423SLionel Sambuc 	rip->i_links_count = NO_LINK; /* initial no links */
71970d95ecSDavid van Moolenbroek 	rip->i_uid = uid;           /* file's uid is owner's */
72970d95ecSDavid van Moolenbroek 	rip->i_gid = gid;           /* ditto group id */
73433d6423SLionel Sambuc 	rip->i_dev = parent->i_dev; /* mark which device it is on */
74433d6423SLionel Sambuc 	rip->i_sp = sp;             /* pointer to super block */
75433d6423SLionel Sambuc 
76433d6423SLionel Sambuc 	/* Fields not cleared already are cleared in wipe_inode(). They have
77433d6423SLionel Sambuc 	 * been put there because truncate() needs to clear the same fields if
78433d6423SLionel Sambuc 	 * the file happens to be open while being truncated. It saves space
79433d6423SLionel Sambuc 	 * not to repeat the code twice.
80433d6423SLionel Sambuc 	 */
81433d6423SLionel Sambuc 	wipe_inode(rip);
82433d6423SLionel Sambuc   }
83433d6423SLionel Sambuc 
84433d6423SLionel Sambuc   return(rip);
85433d6423SLionel Sambuc }
86433d6423SLionel Sambuc 
87433d6423SLionel Sambuc 
88433d6423SLionel Sambuc /*===========================================================================*
89433d6423SLionel Sambuc  *                free_inode                                                 *
90433d6423SLionel Sambuc  *===========================================================================*/
free_inode(register struct inode * rip)91433d6423SLionel Sambuc void free_inode(
92433d6423SLionel Sambuc   register struct inode *rip  /* inode to free */
93433d6423SLionel Sambuc )
94433d6423SLionel Sambuc {
95433d6423SLionel Sambuc /* Return an inode to the pool of unallocated inodes. */
96433d6423SLionel Sambuc   register struct super_block *sp;
97433d6423SLionel Sambuc   dev_t dev = rip->i_dev;
98433d6423SLionel Sambuc   bit_t b = rip->i_num;
99433d6423SLionel Sambuc   u16_t mode = rip->i_mode;
100433d6423SLionel Sambuc 
101433d6423SLionel Sambuc   /* Locate the appropriate super_block. */
102433d6423SLionel Sambuc   sp = get_super(dev);
103433d6423SLionel Sambuc 
104433d6423SLionel Sambuc   if (b <= NO_ENTRY || b > sp->s_inodes_count)
105433d6423SLionel Sambuc 	return;
106433d6423SLionel Sambuc   free_inode_bit(sp, b, (mode & I_TYPE) == I_DIRECTORY);
107433d6423SLionel Sambuc 
108433d6423SLionel Sambuc   rip->i_mode = I_NOT_ALLOC;     /* clear I_TYPE field */
109433d6423SLionel Sambuc }
110433d6423SLionel Sambuc 
111433d6423SLionel Sambuc 
112433d6423SLionel Sambuc static int find_group_dir(struct super_block *sp);
113433d6423SLionel Sambuc static int find_group_hashalloc(struct super_block *sp, struct inode
114433d6423SLionel Sambuc 	*parent);
115433d6423SLionel Sambuc static int find_group_any(struct super_block *sp);
116433d6423SLionel Sambuc static int find_group_orlov(struct super_block *sp, struct inode
117433d6423SLionel Sambuc 	*parent);
118433d6423SLionel Sambuc 
119433d6423SLionel Sambuc 
120433d6423SLionel Sambuc /*===========================================================================*
121433d6423SLionel Sambuc  *                              alloc_inode_bit                              *
122433d6423SLionel Sambuc  *===========================================================================*/
alloc_inode_bit(sp,parent,is_dir)123433d6423SLionel Sambuc static bit_t alloc_inode_bit(sp, parent, is_dir)
124433d6423SLionel Sambuc struct super_block *sp;         /* the filesystem to allocate from */
125433d6423SLionel Sambuc struct inode *parent;		/* parent of newly allocated inode */
126433d6423SLionel Sambuc int is_dir;			/* inode will be a directory if it is TRUE */
127433d6423SLionel Sambuc {
128433d6423SLionel Sambuc   int group;
129433d6423SLionel Sambuc   ino_t inumber = NO_BIT;
130433d6423SLionel Sambuc   bit_t bit;
131433d6423SLionel Sambuc   struct buf *bp;
132433d6423SLionel Sambuc   struct group_desc *gd;
133433d6423SLionel Sambuc 
134433d6423SLionel Sambuc   if (sp->s_rd_only)
135433d6423SLionel Sambuc 	panic("can't alloc inode on read-only filesys.");
136433d6423SLionel Sambuc 
137433d6423SLionel Sambuc   if (opt.mfsalloc) {
138433d6423SLionel Sambuc 	group = find_group_any(sp);
139433d6423SLionel Sambuc   } else {
140433d6423SLionel Sambuc 	if (is_dir) {
141433d6423SLionel Sambuc 		if (opt.use_orlov) {
142433d6423SLionel Sambuc 			group = find_group_orlov(sp, parent);
143433d6423SLionel Sambuc 		} else {
144433d6423SLionel Sambuc 			group = find_group_dir(sp);
145433d6423SLionel Sambuc 		}
146433d6423SLionel Sambuc 	} else {
147433d6423SLionel Sambuc 		group = find_group_hashalloc(sp, parent);
148433d6423SLionel Sambuc 	}
149433d6423SLionel Sambuc   }
150433d6423SLionel Sambuc   /* Check if we have a group where to allocate an inode */
151433d6423SLionel Sambuc   if (group == -1)
152433d6423SLionel Sambuc 	return(NO_BIT);	/* no bit could be allocated */
153433d6423SLionel Sambuc 
154433d6423SLionel Sambuc   gd = get_group_desc(group);
155433d6423SLionel Sambuc   if (gd == NULL)
156433d6423SLionel Sambuc 	  panic("can't get group_desc to alloc block");
157433d6423SLionel Sambuc 
158433d6423SLionel Sambuc   /* find_group_* should always return either a group with
159433d6423SLionel Sambuc    * a free inode slot or -1, which we checked earlier.
160433d6423SLionel Sambuc    */
161433d6423SLionel Sambuc   ASSERT(gd->free_inodes_count);
162433d6423SLionel Sambuc 
163433d6423SLionel Sambuc   bp = get_block(sp->s_dev, gd->inode_bitmap, NORMAL);
164433d6423SLionel Sambuc   bit = setbit(b_bitmap(bp), sp->s_inodes_per_group, 0);
165433d6423SLionel Sambuc   ASSERT(bit != -1); /* group definitly contains free inode */
166433d6423SLionel Sambuc 
167433d6423SLionel Sambuc   inumber = group * sp->s_inodes_per_group + bit + 1;
168433d6423SLionel Sambuc 
169433d6423SLionel Sambuc   /* Extra checks before real allocation.
170433d6423SLionel Sambuc    * Only major bug can cause problems. Since setbit changed
171433d6423SLionel Sambuc    * bp->b_bitmap there is no way to recover from this bug.
172433d6423SLionel Sambuc    * Should never happen.
173433d6423SLionel Sambuc    */
174433d6423SLionel Sambuc   if (inumber > sp->s_inodes_count) {
175433d6423SLionel Sambuc 	panic("ext2: allocator returned inum greater, than\
176433d6423SLionel Sambuc 		    total number of inodes.\n");
177433d6423SLionel Sambuc   }
178433d6423SLionel Sambuc 
179433d6423SLionel Sambuc   if (inumber < EXT2_FIRST_INO(sp)) {
180433d6423SLionel Sambuc 	panic("ext2: allocator tryed to use reserved inode.\n");
181433d6423SLionel Sambuc   }
182433d6423SLionel Sambuc 
183433d6423SLionel Sambuc   lmfs_markdirty(bp);
184*0314acfbSDavid van Moolenbroek   put_block(bp);
185433d6423SLionel Sambuc 
186433d6423SLionel Sambuc   gd->free_inodes_count--;
187433d6423SLionel Sambuc   sp->s_free_inodes_count--;
188433d6423SLionel Sambuc   if (is_dir) {
189433d6423SLionel Sambuc 	gd->used_dirs_count++;
190433d6423SLionel Sambuc 	sp->s_dirs_counter++;
191433d6423SLionel Sambuc   }
192433d6423SLionel Sambuc 
193433d6423SLionel Sambuc   group_descriptors_dirty = 1;
194433d6423SLionel Sambuc 
195433d6423SLionel Sambuc   /* Almost the same as previous 'group' ASSERT */
196433d6423SLionel Sambuc   ASSERT(inumber != NO_BIT);
197433d6423SLionel Sambuc   return inumber;
198433d6423SLionel Sambuc }
199433d6423SLionel Sambuc 
200433d6423SLionel Sambuc 
201433d6423SLionel Sambuc /*===========================================================================*
202433d6423SLionel Sambuc  *                          free_inode_bit                                   *
203433d6423SLionel Sambuc  *===========================================================================*/
free_inode_bit(struct super_block * sp,bit_t bit_returned,int is_dir)204433d6423SLionel Sambuc static void free_inode_bit(struct super_block *sp, bit_t bit_returned,
205433d6423SLionel Sambuc                            int is_dir)
206433d6423SLionel Sambuc {
207433d6423SLionel Sambuc  /* Return an inode by turning off its bitmap bit. */
208433d6423SLionel Sambuc   int group;		/* group number of bit_returned */
209433d6423SLionel Sambuc   int bit;		/* bit_returned number within its group */
210433d6423SLionel Sambuc   struct buf *bp;
211433d6423SLionel Sambuc   struct group_desc *gd;
212433d6423SLionel Sambuc 
213433d6423SLionel Sambuc   if (sp->s_rd_only)
214433d6423SLionel Sambuc 	panic("can't free bit on read-only filesys.");
215433d6423SLionel Sambuc 
216433d6423SLionel Sambuc   /* At first search group, to which bit_returned belongs to
217433d6423SLionel Sambuc    * and figure out in what word bit is stored.
218433d6423SLionel Sambuc    */
219433d6423SLionel Sambuc   if (bit_returned > sp->s_inodes_count ||
220433d6423SLionel Sambuc       bit_returned < EXT2_FIRST_INO(sp))
221433d6423SLionel Sambuc 	panic("trying to free inode %d beyond inodes scope.", bit_returned);
222433d6423SLionel Sambuc 
223433d6423SLionel Sambuc   group = (bit_returned - 1) / sp->s_inodes_per_group;
224433d6423SLionel Sambuc   bit = (bit_returned - 1) % sp->s_inodes_per_group; /* index in bitmap */
225433d6423SLionel Sambuc 
226433d6423SLionel Sambuc   gd = get_group_desc(group);
227433d6423SLionel Sambuc   if (gd == NULL)
228433d6423SLionel Sambuc 	panic("can't get group_desc to alloc block");
229433d6423SLionel Sambuc 
230433d6423SLionel Sambuc   bp = get_block(sp->s_dev, gd->inode_bitmap, NORMAL);
231433d6423SLionel Sambuc 
232433d6423SLionel Sambuc   if (unsetbit(b_bitmap(bp), bit))
233433d6423SLionel Sambuc 	panic("Tried to free unused inode %d", bit_returned);
234433d6423SLionel Sambuc 
235433d6423SLionel Sambuc   lmfs_markdirty(bp);
236*0314acfbSDavid van Moolenbroek   put_block(bp);
237433d6423SLionel Sambuc 
238433d6423SLionel Sambuc   gd->free_inodes_count++;
239433d6423SLionel Sambuc   sp->s_free_inodes_count++;
240433d6423SLionel Sambuc 
241433d6423SLionel Sambuc   if (is_dir) {
242433d6423SLionel Sambuc 	gd->used_dirs_count--;
243433d6423SLionel Sambuc 	sp->s_dirs_counter--;
244433d6423SLionel Sambuc   }
245433d6423SLionel Sambuc 
246433d6423SLionel Sambuc   group_descriptors_dirty = 1;
247433d6423SLionel Sambuc 
248433d6423SLionel Sambuc   if (group < sp->s_igsearch)
249433d6423SLionel Sambuc 	sp->s_igsearch = group;
250433d6423SLionel Sambuc }
251433d6423SLionel Sambuc 
252433d6423SLionel Sambuc 
253433d6423SLionel Sambuc /* it's implemented very close to the linux' find_group_dir() */
find_group_dir(struct super_block * sp)254433d6423SLionel Sambuc static int find_group_dir(struct super_block *sp)
255433d6423SLionel Sambuc {
256433d6423SLionel Sambuc   int avefreei = sp->s_free_inodes_count / sp->s_groups_count;
257433d6423SLionel Sambuc   struct group_desc *gd, *best_gd = NULL;
258433d6423SLionel Sambuc   int group, best_group = -1;
259433d6423SLionel Sambuc 
260433d6423SLionel Sambuc   for (group = 0; group < sp->s_groups_count; ++group) {
261433d6423SLionel Sambuc 	gd = get_group_desc(group);
262433d6423SLionel Sambuc 	if (gd == NULL)
263433d6423SLionel Sambuc 		panic("can't get group_desc to alloc inode");
264433d6423SLionel Sambuc 	if (gd->free_inodes_count == 0)
265433d6423SLionel Sambuc 		continue;
266433d6423SLionel Sambuc 	if (gd->free_inodes_count < avefreei)
267433d6423SLionel Sambuc 		continue;
268433d6423SLionel Sambuc 	if (!best_gd ||
269433d6423SLionel Sambuc 	     gd->free_blocks_count > best_gd->free_blocks_count) {
270433d6423SLionel Sambuc 		best_gd = gd;
271433d6423SLionel Sambuc 		best_group = group;
272433d6423SLionel Sambuc 	}
273433d6423SLionel Sambuc   }
274433d6423SLionel Sambuc 
275433d6423SLionel Sambuc   return best_group; /* group or -1 */
276433d6423SLionel Sambuc }
277433d6423SLionel Sambuc 
278433d6423SLionel Sambuc 
279433d6423SLionel Sambuc /* Analog of ffs_hashalloc() from *BSD.
280433d6423SLionel Sambuc  * 1) Check parent's for free inodes and blocks.
281433d6423SLionel Sambuc  * 2) Quadradically rehash on the group number.
282433d6423SLionel Sambuc  * 3) Make a linear search for free inode.
283433d6423SLionel Sambuc  */
find_group_hashalloc(struct super_block * sp,struct inode * parent)284433d6423SLionel Sambuc static int find_group_hashalloc(struct super_block *sp, struct inode *parent)
285433d6423SLionel Sambuc {
286433d6423SLionel Sambuc   int ngroups = sp->s_groups_count;
287433d6423SLionel Sambuc   struct group_desc *gd;
288433d6423SLionel Sambuc   int group, i;
289433d6423SLionel Sambuc   int parent_group = (parent->i_num - 1) / sp->s_inodes_per_group;
290433d6423SLionel Sambuc 
291433d6423SLionel Sambuc   /* Try to place new inode in its parent group */
292433d6423SLionel Sambuc   gd = get_group_desc(parent_group);
293433d6423SLionel Sambuc   if (gd == NULL)
294433d6423SLionel Sambuc 	panic("can't get group_desc to alloc inode");
295433d6423SLionel Sambuc   if (gd->free_inodes_count && gd->free_blocks_count)
296433d6423SLionel Sambuc 	return parent_group;
297433d6423SLionel Sambuc 
298433d6423SLionel Sambuc   /* We can't allocate inode in the parent's group.
299433d6423SLionel Sambuc    * Now we will try to place it in another blockgroup.
300433d6423SLionel Sambuc    * The main idea is still to keep files from the same
301433d6423SLionel Sambuc    * directory together and use different blockgroups for
302433d6423SLionel Sambuc    * files from another directory, which lives in the same
303433d6423SLionel Sambuc    * blockgroup as our parent.
304433d6423SLionel Sambuc    * Thus we will spread things on the disk.
305433d6423SLionel Sambuc    */
306433d6423SLionel Sambuc   group = (parent_group + parent->i_num) % ngroups;
307433d6423SLionel Sambuc 
308433d6423SLionel Sambuc   /* Make quadratic probing to find a group with free inodes and blocks. */
309433d6423SLionel Sambuc   for (i = 1; i < ngroups; i <<= 1) {
310433d6423SLionel Sambuc 	group += i;
311433d6423SLionel Sambuc 	if (group >= ngroups)
312433d6423SLionel Sambuc 		group -= ngroups;
313433d6423SLionel Sambuc 	gd = get_group_desc(group);
314433d6423SLionel Sambuc 	if (gd == NULL)
315433d6423SLionel Sambuc 		panic("can't get group_desc to alloc inode");
316433d6423SLionel Sambuc 	if (gd->free_inodes_count && gd->free_blocks_count)
317433d6423SLionel Sambuc 		return group;
318433d6423SLionel Sambuc   }
319433d6423SLionel Sambuc 
320433d6423SLionel Sambuc   /* Still no group for new inode, try linear search.
321433d6423SLionel Sambuc    * Also check parent again (but for free inodes only).
322433d6423SLionel Sambuc    */
323433d6423SLionel Sambuc   group = parent_group;
324433d6423SLionel Sambuc   for (i = 0; i < ngroups; i++, group++) {
325433d6423SLionel Sambuc 	if (group >= ngroups)
326433d6423SLionel Sambuc 		group = 0;
327433d6423SLionel Sambuc 	gd = get_group_desc(group);
328433d6423SLionel Sambuc 	if (gd == NULL)
329433d6423SLionel Sambuc 		panic("can't get group_desc to alloc inode");
330433d6423SLionel Sambuc 	if (gd->free_inodes_count)
331433d6423SLionel Sambuc 		return group;
332433d6423SLionel Sambuc   }
333433d6423SLionel Sambuc 
334433d6423SLionel Sambuc   return -1;
335433d6423SLionel Sambuc }
336433d6423SLionel Sambuc 
337433d6423SLionel Sambuc 
338433d6423SLionel Sambuc /* Find first group which has free inode slot.
339433d6423SLionel Sambuc  * This is similar to what MFS does.
340433d6423SLionel Sambuc  */
find_group_any(struct super_block * sp)341433d6423SLionel Sambuc static int find_group_any(struct super_block *sp)
342433d6423SLionel Sambuc {
343433d6423SLionel Sambuc   int ngroups = sp->s_groups_count;
344433d6423SLionel Sambuc   struct group_desc *gd;
345433d6423SLionel Sambuc   int group = sp->s_igsearch;
346433d6423SLionel Sambuc 
347433d6423SLionel Sambuc   for (; group < ngroups; group++) {
348433d6423SLionel Sambuc 	gd = get_group_desc(group);
349433d6423SLionel Sambuc 	if (gd == NULL)
350433d6423SLionel Sambuc 		panic("can't get group_desc to alloc inode");
351433d6423SLionel Sambuc 	if (gd->free_inodes_count) {
352433d6423SLionel Sambuc 		sp->s_igsearch = group;
353433d6423SLionel Sambuc 		return group;
354433d6423SLionel Sambuc 	}
355433d6423SLionel Sambuc   }
356433d6423SLionel Sambuc 
357433d6423SLionel Sambuc   return -1;
358433d6423SLionel Sambuc }
359433d6423SLionel Sambuc 
360433d6423SLionel Sambuc 
361433d6423SLionel Sambuc /* We try to spread first-level directories (i.e. directories in the root
362433d6423SLionel Sambuc  * or in the directory marked as TOPDIR).
363433d6423SLionel Sambuc  * If there are blockgroups with counts for blocks and inodes less than average
364433d6423SLionel Sambuc  * we return a group with lowest directory count. Otherwise we either
365433d6423SLionel Sambuc  * return a group with good free inodes and blocks counts or just a group
366433d6423SLionel Sambuc  * with free inode.
367433d6423SLionel Sambuc  *
368433d6423SLionel Sambuc  * For other directories we try to find a 'good' group, we consider a group as
369433d6423SLionel Sambuc  * a 'good' if it has enough blocks and inodes (greater than min_blocks and
370433d6423SLionel Sambuc  * min_inodes).
371433d6423SLionel Sambuc  *
372433d6423SLionel Sambuc  */
find_group_orlov(struct super_block * sp,struct inode * parent)373433d6423SLionel Sambuc static int find_group_orlov(struct super_block *sp, struct inode *parent)
374433d6423SLionel Sambuc {
375433d6423SLionel Sambuc   int avefreei = sp->s_free_inodes_count / sp->s_groups_count;
376433d6423SLionel Sambuc   int avefreeb = sp->s_free_blocks_count / sp->s_groups_count;
377433d6423SLionel Sambuc 
378433d6423SLionel Sambuc   int group = -1;
379433d6423SLionel Sambuc   int fallback_group = -1; /* Group with at least 1 free inode */
380433d6423SLionel Sambuc   struct group_desc *gd;
381433d6423SLionel Sambuc   int i;
382433d6423SLionel Sambuc 
383433d6423SLionel Sambuc   if (parent->i_num == ROOT_INODE ||
384433d6423SLionel Sambuc       parent->i_flags & EXT2_TOPDIR_FL) {
385433d6423SLionel Sambuc 	int best_group = -1;
386433d6423SLionel Sambuc 	int best_avefree_group = -1; /* Best value of avefreei/avefreeb */
387433d6423SLionel Sambuc 	int best_ndir = sp->s_inodes_per_group;
388433d6423SLionel Sambuc 
389433d6423SLionel Sambuc 	group = (unsigned int)random();
390433d6423SLionel Sambuc 	for (i = 0; i < sp->s_groups_count; i++, group++) {
391433d6423SLionel Sambuc 		if (group >= sp->s_groups_count)
392433d6423SLionel Sambuc 			group = 0;
393433d6423SLionel Sambuc 		gd = get_group_desc(group);
394433d6423SLionel Sambuc 		if (gd == NULL)
395433d6423SLionel Sambuc 			panic("can't get group_desc to alloc inode");
396433d6423SLionel Sambuc 		if (gd->free_inodes_count == 0)
397433d6423SLionel Sambuc 			continue;
398433d6423SLionel Sambuc 
399433d6423SLionel Sambuc 		fallback_group = group;
400433d6423SLionel Sambuc 
401433d6423SLionel Sambuc 		if (gd->free_inodes_count < avefreei ||
402433d6423SLionel Sambuc 		    gd->free_blocks_count < avefreeb)
403433d6423SLionel Sambuc 			continue;
404433d6423SLionel Sambuc 
405433d6423SLionel Sambuc 		best_avefree_group  = group;
406433d6423SLionel Sambuc 
407433d6423SLionel Sambuc 		if (gd->used_dirs_count >= best_ndir)
408433d6423SLionel Sambuc 			continue;
409433d6423SLionel Sambuc 		best_ndir = gd->used_dirs_count;
410433d6423SLionel Sambuc 		best_group = group;
411433d6423SLionel Sambuc 	}
412433d6423SLionel Sambuc 	if (best_group >= 0)
413433d6423SLionel Sambuc 		return best_group;
414433d6423SLionel Sambuc 	if (best_avefree_group >= 0)
415433d6423SLionel Sambuc 		return best_avefree_group;
416433d6423SLionel Sambuc 	return fallback_group;
417433d6423SLionel Sambuc   } else {
418433d6423SLionel Sambuc 	int parent_group = (parent->i_num - 1) / sp->s_inodes_per_group;
419433d6423SLionel Sambuc 	/* 2 is kind of random thing for now,
420433d6423SLionel Sambuc 	 * but performance results are still good.
421433d6423SLionel Sambuc 	 */
422433d6423SLionel Sambuc 	int min_blocks = avefreeb / 2;
423433d6423SLionel Sambuc 	int min_inodes = avefreei / 2;
424433d6423SLionel Sambuc 
425433d6423SLionel Sambuc 	group = parent_group;
426433d6423SLionel Sambuc 	for (i = 0; i < sp->s_groups_count; i++, group++) {
427433d6423SLionel Sambuc 		if (group >= sp->s_groups_count)
428433d6423SLionel Sambuc 			group = 0;
429433d6423SLionel Sambuc 		gd = get_group_desc(group);
430433d6423SLionel Sambuc 		if (gd == NULL)
431433d6423SLionel Sambuc 			panic("can't get group_desc to alloc inode");
432433d6423SLionel Sambuc 		if (gd->free_inodes_count == 0)
433433d6423SLionel Sambuc 			continue;
434433d6423SLionel Sambuc 
435433d6423SLionel Sambuc 		fallback_group = group;
436433d6423SLionel Sambuc 
437433d6423SLionel Sambuc 		if (gd->free_inodes_count >= min_inodes &&
438433d6423SLionel Sambuc 		    gd->free_blocks_count >= min_blocks)
439433d6423SLionel Sambuc 			return group;
440433d6423SLionel Sambuc 	}
441433d6423SLionel Sambuc 	return fallback_group;
442433d6423SLionel Sambuc   }
443433d6423SLionel Sambuc 
444433d6423SLionel Sambuc   return -1;
445433d6423SLionel Sambuc }
446433d6423SLionel Sambuc 
447433d6423SLionel Sambuc 
448433d6423SLionel Sambuc /*===========================================================================*
449433d6423SLionel Sambuc  *                wipe_inode                                                 *
450433d6423SLionel Sambuc  *===========================================================================*/
wipe_inode(register struct inode * rip)451433d6423SLionel Sambuc static void wipe_inode(
452433d6423SLionel Sambuc   register struct inode *rip     /* the inode to be erased */
453433d6423SLionel Sambuc )
454433d6423SLionel Sambuc {
455433d6423SLionel Sambuc /* Erase some fields in the inode. This function is called from alloc_inode()
456433d6423SLionel Sambuc  * when a new inode is to be allocated, and from truncate(), when an existing
457433d6423SLionel Sambuc  * inode is to be truncated.
458433d6423SLionel Sambuc  */
459433d6423SLionel Sambuc 
460433d6423SLionel Sambuc   register int i;
461433d6423SLionel Sambuc 
462433d6423SLionel Sambuc   rip->i_size = 0;
463433d6423SLionel Sambuc   rip->i_update = ATIME | CTIME | MTIME;    /* update all times later */
464433d6423SLionel Sambuc   rip->i_blocks = 0;
465433d6423SLionel Sambuc   rip->i_flags = 0;
466433d6423SLionel Sambuc   rip->i_generation = 0;
467433d6423SLionel Sambuc   rip->i_file_acl = 0;
468433d6423SLionel Sambuc   rip->i_dir_acl = 0;
469433d6423SLionel Sambuc   rip->i_faddr = 0;
470433d6423SLionel Sambuc 
471433d6423SLionel Sambuc   for (i = 0; i < EXT2_N_BLOCKS; i++)
472433d6423SLionel Sambuc 	rip->i_block[i] = NO_BLOCK;
473433d6423SLionel Sambuc   rip->i_block[0] = NO_BLOCK;
474433d6423SLionel Sambuc 
475433d6423SLionel Sambuc   rip->i_dirt = IN_DIRTY;
476433d6423SLionel Sambuc }
477