Changeset 38542dc in mainline for uspace/lib/ext4/libext4_ialloc.c
- Timestamp:
- 2012-08-12T18:36:10Z (12 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 49505fe
- Parents:
- b08e7970
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/ext4/libext4_ialloc.c
rb08e7970 r38542dc 29 29 /** @addtogroup libext4 30 30 * @{ 31 */ 32 31 */ 33 32 /** 34 * @file 35 * @brief Inode (de)allocation operations.33 * @file libext4_ialloc.c 34 * @brief I-node (de)allocation operations. 36 35 */ 37 36 … … 43 42 /** Convert i-node number to relative index in block group. 44 43 * 45 * @param sb superblock 46 * @param inode i-node number to be converted 47 * @return index of the i-node in the block group 44 * @param sb Superblock 45 * @param inode I-node number to be converted 46 * 47 * @return Index of the i-node in the block group 48 * 48 49 */ 49 50 static uint32_t ext4_ialloc_inode2index_in_group(ext4_superblock_t *sb, 50 51 uint32_t inode) 51 52 { 52 53 uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb); … … 56 57 /** Convert relative index of i-node to absolute i-node number. 57 58 * 58 * @param sb superblock 59 * @param inode index to be converted 60 * @return absolute number of the i-node 59 * @param sb Superblock 60 * @param inode Index to be converted 61 * 62 * @return Absolute number of the i-node 63 * 61 64 */ 62 65 static uint32_t ext4_ialloc_index_in_group2inode(ext4_superblock_t *sb, 63 66 uint32_t index, uint32_t bgid) 64 67 { 65 68 uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb); … … 69 72 /** Compute block group number from the i-node number. 70 73 * 71 * @param sb superblock 72 * @param inode i-node number to be found the block group for 73 * @return block group number computed from i-node number 74 * @param sb Superblock 75 * @param inode I-node number to be found the block group for 76 * 77 * @return Block group number computed from i-node number 78 * 74 79 */ 75 80 static uint32_t ext4_ialloc_get_bgid_of_inode(ext4_superblock_t *sb, 76 81 uint32_t inode) 77 82 { 78 83 uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb); 79 84 return (inode - 1) / inodes_per_group; 80 81 85 } 82 86 … … 84 88 /** Free i-node number and modify filesystem data structers. 85 89 * 86 * @param fs filesystem, where the i-node is located 87 * @param index index of i-node to be release 88 * @param is_dir flag us for information whether i-node is directory or not 90 * @param fs Filesystem, where the i-node is located 91 * @param index Index of i-node to be release 92 * @param is_dir Flag us for information whether i-node is directory or not 93 * 89 94 */ 90 95 int ext4_ialloc_free_inode(ext4_filesystem_t *fs, uint32_t index, bool is_dir) 91 96 { 92 int rc;93 94 97 ext4_superblock_t *sb = fs->superblock; 95 98 96 99 /* Compute index of block group and load it */ 97 100 uint32_t block_group = ext4_ialloc_get_bgid_of_inode(sb, index); 98 101 99 102 ext4_block_group_ref_t *bg_ref; 100 rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref); 101 if (rc != EOK) { 102 return rc; 103 } 104 103 int rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref); 104 if (rc != EOK) 105 return rc; 106 105 107 /* Load i-node bitmap */ 106 108 uint32_t bitmap_block_addr = ext4_block_group_get_inode_bitmap( 107 109 bg_ref->block_group, sb); 108 110 block_t *bitmap_block; 109 rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, BLOCK_FLAGS_NONE);110 if (rc != EOK) {111 return rc;112 }113 111 rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 112 BLOCK_FLAGS_NONE); 113 if (rc != EOK) 114 return rc; 115 114 116 /* Free i-node in the bitmap */ 115 117 uint32_t index_in_group = ext4_ialloc_inode2index_in_group(sb, index); 116 118 ext4_bitmap_free_bit(bitmap_block->data, index_in_group); 117 119 bitmap_block->dirty = true; 118 120 119 121 /* Put back the block with bitmap */ 120 122 rc = block_put(bitmap_block); … … 124 126 return rc; 125 127 } 126 128 127 129 /* If released i-node is a directory, decrement used directories count */ 128 130 if (is_dir) { 129 131 uint32_t bg_used_dirs = ext4_block_group_get_used_dirs_count( 130 132 bg_ref->block_group, sb); 131 133 bg_used_dirs--; 132 ext4_block_group_set_used_dirs_count( 133 bg_ref->block_group, sb,bg_used_dirs);134 ext4_block_group_set_used_dirs_count(bg_ref->block_group, sb, 135 bg_used_dirs); 134 136 } 135 137 136 138 /* Update block group free inodes count */ 137 139 uint32_t free_inodes = ext4_block_group_get_free_inodes_count( 138 140 bg_ref->block_group, sb); 139 141 free_inodes++; 140 ext4_block_group_set_free_inodes_count(bg_ref->block_group, 141 sb,free_inodes);142 142 ext4_block_group_set_free_inodes_count(bg_ref->block_group, sb, 143 free_inodes); 144 143 145 bg_ref->dirty = true; 144 146 145 147 /* Put back the modified block group */ 146 148 rc = ext4_filesystem_put_block_group_ref(bg_ref); 147 if (rc != EOK) { 148 return rc; 149 } 150 149 if (rc != EOK) 150 return rc; 151 151 152 /* Update superblock free inodes count */ 152 uint32_t sb_free_inodes = ext4_superblock_get_free_inodes_count(sb); 153 uint32_t sb_free_inodes = 154 ext4_superblock_get_free_inodes_count(sb); 153 155 sb_free_inodes++; 154 156 ext4_superblock_set_free_inodes_count(sb, sb_free_inodes); 155 157 156 158 return EOK; 157 159 } … … 159 161 /** I-node allocation algorithm. 160 162 * 161 * This is more simple algorithm, than Orlov allocator used in the Linux kernel 162 * 163 * @param fs filesystem to allocate i-node on 164 * @param index output value - allocated i-node number 165 * @param is_dir flag if allocated i-node will be file or directory 166 * @return error code 163 * This is more simple algorithm, than Orlov allocator used 164 * in the Linux kernel. 165 * 166 * @param fs Filesystem to allocate i-node on 167 * @param index Output value - allocated i-node number 168 * @param is_dir Flag if allocated i-node will be file or directory 169 * 170 * @return Error code 171 * 167 172 */ 168 173 int ext4_ialloc_alloc_inode(ext4_filesystem_t *fs, uint32_t *index, bool is_dir) 169 174 { 170 int rc;171 172 175 ext4_superblock_t *sb = fs->superblock; 173 176 174 177 uint32_t bgid = 0; 175 178 uint32_t bg_count = ext4_superblock_get_block_group_count(sb); 176 179 uint32_t sb_free_inodes = ext4_superblock_get_free_inodes_count(sb); 177 180 uint32_t avg_free_inodes = sb_free_inodes / bg_count; 178 181 179 182 /* Try to find free i-node in all block groups */ 180 183 while (bgid < bg_count) { 181 182 184 /* Load block group to check */ 183 185 ext4_block_group_ref_t *bg_ref; 184 rc = ext4_filesystem_get_block_group_ref(fs, bgid, &bg_ref);185 if (rc != EOK) {186 int rc = ext4_filesystem_get_block_group_ref(fs, bgid, &bg_ref); 187 if (rc != EOK) 186 188 return rc; 187 } 188 189 189 190 ext4_block_group_t *bg = bg_ref->block_group; 190 191 191 192 /* Read necessary values for algorithm */ 192 193 uint32_t free_blocks = ext4_block_group_get_free_blocks_count(bg, sb); 193 194 uint32_t free_inodes = ext4_block_group_get_free_inodes_count(bg, sb); 194 195 uint32_t used_dirs = ext4_block_group_get_used_dirs_count(bg, sb); 195 196 196 197 /* Check if this block group is good candidate for allocation */ 197 198 if ((free_inodes >= avg_free_inodes) && (free_blocks > 0)) { 198 199 199 /* Load block with bitmap */ 200 uint32_t bitmap_block_addr = 201 202 200 uint32_t bitmap_block_addr = ext4_block_group_get_inode_bitmap( 201 bg_ref->block_group, sb); 202 203 203 block_t *bitmap_block; 204 rc = block_get(&bitmap_block, fs->device, 205 bitmap_block_addr,BLOCK_FLAGS_NONE);206 if (rc != EOK) {204 rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 205 BLOCK_FLAGS_NONE); 206 if (rc != EOK) 207 207 return rc; 208 } 209 208 210 209 /* Try to allocate i-node in the bitmap */ 211 210 uint32_t inodes_in_group = ext4_superblock_get_inodes_in_group(sb, bgid); 212 211 uint32_t index_in_group; 213 rc = ext4_bitmap_find_free_bit_and_set( 214 bitmap_block->data,0, &index_in_group, inodes_in_group);215 212 rc = ext4_bitmap_find_free_bit_and_set(bitmap_block->data, 213 0, &index_in_group, inodes_in_group); 214 216 215 /* Block group has not any free i-node */ 217 216 if (rc == ENOSPC) { … … 220 219 continue; 221 220 } 222 221 223 222 /* Free i-node found, save the bitmap */ 224 223 bitmap_block->dirty = true; 225 224 226 225 rc = block_put(bitmap_block); 227 if (rc != EOK) {226 if (rc != EOK) 228 227 return rc; 229 } 230 228 231 229 /* Modify filesystem counters */ 232 230 free_inodes--; 233 231 ext4_block_group_set_free_inodes_count(bg, sb, free_inodes); 234 232 235 233 /* Increment used directories counter */ 236 234 if (is_dir) { … … 238 236 ext4_block_group_set_used_dirs_count(bg, sb, used_dirs); 239 237 } 240 238 241 239 /* Decrease unused inodes count */ 242 240 if (ext4_block_group_has_flag(bg, 243 EXT4_BLOCK_GROUP_ITABLE_ZEROED)) { 244 241 EXT4_BLOCK_GROUP_ITABLE_ZEROED)) { 245 242 uint32_t unused = 246 247 243 ext4_block_group_get_itable_unused(bg, sb); 244 248 245 uint32_t inodes_in_group = 249 250 246 ext4_superblock_get_inodes_in_group(sb, bgid); 247 251 248 uint32_t free = inodes_in_group - unused; 252 249 253 250 if (index_in_group >= free) { 254 251 unused = inodes_in_group - (index_in_group + 1); 255 256 252 ext4_block_group_set_itable_unused(bg, sb, unused); 257 253 } 258 254 } 259 255 260 256 /* Save modified block group */ 261 257 bg_ref->dirty = true; 262 258 263 259 rc = ext4_filesystem_put_block_group_ref(bg_ref); 264 if (rc != EOK) {260 if (rc != EOK) 265 261 return rc; 266 } 267 262 268 263 /* Update superblock */ 269 264 sb_free_inodes--; 270 265 ext4_superblock_set_free_inodes_count(sb, sb_free_inodes); 271 266 272 267 /* Compute the absolute i-nodex number */ 273 268 *index = ext4_ialloc_index_in_group2inode(sb, index_in_group, bgid); 274 269 275 270 return EOK; 276 277 271 } 278 272 279 273 /* Block group not modified, put it and jump to the next block group */ 280 274 ext4_filesystem_put_block_group_ref(bg_ref); 281 275 ++bgid; 282 276 } 283 277 284 278 return ENOSPC; 285 279 } … … 287 281 /** 288 282 * @} 289 */ 283 */
Note:
See TracChangeset
for help on using the changeset viewer.