1/* 2 * linux/fs/ufs/ialloc.c 3 * 4 * Copyright (c) 1998 5 * Daniel Pirkl <daniel.pirkl@email.cz> 6 * Charles University, Faculty of Mathematics and Physics 7 * 8 * from 9 * 10 * linux/fs/ext2/ialloc.c 11 * 12 * Copyright (C) 1992, 1993, 1994, 1995 13 * Remy Card (card@masi.ibp.fr) 14 * Laboratoire MASI - Institut Blaise Pascal 15 * Universite Pierre et Marie Curie (Paris VI) 16 * 17 * BSD ufs-inspired inode and directory allocation by 18 * Stephen Tweedie (sct@dcs.ed.ac.uk), 1993 19 * Big-endian to little-endian byte-swapping/bitmaps by 20 * David S. Miller (davem@caip.rutgers.edu), 1995 21 */ 22 23#include <linux/fs.h> 24#include <linux/ufs_fs.h> 25#include <linux/sched.h> 26#include <linux/stat.h> 27#include <linux/string.h> 28#include <linux/locks.h> 29#include <linux/quotaops.h> 30#include <asm/bitops.h> 31#include <asm/byteorder.h> 32 33#include "swab.h" 34#include "util.h" 35 36#undef UFS_IALLOC_DEBUG 37 38#ifdef UFS_IALLOC_DEBUG 39#define UFSD(x) printk("(%s, %d), %s: ", __FILE__, __LINE__, __FUNCTION__); printk x; 40#else 41#define UFSD(x) 42#endif 43 44/* 45 * NOTE! When we get the inode, we're the only people 46 * that have access to it, and as such there are no 47 * race conditions we have to worry about. The inode 48 * is not on the hash-lists, and it cannot be reached 49 * through the filesystem because the directory entry 50 * has been deleted earlier. 51 * 52 * HOWEVER: we must make sure that we get no aliases, 53 * which means that we have to call "clear_inode()" 54 * _before_ we mark the inode not in use in the inode 55 * bitmaps. Otherwise a newly created file might use 56 * the same inode number (not actually the same pointer 57 * though), and then we'd have two inodes sharing the 58 * same inode number and space on the harddisk. 59 */ 60void ufs_free_inode (struct inode * inode) 61{ 62 struct super_block * sb; 63 struct ufs_sb_private_info * uspi; 64 struct ufs_super_block_first * usb1; 65 struct ufs_cg_private_info * ucpi; 66 struct ufs_cylinder_group * ucg; 67 int is_directory; 68 unsigned ino, cg, bit; 69 70 UFSD(("ENTER, ino %lu\n", inode->i_ino)) 71 72 sb = inode->i_sb; 73 uspi = sb->u.ufs_sb.s_uspi; 74 usb1 = ubh_get_usb_first(USPI_UBH); 75 76 ino = inode->i_ino; 77 78 lock_super (sb); 79 80 if (!((ino > 1) && (ino < (uspi->s_ncg * uspi->s_ipg )))) { 81 ufs_warning(sb, "ufs_free_inode", "reserved inode or nonexistent inode %u\n", ino); 82 unlock_super (sb); 83 return; 84 } 85 86 cg = ufs_inotocg (ino); 87 bit = ufs_inotocgoff (ino); 88 ucpi = ufs_load_cylinder (sb, cg); 89 if (!ucpi) { 90 unlock_super (sb); 91 return; 92 } 93 ucg = ubh_get_ucg(UCPI_UBH); 94 if (!ufs_cg_chkmagic(sb, ucg)) 95 ufs_panic (sb, "ufs_free_fragments", "internal error, bad cg magic number"); 96 97 ucg->cg_time = cpu_to_fs32(sb, CURRENT_TIME); 98 99 is_directory = S_ISDIR(inode->i_mode); 100 101 DQUOT_FREE_INODE(inode); 102 DQUOT_DROP(inode); 103 104 clear_inode (inode); 105 106 if (ubh_isclr (UCPI_UBH, ucpi->c_iusedoff, bit)) 107 ufs_error(sb, "ufs_free_inode", "bit already cleared for inode %u", ino); 108 else { 109 ubh_clrbit (UCPI_UBH, ucpi->c_iusedoff, bit); 110 if (ino < ucpi->c_irotor) 111 ucpi->c_irotor = ino; 112 fs32_add(sb, &ucg->cg_cs.cs_nifree, 1); 113 fs32_add(sb, &usb1->fs_cstotal.cs_nifree, 1); 114 fs32_add(sb, &sb->fs_cs(cg).cs_nifree, 1); 115 116 if (is_directory) { 117 fs32_sub(sb, &ucg->cg_cs.cs_ndir, 1); 118 fs32_sub(sb, &usb1->fs_cstotal.cs_ndir, 1); 119 fs32_sub(sb, &sb->fs_cs(cg).cs_ndir, 1); 120 } 121 } 122 123 ubh_mark_buffer_dirty (USPI_UBH); 124 ubh_mark_buffer_dirty (UCPI_UBH); 125 if (sb->s_flags & MS_SYNCHRONOUS) { 126 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **) &ucpi); 127 ubh_wait_on_buffer (UCPI_UBH); 128 } 129 130 sb->s_dirt = 1; 131 unlock_super (sb); 132 UFSD(("EXIT\n")) 133} 134 135/* 136 * There are two policies for allocating an inode. If the new inode is 137 * a directory, then a forward search is made for a block group with both 138 * free space and a low directory-to-inode ratio; if that fails, then of 139 * the groups with above-average free space, that group with the fewest 140 * directories already is chosen. 141 * 142 * For other inodes, search forward from the parent directory's block 143 * group to find a free inode. 144 */ 145struct inode * ufs_new_inode (const struct inode * dir, int mode) 146{ 147 struct super_block * sb; 148 struct ufs_sb_private_info * uspi; 149 struct ufs_super_block_first * usb1; 150 struct ufs_cg_private_info * ucpi; 151 struct ufs_cylinder_group * ucg; 152 struct inode * inode; 153 unsigned cg, bit, i, j, start; 154 155 UFSD(("ENTER\n")) 156 157 /* Cannot create files in a deleted directory */ 158 if (!dir || !dir->i_nlink) 159 return ERR_PTR(-EPERM); 160 sb = dir->i_sb; 161 inode = new_inode(sb); 162 if (!inode) 163 return ERR_PTR(-ENOMEM); 164 uspi = sb->u.ufs_sb.s_uspi; 165 usb1 = ubh_get_usb_first(USPI_UBH); 166 167 lock_super (sb); 168 169 /* 170 * Try to place the inode in its parent directory 171 */ 172 i = ufs_inotocg(dir->i_ino); 173 if (sb->fs_cs(i).cs_nifree) { 174 cg = i; 175 goto cg_found; 176 } 177 178 /* 179 * Use a quadratic hash to find a group with a free inode 180 */ 181 for ( j = 1; j < uspi->s_ncg; j <<= 1 ) { 182 i += j; 183 if (i >= uspi->s_ncg) 184 i -= uspi->s_ncg; 185 if (sb->fs_cs(i).cs_nifree) { 186 cg = i; 187 goto cg_found; 188 } 189 } 190 191 /* 192 * That failed: try linear search for a free inode 193 */ 194 i = ufs_inotocg(dir->i_ino) + 1; 195 for (j = 2; j < uspi->s_ncg; j++) { 196 i++; 197 if (i >= uspi->s_ncg) 198 i = 0; 199 if (sb->fs_cs(i).cs_nifree) { 200 cg = i; 201 goto cg_found; 202 } 203 } 204 205 goto failed; 206 207cg_found: 208 ucpi = ufs_load_cylinder (sb, cg); 209 if (!ucpi) 210 goto failed; 211 ucg = ubh_get_ucg(UCPI_UBH); 212 if (!ufs_cg_chkmagic(sb, ucg)) 213 ufs_panic (sb, "ufs_new_inode", "internal error, bad cg magic number"); 214 215 start = ucpi->c_irotor; 216 bit = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_iusedoff, uspi->s_ipg, start); 217 if (!(bit < uspi->s_ipg)) { 218 bit = ubh_find_first_zero_bit (UCPI_UBH, ucpi->c_iusedoff, start); 219 if (!(bit < start)) { 220 ufs_error (sb, "ufs_new_inode", 221 "cylinder group %u corrupted - error in inode bitmap\n", cg); 222 goto failed; 223 } 224 } 225 UFSD(("start = %u, bit = %u, ipg = %u\n", start, bit, uspi->s_ipg)) 226 if (ubh_isclr (UCPI_UBH, ucpi->c_iusedoff, bit)) 227 ubh_setbit (UCPI_UBH, ucpi->c_iusedoff, bit); 228 else { 229 ufs_panic (sb, "ufs_new_inode", "internal error"); 230 goto failed; 231 } 232 233 fs32_sub(sb, &ucg->cg_cs.cs_nifree, 1); 234 fs32_sub(sb, &usb1->fs_cstotal.cs_nifree, 1); 235 fs32_sub(sb, &sb->fs_cs(cg).cs_nifree, 1); 236 237 if (S_ISDIR(mode)) { 238 fs32_add(sb, &ucg->cg_cs.cs_ndir, 1); 239 fs32_add(sb, &usb1->fs_cstotal.cs_ndir, 1); 240 fs32_add(sb, &sb->fs_cs(cg).cs_ndir, 1); 241 } 242 243 ubh_mark_buffer_dirty (USPI_UBH); 244 ubh_mark_buffer_dirty (UCPI_UBH); 245 if (sb->s_flags & MS_SYNCHRONOUS) { 246 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **) &ucpi); 247 ubh_wait_on_buffer (UCPI_UBH); 248 } 249 sb->s_dirt = 1; 250 251 inode->i_mode = mode; 252 inode->i_uid = current->fsuid; 253 if (dir->i_mode & S_ISGID) { 254 inode->i_gid = dir->i_gid; 255 if (S_ISDIR(mode)) 256 inode->i_mode |= S_ISGID; 257 } else 258 inode->i_gid = current->fsgid; 259 260 inode->i_ino = cg * uspi->s_ipg + bit; 261 inode->i_blksize = PAGE_SIZE; /* This is the optimal IO size (for stat), not the fs block size */ 262 inode->i_blocks = 0; 263 inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME; 264 inode->u.ufs_i.i_flags = dir->u.ufs_i.i_flags; 265 inode->u.ufs_i.i_lastfrag = 0; 266 267 insert_inode_hash(inode); 268 mark_inode_dirty(inode); 269 270 unlock_super (sb); 271 272 if (DQUOT_ALLOC_INODE(inode)) { 273 DQUOT_DROP(inode); 274 inode->i_flags |= S_NOQUOTA; 275 inode->i_nlink = 0; 276 iput(inode); 277 return ERR_PTR(-EDQUOT); 278 } 279 280 UFSD(("allocating inode %lu\n", inode->i_ino)) 281 UFSD(("EXIT\n")) 282 return inode; 283 284failed: 285 unlock_super (sb); 286 make_bad_inode(inode); 287 iput (inode); 288 UFSD(("EXIT (FAILED)\n")) 289 return ERR_PTR(-ENOSPC); 290} 291