Welcome to The Fiwix Project
A UNIX-like kernel for the i386 architecture
![[previous]](../icons/n_left.png){kind=icon}
![[next]](../icons/n_right.png){kind=icon}
![[first]](../icons/first.png){kind=icon}
![[last]](../icons/last.png){kind=icon}
![[top]](../icons/n_top.png){kind=icon}
![[bottom]](../icons/bottom.png){kind=icon}
![[index]](../icons/index.png){kind=icon}
![[help]](../icons/help.png){kind=icon}
*/
1 /* 2 * fiwix/fs/inode.c 3 * 4 * Copyright 2018-2021, Jordi Sanfeliu. All rights reserved. 5 * Distributed under the terms of the Fiwix License. 6 */ 7 8 /* 9 * inode.c implements a cache with a free list as a doubly circular linked 10 * list and a chained hash table with doubly linked lists. 11 * 12 * hash table 13 * +--------+ +--------------+ +--------------+ +--------------+ 14 * | index | |prev|data|next| |prev|data|next| |prev|data|next| 15 * | 0 --> | / | | ---> <--- | | ---> <--- | | / | 16 * +--------+ +--------------+ +--------------+ +--------------+ 17 * +--------+ +--------------+ +--------------+ +--------------+ 18 * | index | |prev|data|next| |prev|data|next| |prev|data|next| 19 * | 1 --> | / | | ---> <--- | | ---> <--- | | / | 20 * +--------+ +--------------+ +--------------+ +--------------+ 21 * (inode) (inode) (inode) 22 * ... 23 */ 24 25 #include <fiwix/asm.h> 26 #include <fiwix/kernel.h> 27 #include <fiwix/sleep.h> 28 #include <fiwix/sched.h> 29 #include <fiwix/fs.h> 30 #include <fiwix/filesystems.h> 31 #include <fiwix/stat.h> 32 #include <fiwix/errno.h> 33 #include <fiwix/mm.h> 34 #include <fiwix/stdio.h> 35 #include <fiwix/string.h> 36 37 #define INODE_HASH(dev, inode) (((__dev_t)(dev) ^ (__ino_t)(inode)) % (NR_INO_HASH)) 38 #define NR_INODES (inode_table_size / sizeof(struct inode)) 39 #define NR_INO_HASH (inode_hash_table_size / sizeof(unsigned int)) 40 41 struct inode *inode_table; /* inode pool */ 42 struct inode *inode_head; /* inode pool head */ 43 struct inode **inode_hash_table; 44 45 static struct resource sync_resource = { NULL, NULL }; 46 47 static void insert_to_hash(struct inode *i) 48 { 49 struct inode **h; 50 int n; 51 52 n = INODE_HASH(i->dev, i->inode); 53 h = &inode_hash_table[n]; 54 55 if(!*h) { 56 *h = i; 57 (*h)->prev_hash = (*h)->next_hash = NULL; 58 } else { 59 i->prev_hash = NULL; 60 i->next_hash = *h; 61 (*h)->prev_hash = i; 62 *h = i; 63 } 64 } 65 66 static void remove_from_hash(struct inode *i) 67 { 68 struct inode **h; 69 int n; 70 71 if(!i->inode) { 72 return; 73 } 74 75 n = INODE_HASH(i->dev, i->inode); 76 h = &inode_hash_table[n]; 77 78 while(*h) { 79 if(*h == i) { 80 if((*h)->next_hash) { 81 (*h)->next_hash->prev_hash = (*h)->prev_hash; 82 } 83 if((*h)->prev_hash) { 84 (*h)->prev_hash->next_hash = (*h)->next_hash; 85 } 86 if(h == &inode_hash_table[n]) { 87 *h = (*h)->next_hash; 88 } 89 break; 90 } 91 h = &(*h)->next_hash; 92 } 93 } 94 95 static void insert_on_free_list(struct inode *i) 96 { 97 if(!inode_head) { 98 i->prev_free = i->next_free = i; 99 inode_head = i; 100 } else { 101 i->next_free = inode_head; 102 i->prev_free = inode_head->prev_free; 103 inode_head->prev_free->next_free = i; 104 inode_head->prev_free = i; 105 } 106 107 kstat.free_inodes++; 108 } 109 110 static void remove_from_free_list(struct inode *i) 111 { 112 if(!kstat.free_inodes) { 113 return; 114 } 115 116 i->prev_free->next_free = i->next_free; 117 i->next_free->prev_free = i->prev_free; 118 kstat.free_inodes--; 119 if(i == inode_head) { 120 inode_head = i->next_free; 121 } 122 123 if(!kstat.free_inodes) { 124 inode_head = NULL; 125 } 126 } 127 128 static struct inode * get_free_inode(void) 129 { 130 unsigned long int flags; 131 struct inode *i; 132 133 /* no more inodes on free list */ 134 if(!kstat.free_inodes) { 135 return NULL; 136 } 137 138 SAVE_FLAGS(flags); CLI(); 139 140 i = inode_head; 141 remove_from_free_list(i); 142 remove_from_hash(i); 143 i->i_mode = 0; 144 i->i_uid = 0; 145 i->i_size = 0; 146 i->i_atime = 0; 147 i->i_ctime = 0; 148 i->i_mtime = 0; 149 i->i_gid = 0; 150 i->i_nlink = 0; 151 i->i_blocks = 0; 152 i->i_flags = 0; 153 i->locked = 0; 154 i->dirty = 0; 155 i->mount_point = NULL; 156 i->dev = 0; 157 i->inode = 0; 158 i->count = 0; 159 i->rdev = 0; 160 i->fsop = NULL; 161 i->sb = NULL; 162 memset_b(&i->u, NULL, sizeof(i->u)); 163 164 RESTORE_FLAGS(flags); 165 return i; 166 } 167 168 static int read_inode(struct inode *i) 169 { 170 int errno; 171 172 inode_lock(i); 173 if(i->sb && i->sb->fsop && i->sb->fsop->read_inode) { 174 errno = i->sb->fsop->read_inode(i); 175 inode_unlock(i); 176 return errno; 177 } 178 inode_unlock(i); 179 return -EINVAL; 180 } 181 182 static int write_inode(struct inode *i) 183 { 184 int errno; 185 186 inode_lock(i); 187 if(i->sb && i->sb->fsop && i->sb->fsop->write_inode) { 188 errno = i->sb->fsop->write_inode(i); 189 } else { 190 /* PIPE_DEV inodes can't be flushed on disk */ 191 i->dirty = 0; 192 errno = 0; 193 } 194 inode_unlock(i); 195 196 return errno; 197 } 198 199 static struct inode * search_inode_hash(__dev_t dev, __ino_t inode) 200 { 201 struct inode *i; 202 int n; 203 204 n = INODE_HASH(dev, inode); 205 i = inode_hash_table[n]; 206 207 while(i) { 208 if(i->dev == dev && i->inode == inode) { 209 return i; 210 } 211 i = i->next_hash; 212 } 213 214 return NULL; 215 } 216 217 void inode_lock(struct inode *i) 218 { 219 unsigned long int flags; 220 221 for(;;) { 222 SAVE_FLAGS(flags); CLI(); 223 if(i->locked) { 224 RESTORE_FLAGS(flags); 225 sleep(i, PROC_UNINTERRUPTIBLE); 226 } else { 227 break; 228 } 229 } 230 i->locked = 1; 231 RESTORE_FLAGS(flags); 232 } 233 234 void inode_unlock(struct inode *i) 235 { 236 unsigned long int flags; 237 238 SAVE_FLAGS(flags); CLI(); 239 i->locked = 0; 240 wakeup(i); 241 RESTORE_FLAGS(flags); 242 } 243 244 struct inode * ialloc(struct superblock *sb, int mode) 245 { 246 int errno; 247 struct inode *i; 248 249 if((i = get_free_inode())) { 250 i->sb = sb; 251 i->rdev = sb->dev; 252 if(i->sb && i->sb->fsop && i->sb->fsop->ialloc) { 253 errno = i->sb->fsop->ialloc(i, mode); 254 } else { 255 printk("WARNING: this filesystem does not have the ialloc() method!\n"); 256 i->count = 1; 257 i->sb = NULL; 258 iput(i); 259 return NULL; 260 } 261 if(errno) { 262 i->count = 1; 263 i->sb = NULL; 264 iput(i); 265 return NULL; 266 } 267 i->dev = sb->dev; 268 insert_to_hash(i); 269 return i; 270 } 271 printk("WARNING: %s(): no more inodes on free list!\n", __FUNCTION__); 272 return NULL; 273 } 274 275 struct inode * iget(struct superblock *sb, __ino_t inode) 276 { 277 unsigned long int flags; 278 struct inode *i; 279 280 if(!inode) { 281 return NULL; 282 } 283 284 for(;;) { 285 if((i = search_inode_hash(sb->dev, inode))) { 286 inode_lock(i); 287 288 if(i->mount_point) { 289 inode_unlock(i); 290 i = i->mount_point; 291 inode_lock(i); 292 } 293 if(!i->count) { 294 remove_from_free_list(i); 295 } 296 i->count++; 297 inode_unlock(i); 298 return i; 299 } 300 301 if(!(i = get_free_inode())) { 302 printk("WARNING: %s(): no more inodes on free list! (%d).\n", __FUNCTION__, kstat.free_inodes); 303 return NULL; 304 } 305 306 SAVE_FLAGS(flags); CLI(); 307 i->dev = i->rdev = sb->dev; 308 i->inode = inode; 309 i->sb = sb; 310 i->count = 1; 311 RESTORE_FLAGS(flags); 312 if(read_inode(i)) { 313 iput(i); 314 return NULL; 315 } 316 insert_to_hash(i); 317 return i; 318 } 319 } 320 321 int bmap(struct inode *i, __off_t offset, int mode) 322 { 323 if(i->fsop && i->fsop->bmap) { 324 return i->fsop->bmap(i, offset, mode); 325 } 326 return -EPERM; 327 } 328 329 int check_fs_busy(__dev_t dev, struct inode *root) 330 { 331 struct inode *i; 332 unsigned int n; 333 334 i = &inode_table[0]; 335 for(n = 0; n < NR_INODES; n++, i = &inode_table[n]) { 336 if(i->dev == dev && i->count) { 337 if(i == root && i->count == 1) { 338 continue; 339 } 340 /* FIXME: to be removed */ 341 printk("WARNING: root %d with count %d (on dev %d,%d)\n", root->inode, root->count, MAJOR(i->dev), MINOR(i->dev)); 342 printk("WARNING: inode %d with count %d (on dev %d,%d)\n", i->inode, i->count, MAJOR(i->dev), MINOR(i->dev)); 343 return 1; 344 } 345 } 346 return 0; 347 } 348 349 void iput(struct inode *i) 350 { 351 unsigned long int flags; 352 353 /* this solves the problem with rmdir('/') and iput(dir) which is NULL */ 354 if(!i) { 355 return; 356 } 357 358 if(!i->count) { 359 printk("WARNING: %s(): trying to free an already freed inode (%d)!\n", __FUNCTION__, i->inode); 360 return; 361 } 362 363 if(--i->count > 0) { 364 return; 365 } 366 367 if(!i->i_nlink) { 368 if(i->sb && i->sb->fsop && i->sb->fsop->ifree) { 369 inode_lock(i); 370 i->sb->fsop->ifree(i); 371 inode_unlock(i); 372 } 373 remove_from_hash(i); 374 } 375 if(i->dirty) { 376 if(write_inode(i)) { 377 printk("WARNING: %s(): can't write inode %d (%d,%d), will remain as dirty.\n", __FUNCTION__, i->inode, MAJOR(i->dev), MINOR(i->dev)); 378 return; 379 } 380 } 381 382 SAVE_FLAGS(flags); CLI(); 383 insert_on_free_list(i); 384 RESTORE_FLAGS(flags); 385 } 386 387 void sync_inodes(__dev_t dev) 388 { 389 struct inode *i; 390 int n; 391 392 i = &inode_table[0]; 393 394 lock_resource(&sync_resource); 395 for(n = 0; n < NR_INODES; n++) { 396 if(i->dirty) { 397 if(!dev || i->dev == dev) { 398 if(write_inode(i)) { 399 printk("WARNING: %s(): can't write inode %d (%d,%d), will remain as dirty.\n", __FUNCTION__, i->inode, MAJOR(i->dev), MINOR(i->dev)); 400 } 401 } 402 } 403 i++; 404 } 405 unlock_resource(&sync_resource); 406 } 407 408 void invalidate_inodes(__dev_t dev) 409 { 410 unsigned long int flags; 411 unsigned int n; 412 struct inode *i; 413 414 i = &inode_table[0]; 415 SAVE_FLAGS(flags); CLI(); 416 417 for(n = 0; n < NR_INODES; n++) { 418 if(i->dev == dev) { 419 inode_lock(i); 420 remove_from_hash(i); 421 inode_unlock(i); 422 } 423 i++; 424 } 425 426 RESTORE_FLAGS(flags); 427 } 428 429 void inode_init(void) 430 { 431 struct inode *i; 432 unsigned int n; 433 434 memset_b(inode_table, NULL, inode_table_size); 435 memset_b(inode_hash_table, NULL, inode_hash_table_size); 436 for(n = 0; n < NR_INODES; n++) { 437 i = &inode_table[n]; 438 i->count = 1; 439 insert_on_free_list(i); 440 } 441 }
![[top]](../icons/top.png){kind=icon}
![[bottom]](../icons/n_bottom.png){kind=icon}
*/
