home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / KERNEL-S / V1.0 / LINUX-1.0 / LINUX-1 / linux / fs / ext / freelists.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-01  |  9.9 KB  |  349 lines
  1. /*
  2.  *  linux/fs/ext/freelists.c
  3.  *
  4.  *  Copyright (C) 1992  Remy Card (card@masi.ibp.fr)
  5.  *
  6.  */
  7.  
  8. /* freelists.c contains the code that handles the inode and block free lists */
  9.  
  10.  
  11. /*
  12.  
  13.    The free blocks are managed by a linked list. The super block contains the
  14.    number of the first free block. This block contains 254 numbers of other
  15.    free blocks and the number of the next block in the list.
  16.  
  17.    When an ext fs is mounted, the number of the first free block is stored
  18.    in s->u.ext_sb.s_firstfreeblocknumber and the block header is stored in
  19.    s->u.ext_sb.s_firstfreeblock. u.ext_sb.s_freeblockscount contains the count
  20.    of free blocks.
  21.  
  22.    The free inodes are also managed by a linked list in a similar way. The
  23.    super block contains the number of the first free inode. This inode contains
  24.    14 numbers of other free inodes and the number of the next inode in the list.
  25.    
  26.    The number of the first free inode is stored in
  27.    s->u.ext_sb.s_firstfreeinodenumber and the header of the block containing
  28.    the inode is stored in s->u.ext_sb.s_firstfreeinodeblock.
  29.    u.ext_sb.s_freeinodescount contains the count of free inodes.
  30.  
  31. */
  32.  
  33. #include <linux/sched.h>
  34. #include <linux/ext_fs.h>
  35. #include <linux/stat.h>
  36. #include <linux/kernel.h>
  37. #include <linux/string.h>
  38. #include <linux/locks.h>
  39.  
  40. #define clear_block(addr) \
  41. __asm__("cld\n\t" \
  42.         "rep\n\t" \
  43.         "stosl" \
  44.         : \
  45.         :"a" (0),"c" (BLOCK_SIZE/4),"D" ((long) (addr)):"cx","di")
  46.  
  47. void ext_free_block(struct super_block * sb, int block)
  48. {
  49.     struct buffer_head * bh;
  50.     struct ext_free_block * efb;
  51.  
  52.     if (!sb) {
  53.         printk("trying to free block on non-existent device\n");
  54.         return;
  55.     }
  56.     lock_super (sb);
  57.     if (block < sb->u.ext_sb.s_firstdatazone ||
  58.         block >= sb->u.ext_sb.s_nzones) {
  59.         printk("trying to free block not in datazone\n");
  60.         return;
  61.     }
  62.     bh = get_hash_table(sb->s_dev, block, sb->s_blocksize);
  63.     if (bh)
  64.         bh->b_dirt=0;
  65.     brelse(bh);
  66.     if (sb->u.ext_sb.s_firstfreeblock)
  67.         efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  68.     if (!sb->u.ext_sb.s_firstfreeblock || efb->count == 254) {
  69. #ifdef EXTFS_DEBUG
  70. printk("ext_free_block: block full, skipping to %d\n", block);
  71. #endif
  72.         if (sb->u.ext_sb.s_firstfreeblock)
  73.             brelse (sb->u.ext_sb.s_firstfreeblock);
  74.         if (!(sb->u.ext_sb.s_firstfreeblock = bread (sb->s_dev,
  75.             block, sb->s_blocksize)))
  76.             panic ("ext_free_block: unable to read block to free\n");
  77.         efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  78.         efb->next = sb->u.ext_sb.s_firstfreeblocknumber;
  79.         efb->count = 0;
  80.         sb->u.ext_sb.s_firstfreeblocknumber = block;
  81.     } else {
  82.         efb->free[efb->count++] = block;
  83.     }
  84.     sb->u.ext_sb.s_freeblockscount ++;
  85.     sb->s_dirt = 1;
  86.     sb->u.ext_sb.s_firstfreeblock->b_dirt = 1;
  87.     unlock_super (sb);
  88.     return;
  89. }
  90.  
  91. int ext_new_block(struct super_block * sb)
  92. {
  93.     struct buffer_head * bh;
  94.     struct ext_free_block * efb;
  95.     int j;
  96.  
  97.     if (!sb) {
  98.         printk("trying to get new block from non-existent device\n");
  99.         return 0;
  100.     }
  101.     if (!sb->u.ext_sb.s_firstfreeblock)
  102.         return 0;
  103.     lock_super (sb);
  104.     efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  105.     if (efb->count) {
  106.         j = efb->free[--efb->count];
  107.         sb->u.ext_sb.s_firstfreeblock->b_dirt = 1;
  108.     } else {
  109. #ifdef EXTFS_DEBUG
  110. printk("ext_new_block: block empty, skipping to %d\n", efb->next);
  111. #endif
  112.         j = sb->u.ext_sb.s_firstfreeblocknumber;
  113.         sb->u.ext_sb.s_firstfreeblocknumber = efb->next;
  114.         brelse (sb->u.ext_sb.s_firstfreeblock);
  115.         if (!sb->u.ext_sb.s_firstfreeblocknumber) {
  116.             sb->u.ext_sb.s_firstfreeblock = NULL;
  117.         } else {
  118.             if (!(sb->u.ext_sb.s_firstfreeblock = bread (sb->s_dev,
  119.                 sb->u.ext_sb.s_firstfreeblocknumber,
  120.                 sb->s_blocksize)))
  121.                 panic ("ext_new_block: unable to read next free block\n");
  122.         }
  123.     }
  124.     if (j < sb->u.ext_sb.s_firstdatazone || j > sb->u.ext_sb.s_nzones) {
  125.         printk ("ext_new_block: blk = %d\n", j);
  126.         printk("allocating block not in data zone\n");
  127.         return 0;
  128.     }
  129.     sb->u.ext_sb.s_freeblockscount --;
  130.     sb->s_dirt = 1;
  131.  
  132.     if (!(bh=getblk(sb->s_dev, j, sb->s_blocksize))) {
  133.         printk("new_block: cannot get block");
  134.         return 0;
  135.     }
  136.     clear_block(bh->b_data);
  137.     bh->b_uptodate = 1;
  138.     bh->b_dirt = 1;
  139.     brelse(bh);
  140. #ifdef EXTFS_DEBUG
  141. printk("ext_new_block: allocating block %d\n", j);
  142. #endif
  143.     unlock_super (sb);
  144.     return j;
  145. }
  146.  
  147. unsigned long ext_count_free_blocks(struct super_block *sb)
  148. {
  149. #ifdef EXTFS_DEBUG
  150.     struct buffer_head * bh;
  151.     struct ext_free_block * efb;
  152.     unsigned long count, block;
  153.  
  154.     lock_super (sb);
  155.     if (!sb->u.ext_sb.s_firstfreeblock)
  156.         count = 0;
  157.     else {
  158.         efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  159.         count = efb->count + 1;
  160.         block = efb->next;
  161.         while (block) {
  162.             if (!(bh = bread (sb->s_dev, block, sb->s_blocksize))) {
  163.                 printk ("ext_count_free: error while reading free blocks list\n");
  164.                 block = 0;
  165.             } else {
  166.                 efb = (struct ext_free_block *) bh->b_data;
  167.                 count += efb->count + 1;
  168.                 block = efb->next;
  169.                 brelse (bh);
  170.             }
  171.         }
  172.     }
  173. printk("ext_count_free_blocks: stored = %d, computed = %d\n",
  174.     sb->u.ext_sb.s_freeblockscount, count);
  175.     unlock_super (sb);
  176.     return count;
  177. #else
  178.     return sb->u.ext_sb.s_freeblockscount;
  179. #endif
  180. }
  181.  
  182. void ext_free_inode(struct inode * inode)
  183. {
  184.     struct buffer_head * bh;
  185.     struct ext_free_inode * efi;
  186.     struct super_block * sb;
  187.     unsigned long block;
  188.     unsigned long ino;
  189.     dev_t dev;
  190.  
  191.     if (!inode)
  192.         return;
  193.     if (!inode->i_dev) {
  194.         printk("free_inode: inode has no device\n");
  195.         return;
  196.     }
  197.     if (inode->i_count != 1) {
  198.         printk("free_inode: inode has count=%d\n",inode->i_count);
  199.         return;
  200.     }
  201.     if (inode->i_nlink) {
  202.         printk("free_inode: inode has nlink=%d\n",inode->i_nlink);
  203.         return;
  204.     }
  205.     if (!inode->i_sb) {
  206.         printk("free_inode: inode on non-existent device\n");
  207.         return;
  208.     }
  209.     sb = inode->i_sb;
  210.     ino = inode->i_ino;
  211.     dev = inode->i_dev;
  212.     clear_inode(inode);
  213.     lock_super (sb);
  214.     if (ino < 1 || ino > sb->u.ext_sb.s_ninodes) {
  215.         printk("free_inode: inode 0 or non-existent inode\n");
  216.         unlock_super (sb);
  217.         return;
  218.     }
  219.     if (sb->u.ext_sb.s_firstfreeinodeblock)
  220.         efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
  221.             (sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK;
  222.     if (!sb->u.ext_sb.s_firstfreeinodeblock || efi->count == 14) {
  223. #ifdef EXTFS_DEBUG
  224. printk("ext_free_inode: inode full, skipping to %d\n", ino);
  225. #endif
  226.         if (sb->u.ext_sb.s_firstfreeinodeblock)
  227.             brelse (sb->u.ext_sb.s_firstfreeinodeblock);
  228.         block = 2 + (ino - 1) / EXT_INODES_PER_BLOCK;
  229.         if (!(bh = bread(dev, block, sb->s_blocksize)))
  230.             panic("ext_free_inode: unable to read inode block\n");
  231.         efi = ((struct ext_free_inode *) bh->b_data) +
  232.             (ino - 1) % EXT_INODES_PER_BLOCK;
  233.         efi->next = sb->u.ext_sb.s_firstfreeinodenumber;
  234.         efi->count = 0;
  235.         sb->u.ext_sb.s_firstfreeinodenumber = ino;
  236.         sb->u.ext_sb.s_firstfreeinodeblock = bh;
  237.     } else {
  238.         efi->free[efi->count++] = ino;
  239.     }
  240.     sb->u.ext_sb.s_freeinodescount ++;
  241.     sb->s_dirt = 1;
  242.     sb->u.ext_sb.s_firstfreeinodeblock->b_dirt = 1;
  243.     unlock_super (sb);
  244. }
  245.  
  246. struct inode * ext_new_inode(const struct inode * dir)
  247. {
  248.     struct super_block * sb;
  249.     struct inode * inode;
  250.     struct ext_free_inode * efi;
  251.     unsigned long block;
  252.     int j;
  253.  
  254.     if (!dir || !(inode=get_empty_inode()))
  255.         return NULL;
  256.     sb = dir->i_sb;
  257.     inode->i_sb = sb;
  258.     inode->i_flags = sb->s_flags;
  259.     if (!sb->u.ext_sb.s_firstfreeinodeblock)
  260.         return 0;
  261.     lock_super (sb);
  262.     efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
  263.         (sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK;
  264.     if (efi->count) {
  265.         j = efi->free[--efi->count];
  266.         sb->u.ext_sb.s_firstfreeinodeblock->b_dirt = 1;
  267.     } else {
  268. #ifdef EXTFS_DEBUG
  269. printk("ext_free_inode: inode empty, skipping to %d\n", efi->next);
  270. #endif
  271.         j = sb->u.ext_sb.s_firstfreeinodenumber;
  272.         if (efi->next > sb->u.ext_sb.s_ninodes) {
  273.             printk ("efi->next = %d\n", efi->next);
  274.             panic ("ext_new_inode: bad inode number in free list\n");
  275.         }
  276.         sb->u.ext_sb.s_firstfreeinodenumber = efi->next;
  277.         block = 2 + (((unsigned long) efi->next) - 1) / EXT_INODES_PER_BLOCK;
  278.         brelse (sb->u.ext_sb.s_firstfreeinodeblock);
  279.         if (!sb->u.ext_sb.s_firstfreeinodenumber) {
  280.             sb->u.ext_sb.s_firstfreeinodeblock = NULL;
  281.         } else {
  282.             if (!(sb->u.ext_sb.s_firstfreeinodeblock =
  283.                 bread(sb->s_dev, block, sb->s_blocksize)))
  284.                 panic ("ext_new_inode: unable to read next free inode block\n");
  285.         }
  286.     }
  287.     sb->u.ext_sb.s_freeinodescount --;
  288.     sb->s_dirt = 1;
  289.     inode->i_count = 1;
  290.     inode->i_nlink = 1;
  291.     inode->i_dev = sb->s_dev;
  292.     inode->i_uid = current->euid;
  293.     inode->i_gid = (dir->i_mode & S_ISGID) ? dir->i_gid : current->egid;
  294.     inode->i_dirt = 1;
  295.     inode->i_ino = j;
  296.     inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
  297.     inode->i_op = NULL;
  298.     inode->i_blocks = inode->i_blksize = 0;
  299.     insert_inode_hash(inode);
  300. #ifdef EXTFS_DEBUG
  301. printk("ext_new_inode : allocating inode %d\n", inode->i_ino);
  302. #endif
  303.     unlock_super (sb);
  304.     return inode;
  305. }
  306.  
  307. unsigned long ext_count_free_inodes(struct super_block *sb)
  308. {
  309. #ifdef EXTFS_DEBUG
  310.     struct buffer_head * bh;
  311.     struct ext_free_inode * efi;
  312.     unsigned long count, block, ino;
  313.  
  314.     lock_super (sb);
  315.     if (!sb->u.ext_sb.s_firstfreeinodeblock)
  316.         count = 0;
  317.     else {
  318.         efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
  319.             ((sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK);
  320.         count = efi->count + 1;
  321.         ino = efi->next;
  322.         while (ino) {
  323.             if (ino < 1 || ino > sb->u.ext_sb.s_ninodes) {
  324.                 printk ("u.ext_sb.s_firstfreeinodenumber = %d, ino = %d\n", 
  325.                     (int) sb->u.ext_sb.s_firstfreeinodenumber,ino);
  326.                 panic ("ext_count_fre_inodes: bad inode number in free list\n");
  327.             }
  328.             block = 2 + ((ino - 1) / EXT_INODES_PER_BLOCK);
  329.             if (!(bh = bread (sb->s_dev, block, sb->s_blocksize))) {
  330.                 printk ("ext_count_free_inodes: error while reading free inodes list\n");
  331.                 block = 0;
  332.             } else {
  333.                 efi = ((struct ext_free_inode *) bh->b_data) +
  334.                     ((ino - 1) % EXT_INODES_PER_BLOCK);
  335.                 count += efi->count + 1;
  336.                 ino = efi->next;
  337.                 brelse (bh);
  338.             }
  339.         }
  340.     }
  341. printk("ext_count_free_inodes: stored = %d, computed = %d\n",
  342.     sb->u.ext_sb.s_freeinodescount, count);
  343.     unlock_super (sb);
  344.     return count;
  345. #else
  346.     return sb->u.ext_sb.s_freeinodescount;
  347. #endif
  348. }
  349.