Lines Matching +full:big +full:- +full:endian +full:- +full:desc
1 // SPDX-License-Identifier: GPL-2.0
7 * Laboratoire MASI - Institut Blaise Pascal
11 * Big-endian to little-endian byte-swapping/bitmaps by
45 struct ext2_group_desc * desc; in ext2_get_group_desc() local
48 if (block_group >= sbi->s_groups_count) { in ext2_get_group_desc()
49 WARN(1, "block_group >= groups_count - " in ext2_get_group_desc()
51 block_group, sbi->s_groups_count); in ext2_get_group_desc()
57 offset = block_group & (EXT2_DESC_PER_BLOCK(sb) - 1); in ext2_get_group_desc()
58 if (!sbi->s_group_desc[group_desc]) { in ext2_get_group_desc()
59 WARN(1, "Group descriptor not loaded - " in ext2_get_group_desc()
60 "block_group = %d, group_desc = %lu, desc = %lu", in ext2_get_group_desc()
65 desc = (struct ext2_group_desc *) sbi->s_group_desc[group_desc]->b_data; in ext2_get_group_desc()
67 *bh = sbi->s_group_desc[group_desc]; in ext2_get_group_desc()
68 return desc + offset; in ext2_get_group_desc()
72 struct ext2_group_desc *desc, in ext2_valid_block_bitmap() argument
83 max_bit = ext2_group_last_block_no(sb, block_group) - group_first_block; in ext2_valid_block_bitmap()
86 bitmap_blk = le32_to_cpu(desc->bg_block_bitmap); in ext2_valid_block_bitmap()
87 offset = bitmap_blk - group_first_block; in ext2_valid_block_bitmap()
89 !ext2_test_bit(offset, bh->b_data)) in ext2_valid_block_bitmap()
94 bitmap_blk = le32_to_cpu(desc->bg_inode_bitmap); in ext2_valid_block_bitmap()
95 offset = bitmap_blk - group_first_block; in ext2_valid_block_bitmap()
97 !ext2_test_bit(offset, bh->b_data)) in ext2_valid_block_bitmap()
102 bitmap_blk = le32_to_cpu(desc->bg_inode_table); in ext2_valid_block_bitmap()
103 offset = bitmap_blk - group_first_block; in ext2_valid_block_bitmap()
105 offset + EXT2_SB(sb)->s_itb_per_group - 1 > max_bit) in ext2_valid_block_bitmap()
107 next_zero_bit = ext2_find_next_zero_bit(bh->b_data, in ext2_valid_block_bitmap()
108 offset + EXT2_SB(sb)->s_itb_per_group, in ext2_valid_block_bitmap()
110 if (next_zero_bit >= offset + EXT2_SB(sb)->s_itb_per_group) in ext2_valid_block_bitmap()
116 "Invalid block bitmap - " in ext2_valid_block_bitmap()
131 struct ext2_group_desc * desc; in read_block_bitmap() local
136 desc = ext2_get_group_desc(sb, block_group, NULL); in read_block_bitmap()
137 if (!desc) in read_block_bitmap()
139 bitmap_blk = le32_to_cpu(desc->bg_block_bitmap); in read_block_bitmap()
143 "Cannot read block bitmap - " in read_block_bitmap()
145 block_group, le32_to_cpu(desc->bg_block_bitmap)); in read_block_bitmap()
154 "Cannot read block bitmap - " in read_block_bitmap()
156 block_group, le32_to_cpu(desc->bg_block_bitmap)); in read_block_bitmap()
160 ext2_valid_block_bitmap(sb, desc, block_group, bh); in read_block_bitmap()
169 struct ext2_group_desc *desc, struct buffer_head *bh, int count) in group_adjust_blocks() argument
176 free_blocks = le16_to_cpu(desc->bg_free_blocks_count); in group_adjust_blocks()
177 desc->bg_free_blocks_count = cpu_to_le16(free_blocks + count); in group_adjust_blocks()
185 * --------------------------------------------
189 * We use a red-black tree to represent per-filesystem reservation
195 * __rsv_window_dump() -- Dump the filesystem block allocation reservation map
196 * @root: root of per-filesystem reservation rb tree
223 rsv, rsv->rsv_start, rsv->rsv_end); in __rsv_window_dump()
224 if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) { in __rsv_window_dump()
229 if (prev && prev->rsv_end >= rsv->rsv_start) { in __rsv_window_dump()
230 printk("Bad reservation %p (prev->end >= start)\n", in __rsv_window_dump()
264 * grp_goal (given goal block) could be -1, which means no specific
278 if ((rsv->_rsv_start > group_last_block) || in goal_in_my_reservation()
279 (rsv->_rsv_end < group_first_block)) in goal_in_my_reservation()
281 if ((grp_goal >= 0) && ((grp_goal + group_first_block < rsv->_rsv_start) in goal_in_my_reservation()
282 || (grp_goal + group_first_block > rsv->_rsv_end))) in goal_in_my_reservation()
299 struct rb_node *n = root->rb_node; in search_reserve_window()
308 if (goal < rsv->rsv_start) in search_reserve_window()
309 n = n->rb_left; in search_reserve_window()
310 else if (goal > rsv->rsv_end) in search_reserve_window()
311 n = n->rb_right; in search_reserve_window()
321 if (rsv->rsv_start > goal) { in search_reserve_window()
322 n = rb_prev(&rsv->rsv_node); in search_reserve_window()
329 * ext2_rsv_window_add() -- Insert a window to the block reservation rb tree.
338 struct rb_root *root = &EXT2_SB(sb)->s_rsv_window_root; in ext2_rsv_window_add()
339 struct rb_node *node = &rsv->rsv_node; in ext2_rsv_window_add()
340 ext2_fsblk_t start = rsv->rsv_start; in ext2_rsv_window_add()
342 struct rb_node ** p = &root->rb_node; in ext2_rsv_window_add()
351 if (start < this->rsv_start) in ext2_rsv_window_add()
352 p = &(*p)->rb_left; in ext2_rsv_window_add()
353 else if (start > this->rsv_end) in ext2_rsv_window_add()
354 p = &(*p)->rb_right; in ext2_rsv_window_add()
366 * rsv_window_remove() -- unlink a window from the reservation rb tree
377 rsv->rsv_start = EXT2_RESERVE_WINDOW_NOT_ALLOCATED; in rsv_window_remove()
378 rsv->rsv_end = EXT2_RESERVE_WINDOW_NOT_ALLOCATED; in rsv_window_remove()
379 rsv->rsv_alloc_hit = 0; in rsv_window_remove()
380 rb_erase(&rsv->rsv_node, &EXT2_SB(sb)->s_rsv_window_root); in rsv_window_remove()
384 * rsv_is_empty() -- Check if the reservation window is allocated.
392 return (rsv->_rsv_end == EXT2_RESERVE_WINDOW_NOT_ALLOCATED); in rsv_is_empty()
420 struct super_block *sb = inode->i_sb; in ext2_init_block_alloc_info()
424 struct ext2_reserve_window_node *rsv = &block_i->rsv_window_node; in ext2_init_block_alloc_info()
426 rsv->rsv_start = EXT2_RESERVE_WINDOW_NOT_ALLOCATED; in ext2_init_block_alloc_info()
427 rsv->rsv_end = EXT2_RESERVE_WINDOW_NOT_ALLOCATED; in ext2_init_block_alloc_info()
435 rsv->rsv_goal_size = 0; in ext2_init_block_alloc_info()
437 rsv->rsv_goal_size = EXT2_DEFAULT_RESERVE_BLOCKS; in ext2_init_block_alloc_info()
438 rsv->rsv_alloc_hit = 0; in ext2_init_block_alloc_info()
439 block_i->last_alloc_logical_block = 0; in ext2_init_block_alloc_info()
440 block_i->last_alloc_physical_block = 0; in ext2_init_block_alloc_info()
442 ei->i_block_alloc_info = block_i; in ext2_init_block_alloc_info()
460 struct ext2_block_alloc_info *block_i = ei->i_block_alloc_info; in ext2_discard_reservation()
462 spinlock_t *rsv_lock = &EXT2_SB(inode->i_sb)->s_rsv_window_lock; in ext2_discard_reservation()
467 rsv = &block_i->rsv_window_node; in ext2_discard_reservation()
468 if (!rsv_is_empty(&rsv->rsv_window)) { in ext2_discard_reservation()
470 if (!rsv_is_empty(&rsv->rsv_window)) in ext2_discard_reservation()
471 rsv_window_remove(inode->i_sb, rsv); in ext2_discard_reservation()
477 * ext2_free_blocks() -- Free given blocks and update quota and i_blocks
491 struct super_block * sb = inode->i_sb; in ext2_free_blocks()
493 struct ext2_group_desc * desc; in ext2_free_blocks() local
494 struct ext2_super_block * es = sbi->s_es; in ext2_free_blocks()
499 "Freeing blocks not in datazone - " in ext2_free_blocks()
504 ext2_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1); in ext2_free_blocks()
508 block_group = (block - le32_to_cpu(es->s_first_data_block)) / in ext2_free_blocks()
510 bit = (block - le32_to_cpu(es->s_first_data_block)) % in ext2_free_blocks()
517 overflow = bit + count - EXT2_BLOCKS_PER_GROUP(sb); in ext2_free_blocks()
518 count -= overflow; in ext2_free_blocks()
525 desc = ext2_get_group_desc (sb, block_group, &bh2); in ext2_free_blocks()
526 if (!desc) in ext2_free_blocks()
529 if (in_range (le32_to_cpu(desc->bg_block_bitmap), block, count) || in ext2_free_blocks()
530 in_range (le32_to_cpu(desc->bg_inode_bitmap), block, count) || in ext2_free_blocks()
531 in_range (block, le32_to_cpu(desc->bg_inode_table), in ext2_free_blocks()
532 sbi->s_itb_per_group) || in ext2_free_blocks()
533 in_range (block + count - 1, le32_to_cpu(desc->bg_inode_table), in ext2_free_blocks()
534 sbi->s_itb_per_group)) { in ext2_free_blocks()
536 "Freeing blocks in system zones - " in ext2_free_blocks()
544 bit + i, bitmap_bh->b_data)) { in ext2_free_blocks()
553 if (sb->s_flags & SB_SYNCHRONOUS) in ext2_free_blocks()
556 group_adjust_blocks(sb, block_group, desc, bh2, group_freed); in ext2_free_blocks()
567 percpu_counter_add(&sbi->s_freeblocks_counter, freed); in ext2_free_blocks()
579 * The bitmap search --- search forward through the actual bitmap on disk until
588 next = ext2_find_next_zero_bit(bh->b_data, maxblocks, start); in bitmap_search_next_usable_block()
590 return -1; in bitmap_search_next_usable_block()
619 * next 64-bit boundary is simple.. in find_next_usable_block()
624 here = ext2_find_next_zero_bit(bh->b_data, end_goal, start); in find_next_usable_block()
634 p = ((char *)bh->b_data) + (here >> 3); in find_next_usable_block()
635 r = memscan(p, 0, ((maxblocks + 7) >> 3) - (here >> 3)); in find_next_usable_block()
636 next = (r - ((char *)bh->b_data)) << 3; in find_next_usable_block()
679 end = group_last_block - group_first_block + 1; in ext2_try_to_allocate()
682 if (my_rsv->_rsv_start >= group_first_block) in ext2_try_to_allocate()
683 start = my_rsv->_rsv_start - group_first_block; in ext2_try_to_allocate()
684 if (my_rsv->_rsv_end < group_last_block) in ext2_try_to_allocate()
685 end = my_rsv->_rsv_end - group_first_block + 1; in ext2_try_to_allocate()
687 grp_goal = -1; in ext2_try_to_allocate()
699 !ext2_test_bit(grp_goal - 1, in ext2_try_to_allocate()
700 bitmap_bh->b_data); in ext2_try_to_allocate()
701 i++, grp_goal--) in ext2_try_to_allocate()
708 grp_goal, bitmap_bh->b_data)) { in ext2_try_to_allocate()
720 return grp_goal - num; in ext2_try_to_allocate()
722 return -1; in ext2_try_to_allocate()
726 * find_next_reservable_window - Find a reservable space within the given range.
752 * Return: -1 if we could not find a range of sufficient size. If we could,
765 int size = my_rsv->rsv_goal_size; in find_next_reservable_window()
767 /* TODO: make the start of the reservation window byte-aligned */ in find_next_reservable_window()
772 return -1; in find_next_reservable_window()
775 if (cur <= rsv->rsv_end) in find_next_reservable_window()
776 cur = rsv->rsv_end + 1; in find_next_reservable_window()
780 * that is what is expected, during the re-search, we could in find_next_reservable_window()
785 * space with expected-size (or more)... in find_next_reservable_window()
788 return -1; /* fail */ in find_next_reservable_window()
791 next = rb_next(&rsv->rsv_node); in find_next_reservable_window()
801 if (cur + size <= rsv->rsv_start) { in find_next_reservable_window()
803 * Found a reserveable space big enough. We could in find_next_reservable_window()
820 if ((prev != my_rsv) && (!rsv_is_empty(&my_rsv->rsv_window))) in find_next_reservable_window()
830 my_rsv->rsv_start = cur; in find_next_reservable_window()
831 my_rsv->rsv_end = cur + size - 1; in find_next_reservable_window()
832 my_rsv->rsv_alloc_hit = 0; in find_next_reservable_window()
841 * alloc_new_reservation - Allocate a new reservation window.
867 * Return: 0 on success, -1 if we failed to find a reservation window
877 struct rb_root *fs_rsv_root = &EXT2_SB(sb)->s_rsv_window_root; in alloc_new_reservation()
880 spinlock_t *rsv_lock = &EXT2_SB(sb)->s_rsv_window_lock; in alloc_new_reservation()
890 size = my_rsv->rsv_goal_size; in alloc_new_reservation()
892 if (!rsv_is_empty(&my_rsv->rsv_window)) { in alloc_new_reservation()
907 if ((my_rsv->rsv_start <= group_end_block) && in alloc_new_reservation()
908 (my_rsv->rsv_end > group_end_block) && in alloc_new_reservation()
909 (start_block >= my_rsv->rsv_start)) in alloc_new_reservation()
910 return -1; in alloc_new_reservation()
912 if ((my_rsv->rsv_alloc_hit > in alloc_new_reservation()
913 (my_rsv->rsv_end - my_rsv->rsv_start + 1) / 2)) { in alloc_new_reservation()
923 my_rsv->rsv_goal_size= size; in alloc_new_reservation()
944 if (ret == -1) { in alloc_new_reservation()
945 if (!rsv_is_empty(&my_rsv->rsv_window)) in alloc_new_reservation()
948 return -1; in alloc_new_reservation()
962 my_rsv->rsv_start - group_first_block, in alloc_new_reservation()
963 bitmap_bh, group_end_block - group_first_block + 1); in alloc_new_reservation()
971 if (!rsv_is_empty(&my_rsv->rsv_window)) in alloc_new_reservation()
974 return -1; /* failed */ in alloc_new_reservation()
982 if (start_block >= my_rsv->rsv_start && start_block <= my_rsv->rsv_end) in alloc_new_reservation()
1009 * expand the reservation window size if necessary on a best-effort
1017 spinlock_t *rsv_lock = &EXT2_SB(sb)->s_rsv_window_lock; in try_to_extend_reservation()
1022 next = rb_next(&my_rsv->rsv_node); in try_to_extend_reservation()
1025 my_rsv->rsv_end += size; in try_to_extend_reservation()
1029 if ((next_rsv->rsv_start - my_rsv->rsv_end - 1) >= size) in try_to_extend_reservation()
1030 my_rsv->rsv_end += size; in try_to_extend_reservation()
1032 my_rsv->rsv_end = next_rsv->rsv_start - 1; in try_to_extend_reservation()
1061 * We use a red-black tree for the per-filesystem reservation list.
1108 if (rsv_is_empty(&my_rsv->rsv_window) || (ret < 0) || in ext2_try_to_allocate_with_rsv()
1109 !goal_in_my_reservation(&my_rsv->rsv_window, in ext2_try_to_allocate_with_rsv()
1111 if (my_rsv->rsv_goal_size < *count) in ext2_try_to_allocate_with_rsv()
1112 my_rsv->rsv_goal_size = *count; in ext2_try_to_allocate_with_rsv()
1118 if (!goal_in_my_reservation(&my_rsv->rsv_window, in ext2_try_to_allocate_with_rsv()
1120 grp_goal = -1; in ext2_try_to_allocate_with_rsv()
1122 int curr = my_rsv->rsv_end - in ext2_try_to_allocate_with_rsv()
1127 *count - curr); in ext2_try_to_allocate_with_rsv()
1130 if ((my_rsv->rsv_start > group_last_block) || in ext2_try_to_allocate_with_rsv()
1131 (my_rsv->rsv_end < group_first_block)) { in ext2_try_to_allocate_with_rsv()
1135 group_last_block, my_rsv->rsv_start, in ext2_try_to_allocate_with_rsv()
1136 my_rsv->rsv_end); in ext2_try_to_allocate_with_rsv()
1137 rsv_window_dump(&EXT2_SB(sb)->s_rsv_window_root, 1); in ext2_try_to_allocate_with_rsv()
1138 return -1; in ext2_try_to_allocate_with_rsv()
1141 &num, &my_rsv->rsv_window); in ext2_try_to_allocate_with_rsv()
1143 my_rsv->rsv_alloc_hit += num; in ext2_try_to_allocate_with_rsv()
1154 * @sbi: in-core super block structure.
1162 free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter); in ext2_has_free_blocks()
1163 root_blocks = le32_to_cpu(sbi->s_es->s_r_blocks_count); in ext2_has_free_blocks()
1165 !uid_eq(sbi->s_resuid, current_fsuid()) && in ext2_has_free_blocks()
1166 (gid_eq(sbi->s_resgid, GLOBAL_ROOT_GID) || in ext2_has_free_blocks()
1167 !in_group_p (sbi->s_resgid))) { in ext2_has_free_blocks()
1174 * Returns 1 if the passed-in block region is valid; 0 if some part overlaps
1180 if ((start_blk <= le32_to_cpu(sbi->s_es->s_first_data_block)) || in ext2_data_block_valid()
1181 (start_blk + count - 1 < start_blk) || in ext2_data_block_valid()
1182 (start_blk + count - 1 >= le32_to_cpu(sbi->s_es->s_blocks_count))) in ext2_data_block_valid()
1186 if ((start_blk <= sbi->s_sb_block) && in ext2_data_block_valid()
1187 (start_blk + count - 1 >= sbi->s_sb_block)) in ext2_data_block_valid()
1194 * ext2_new_blocks() -- core block(s) allocation function
1216 ext2_grpblk_t grp_alloc_blk; /* blockgroup-relative allocated block*/ in ext2_new_blocks()
1217 ext2_fsblk_t ret_block; /* filesyetem-wide allocated block */ in ext2_new_blocks()
1232 *errp = -ENOSPC; in ext2_new_blocks()
1233 sb = inode->i_sb; in ext2_new_blocks()
1245 es = EXT2_SB(sb)->s_es; in ext2_new_blocks()
1249 * mounted with reservation(default,-o reservation), and it's a regular in ext2_new_blocks()
1255 block_i = EXT2_I(inode)->i_block_alloc_info; in ext2_new_blocks()
1257 windowsz = block_i->rsv_window_node.rsv_goal_size; in ext2_new_blocks()
1259 my_rsv = &block_i->rsv_window_node; in ext2_new_blocks()
1263 *errp = -ENOSPC; in ext2_new_blocks()
1270 if (goal < le32_to_cpu(es->s_first_data_block) || in ext2_new_blocks()
1271 goal >= le32_to_cpu(es->s_blocks_count)) in ext2_new_blocks()
1272 goal = le32_to_cpu(es->s_first_data_block); in ext2_new_blocks()
1273 group_no = (goal - le32_to_cpu(es->s_first_data_block)) / in ext2_new_blocks()
1281 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count); in ext2_new_blocks()
1288 && (rsv_is_empty(&my_rsv->rsv_window))) in ext2_new_blocks()
1292 grp_target_blk = ((goal - le32_to_cpu(es->s_first_data_block)) % in ext2_new_blocks()
1296 * working out or fs corruption), the bitmap_bh is non-null in ext2_new_blocks()
1311 ngroups = EXT2_SB(sb)->s_groups_count; in ext2_new_blocks()
1326 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count); in ext2_new_blocks()
1346 * try to allocate block(s) from this group, without a goal(-1). in ext2_new_blocks()
1349 bitmap_bh, -1, my_rsv, &num); in ext2_new_blocks()
1367 *errp = -ENOSPC; in ext2_new_blocks()
1373 group_no, gdp->bg_free_blocks_count); in ext2_new_blocks()
1377 if (in_range(le32_to_cpu(gdp->bg_block_bitmap), ret_block, num) || in ext2_new_blocks()
1378 in_range(le32_to_cpu(gdp->bg_inode_bitmap), ret_block, num) || in ext2_new_blocks()
1379 in_range(ret_block, le32_to_cpu(gdp->bg_inode_table), in ext2_new_blocks()
1380 EXT2_SB(sb)->s_itb_per_group) || in ext2_new_blocks()
1381 in_range(ret_block + num - 1, le32_to_cpu(gdp->bg_inode_table), in ext2_new_blocks()
1382 EXT2_SB(sb)->s_itb_per_group)) { in ext2_new_blocks()
1384 "Allocating block in system zone - " in ext2_new_blocks()
1398 if (ret_block + num - 1 >= le32_to_cpu(es->s_blocks_count)) { in ext2_new_blocks()
1400 "block("E2FSBLK") >= blocks count(%d) - " in ext2_new_blocks()
1402 le32_to_cpu(es->s_blocks_count), group_no, es); in ext2_new_blocks()
1406 group_adjust_blocks(sb, group_no, gdp, gdp_bh, -num); in ext2_new_blocks()
1407 percpu_counter_sub(&sbi->s_freeblocks_counter, num); in ext2_new_blocks()
1410 if (sb->s_flags & SB_SYNCHRONOUS) in ext2_new_blocks()
1416 dquot_free_block_nodirty(inode, *count-num); in ext2_new_blocks()
1423 *errp = -EIO; in ext2_new_blocks()
1440 return numchars * BITS_PER_BYTE - memweight(map->b_data, numchars); in ext2_count_free()
1447 struct ext2_group_desc * desc; in ext2_count_free_blocks() local
1454 es = EXT2_SB(sb)->s_es; in ext2_count_free_blocks()
1457 desc = NULL; in ext2_count_free_blocks()
1458 for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) { in ext2_count_free_blocks()
1460 desc = ext2_get_group_desc (sb, i, NULL); in ext2_count_free_blocks()
1461 if (!desc) in ext2_count_free_blocks()
1463 desc_count += le16_to_cpu(desc->bg_free_blocks_count); in ext2_count_free_blocks()
1468 x = ext2_count_free(bitmap_bh, sb->s_blocksize); in ext2_count_free_blocks()
1470 i, le16_to_cpu(desc->bg_free_blocks_count), x); in ext2_count_free_blocks()
1475 (long)le32_to_cpu(es->s_free_blocks_count), in ext2_count_free_blocks()
1479 for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) { in ext2_count_free_blocks()
1480 desc = ext2_get_group_desc(sb, i, NULL); in ext2_count_free_blocks()
1481 if (!desc) in ext2_count_free_blocks()
1483 desc_count += le16_to_cpu(desc->bg_free_blocks_count); in ext2_count_free_blocks()
1507 * ext2_bg_has_super - number of blocks used by the superblock in group
1523 * ext2_bg_num_gdb - number of blocks used by the group table in group
1533 return ext2_bg_has_super(sb, group) ? EXT2_SB(sb)->s_gdb_count : 0; in ext2_bg_num_gdb()