Lines Matching defs:ctl
47 static int link_free_space(struct btrfs_free_space_ctl *ctl,
49 static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
51 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
54 static void free_bitmap(struct btrfs_free_space_ctl *ctl,
56 static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
60 static void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
65 while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
68 unlink_free_space(ctl, info, true);
71 free_bitmap(ctl, info);
74 cond_resched_lock(&ctl->tree_lock);
689 static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
691 struct btrfs_block_group *block_group = ctl->block_group;
696 u64 bytes_per_bg = BITS_PER_BITMAP * ctl->unit;
701 if (ctl->total_bitmaps > max_bitmaps)
705 ctl->total_bitmaps, ctl->unit, max_bitmaps,
707 ASSERT(ctl->total_bitmaps <= max_bitmaps);
720 bitmap_bytes = ctl->total_bitmaps * ctl->unit;
729 ctl->extents_thresh =
734 struct btrfs_free_space_ctl *ctl,
832 spin_lock(&ctl->tree_lock);
833 ret = link_free_space(ctl, e);
834 spin_unlock(&ctl->tree_lock);
852 spin_lock(&ctl->tree_lock);
853 ret = link_free_space(ctl, e);
855 spin_unlock(&ctl->tree_lock);
861 ctl->total_bitmaps++;
862 recalculate_thresholds(ctl);
863 spin_unlock(&ctl->tree_lock);
891 spin_lock(&ctl->tree_lock);
892 __btrfs_remove_free_space_cache(ctl);
893 spin_unlock(&ctl->tree_lock);
898 struct btrfs_free_space_ctl *ctl)
904 while (!ret && (n = rb_first(&ctl->free_space_offset)) != NULL) {
910 unlink_free_space(ctl, info, true);
911 spin_unlock(&ctl->tree_lock);
914 spin_lock(&ctl->tree_lock);
917 u64 bytes = ctl->unit;
919 ret = search_bitmap(ctl, info, &offset, &bytes, false);
921 bitmap_clear_bits(ctl, info, offset, bytes, true);
922 spin_unlock(&ctl->tree_lock);
925 spin_lock(&ctl->tree_lock);
927 free_bitmap(ctl, info);
931 cond_resched_lock(&ctl->tree_lock);
941 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
952 * valid copy it all into the actual free space ctl.
1060 spin_lock(&ctl->tree_lock);
1062 spin_unlock(&ctl->tree_lock);
1069 struct btrfs_free_space_ctl *ctl,
1077 struct rb_node *node = rb_first(&ctl->free_space_offset);
1129 list_for_each_entry(trim_entry, &ctl->trimming_ranges, list) {
1367 * @ctl: free space cache we are going to write out
1377 struct btrfs_free_space_ctl *ctl,
1422 mutex_lock(&ctl->cache_writeout_mutex);
1424 spin_lock(&ctl->tree_lock);
1425 ret = write_cache_extent_entries(io_ctl, ctl,
1449 spin_unlock(&ctl->tree_lock);
1450 mutex_unlock(&ctl->cache_writeout_mutex);
1492 spin_unlock(&ctl->tree_lock);
1493 mutex_unlock(&ctl->cache_writeout_mutex);
1520 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1535 ret = __btrfs_write_out_cache(fs_info->tree_root, inode, ctl,
1570 static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
1576 bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
1577 bitmap_start = offset - ctl->start;
1580 bitmap_start += ctl->start;
1585 static int tree_insert_offset(struct btrfs_free_space_ctl *ctl,
1593 lockdep_assert_held(&ctl->tree_lock);
1599 root = &ctl->free_space_offset;
1702 tree_search_offset(struct btrfs_free_space_ctl *ctl,
1705 struct rb_node *n = ctl->free_space_offset.rb_node;
1708 lockdep_assert_held(&ctl->tree_lock);
1790 if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
1805 ctl->unit > offset)
1815 static inline void unlink_free_space(struct btrfs_free_space_ctl *ctl,
1819 lockdep_assert_held(&ctl->tree_lock);
1821 rb_erase(&info->offset_index, &ctl->free_space_offset);
1822 rb_erase_cached(&info->bytes_index, &ctl->free_space_bytes);
1823 ctl->free_extents--;
1826 ctl->discardable_extents[BTRFS_STAT_CURR]--;
1827 ctl->discardable_bytes[BTRFS_STAT_CURR] -= info->bytes;
1831 ctl->free_space -= info->bytes;
1834 static int link_free_space(struct btrfs_free_space_ctl *ctl,
1839 lockdep_assert_held(&ctl->tree_lock);
1842 ret = tree_insert_offset(ctl, NULL, info);
1846 rb_add_cached(&info->bytes_index, &ctl->free_space_bytes, entry_less);
1849 ctl->discardable_extents[BTRFS_STAT_CURR]++;
1850 ctl->discardable_bytes[BTRFS_STAT_CURR] += info->bytes;
1853 ctl->free_space += info->bytes;
1854 ctl->free_extents++;
1858 static void relink_bitmap_entry(struct btrfs_free_space_ctl *ctl,
1865 * want to re-link it into our ctl bytes index.
1870 lockdep_assert_held(&ctl->tree_lock);
1872 rb_erase_cached(&info->bytes_index, &ctl->free_space_bytes);
1873 rb_add_cached(&info->bytes_index, &ctl->free_space_bytes, entry_less);
1876 static inline void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1883 start = offset_to_bit(info->offset, ctl->unit, offset);
1884 count = bytes_to_bits(bytes, ctl->unit);
1891 if (info->max_extent_size > ctl->unit)
1894 relink_bitmap_entry(ctl, info);
1904 ctl->discardable_extents[BTRFS_STAT_CURR] += extent_delta;
1905 ctl->discardable_bytes[BTRFS_STAT_CURR] -= bytes;
1909 ctl->free_space -= bytes;
1912 static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
1919 start = offset_to_bit(info->offset, ctl->unit, offset);
1920 count = bytes_to_bits(bytes, ctl->unit);
1932 ctl->free_space += bytes;
1934 relink_bitmap_entry(ctl, info);
1944 ctl->discardable_extents[BTRFS_STAT_CURR] += extent_delta;
1945 ctl->discardable_bytes[BTRFS_STAT_CURR] += bytes;
1953 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
1974 i = offset_to_bit(bitmap_info->offset, ctl->unit,
1976 bits = bytes_to_bits(*bytes, ctl->unit);
1996 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
1997 *bytes = (u64)(found_bits) * ctl->unit;
2001 *bytes = (u64)(max_bits) * ctl->unit;
2003 relink_bitmap_entry(ctl, bitmap_info);
2009 find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,
2018 if (!ctl->free_space_offset.rb_node)
2022 node = rb_first_cached(&ctl->free_space_bytes);
2024 entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset),
2059 tmp = entry->offset - ctl->start + align - 1;
2061 tmp = tmp * align + ctl->start;
2085 ret = search_bitmap(ctl, entry, &tmp, &size, true);
2115 static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,
2118 info->offset = offset_to_bitmap(ctl, offset);
2122 link_free_space(ctl, info);
2123 ctl->total_bitmaps++;
2124 recalculate_thresholds(ctl);
2127 static void free_bitmap(struct btrfs_free_space_ctl *ctl,
2137 ctl->discardable_extents[BTRFS_STAT_CURR] -=
2139 ctl->discardable_bytes[BTRFS_STAT_CURR] -= bitmap_info->bytes;
2142 unlink_free_space(ctl, bitmap_info, true);
2145 ctl->total_bitmaps--;
2146 recalculate_thresholds(ctl);
2149 static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,
2158 end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * ctl->unit) - 1;
2167 search_bytes = ctl->unit;
2169 ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes,
2180 bitmap_clear_bits(ctl, bitmap_info, search_start, search_bytes, true);
2187 free_bitmap(ctl, bitmap_info);
2213 search_bytes = ctl->unit;
2214 ret = search_bitmap(ctl, bitmap_info, &search_start,
2221 free_bitmap(ctl, bitmap_info);
2226 static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl,
2239 ctl->discardable_extents[BTRFS_STAT_CURR] +=
2241 ctl->discardable_bytes[BTRFS_STAT_CURR] += info->bytes;
2246 end = info->offset + (u64)(BITS_PER_BITMAP * ctl->unit);
2250 bitmap_set_bits(ctl, info, offset, bytes_to_set);
2256 static bool use_bitmap(struct btrfs_free_space_ctl *ctl,
2259 struct btrfs_block_group *block_group = ctl->block_group;
2276 if (!forced && ctl->free_extents < ctl->extents_thresh) {
2285 if (ctl->free_extents * 3 <= ctl->extents_thresh)
2300 if (((BITS_PER_BITMAP * ctl->unit) >> 1) > block_group->length)
2310 static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl,
2324 if (!ctl->op->use_bitmap(ctl, info))
2327 if (ctl->op == &free_space_op)
2328 block_group = ctl->block_group;
2356 if (entry->offset == offset_to_bitmap(ctl, offset)) {
2357 bytes_added = add_bytes_to_bitmap(ctl, entry, offset,
2370 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
2377 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes,
2391 add_new_bitmap(ctl, info, offset);
2396 spin_unlock(&ctl->tree_lock);
2403 spin_lock(&ctl->tree_lock);
2413 spin_lock(&ctl->tree_lock);
2448 static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,
2464 right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
2471 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
2476 unlink_free_space(ctl, right_info, update_stat);
2486 unlink_free_space(ctl, left_info, update_stat);
2496 static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl,
2504 const u64 bitmap_offset = offset_to_bitmap(ctl, end);
2507 bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
2511 i = offset_to_bit(bitmap->offset, ctl->unit, end);
2515 bytes = (j - i) * ctl->unit;
2522 bitmap_clear_bits(ctl, bitmap, end, bytes, update_stat);
2525 free_bitmap(ctl, bitmap);
2530 static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
2541 bitmap_offset = offset_to_bitmap(ctl, info->offset);
2546 bitmap_offset = offset_to_bitmap(ctl, info->offset - 1);
2549 bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
2553 i = offset_to_bit(bitmap->offset, ctl->unit, info->offset) - 1;
2565 bytes = (i + 1) * ctl->unit;
2567 bytes = (i - prev_j) * ctl->unit;
2576 bitmap_clear_bits(ctl, bitmap, info->offset, bytes, update_stat);
2579 free_bitmap(ctl, bitmap);
2595 static void steal_from_bitmap(struct btrfs_free_space_ctl *ctl,
2606 if (ctl->total_bitmaps > 0) {
2610 stole_end = steal_from_bitmap_to_end(ctl, info, update_stat);
2611 if (ctl->total_bitmaps > 0)
2612 stole_front = steal_from_bitmap_to_front(ctl, info,
2616 try_merge_free_space(ctl, info, update_stat);
2625 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2642 spin_lock(&ctl->tree_lock);
2644 if (try_merge_free_space(ctl, info, true))
2652 ret = insert_into_bitmap(ctl, info);
2666 steal_from_bitmap(ctl, info, true);
2670 ret = link_free_space(ctl, info);
2675 spin_unlock(&ctl->tree_lock);
2694 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2706 spin_lock(&ctl->tree_lock);
2719 ctl->free_space += to_free;
2726 spin_unlock(&ctl->tree_lock);
2796 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2821 spin_lock(&ctl->tree_lock);
2828 info = tree_search_offset(ctl, offset, 0, 0);
2834 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
2849 unlink_free_space(ctl, info, true);
2856 ret = link_free_space(ctl, info);
2869 ret = link_free_space(ctl, info);
2883 spin_unlock(&ctl->tree_lock);
2894 ret = remove_from_bitmap(ctl, info, &offset, &bytes);
2901 spin_unlock(&ctl->tree_lock);
2910 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2927 spin_lock(&ctl->tree_lock);
2928 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
2936 spin_unlock(&ctl->tree_lock);
2945 struct btrfs_free_space_ctl *ctl)
2949 spin_lock_init(&ctl->tree_lock);
2950 ctl->unit = fs_info->sectorsize;
2951 ctl->start = block_group->start;
2952 ctl->block_group = block_group;
2953 ctl->op = &free_space_op;
2954 ctl->free_space_bytes = RB_ROOT_CACHED;
2955 INIT_LIST_HEAD(&ctl->trimming_ranges);
2956 mutex_init(&ctl->cache_writeout_mutex);
2963 ctl->extents_thresh = (SZ_32K / 2) / sizeof(struct btrfs_free_space);
2976 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2979 lockdep_assert_held(&ctl->tree_lock);
3003 ctl->discardable_extents[BTRFS_STAT_CURR]--;
3004 ctl->discardable_bytes[BTRFS_STAT_CURR] -=
3008 try_merge_free_space(ctl, entry, false);
3009 steal_from_bitmap(ctl, entry, false);
3013 ctl->discardable_extents[BTRFS_STAT_CURR]++;
3014 ctl->discardable_bytes[BTRFS_STAT_CURR] +=
3018 tree_insert_offset(ctl, NULL, entry);
3019 rb_add_cached(&entry->bytes_index, &ctl->free_space_bytes,
3029 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3033 spin_lock(&ctl->tree_lock);
3042 cond_resched_lock(&ctl->tree_lock);
3044 __btrfs_remove_free_space_cache(ctl);
3046 spin_unlock(&ctl->tree_lock);
3055 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3060 spin_lock(&ctl->tree_lock);
3061 node = rb_first(&ctl->free_space_offset);
3074 spin_unlock(&ctl->tree_lock);
3082 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3095 spin_lock(&ctl->tree_lock);
3096 entry = find_free_space(ctl, &offset, &bytes_search,
3104 bitmap_clear_bits(ctl, entry, offset, bytes, true);
3110 free_bitmap(ctl, entry);
3112 unlink_free_space(ctl, entry, true);
3127 link_free_space(ctl, entry);
3131 spin_unlock(&ctl->tree_lock);
3151 struct btrfs_free_space_ctl *ctl;
3169 ctl = block_group->free_space_ctl;
3172 spin_lock(&ctl->tree_lock);
3174 spin_unlock(&ctl->tree_lock);
3188 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3197 err = search_bitmap(ctl, entry, &search_start, &search_bytes, true);
3205 bitmap_clear_bits(ctl, entry, ret, bytes, false);
3219 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3284 spin_lock(&ctl->tree_lock);
3289 ctl->free_space -= bytes;
3291 ctl->discardable_bytes[BTRFS_STAT_CURR] -= bytes;
3296 ctl->free_extents--;
3300 ctl->total_bitmaps--;
3301 recalculate_thresholds(ctl);
3303 ctl->discardable_extents[BTRFS_STAT_CURR]--;
3309 spin_unlock(&ctl->tree_lock);
3320 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3331 lockdep_assert_held(&ctl->tree_lock);
3333 i = offset_to_bit(entry->offset, ctl->unit,
3335 want_bits = bytes_to_bits(bytes, ctl->unit);
3336 min_bits = bytes_to_bits(min_bytes, ctl->unit);
3362 entry->max_extent_size = (u64)max_bits * ctl->unit;
3373 if (cluster->max_size < found_bits * ctl->unit)
3374 cluster->max_size = found_bits * ctl->unit;
3381 cluster->window_start = start * ctl->unit + entry->offset;
3382 rb_erase(&entry->offset_index, &ctl->free_space_offset);
3383 rb_erase_cached(&entry->bytes_index, &ctl->free_space_bytes);
3394 ret = tree_insert_offset(ctl, cluster, entry);
3398 total_found * ctl->unit, 1);
3413 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3422 lockdep_assert_held(&ctl->tree_lock);
3424 entry = tree_search_offset(ctl, offset, 0, 1);
3484 rb_erase(&entry->offset_index, &ctl->free_space_offset);
3485 rb_erase_cached(&entry->bytes_index, &ctl->free_space_bytes);
3486 ret = tree_insert_offset(ctl, cluster, entry);
3506 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3509 u64 bitmap_offset = offset_to_bitmap(ctl, offset);
3511 if (ctl->total_bitmaps == 0)
3522 entry = tree_search_offset(ctl, bitmap_offset, 1, 0);
3556 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3580 spin_lock(&ctl->tree_lock);
3586 if (ctl->free_space < bytes) {
3587 spin_unlock(&ctl->tree_lock);
3624 spin_unlock(&ctl->tree_lock);
3651 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3675 mutex_lock(&ctl->cache_writeout_mutex);
3685 mutex_unlock(&ctl->cache_writeout_mutex);
3710 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3723 mutex_lock(&ctl->cache_writeout_mutex);
3724 spin_lock(&ctl->tree_lock);
3726 if (ctl->free_space < minlen)
3729 entry = tree_search_offset(ctl, start, 0, 1);
3753 spin_unlock(&ctl->tree_lock);
3754 mutex_unlock(&ctl->cache_writeout_mutex);
3757 unlink_free_space(ctl, entry, true);
3770 link_free_space(ctl, entry);
3778 spin_unlock(&ctl->tree_lock);
3779 mutex_unlock(&ctl->cache_writeout_mutex);
3783 unlink_free_space(ctl, entry, true);
3787 spin_unlock(&ctl->tree_lock);
3790 list_add_tail(&trim_entry.list, &ctl->trimming_ranges);
3791 mutex_unlock(&ctl->cache_writeout_mutex);
3818 spin_unlock(&ctl->tree_lock);
3819 mutex_unlock(&ctl->cache_writeout_mutex);
3838 static void reset_trimming_bitmap(struct btrfs_free_space_ctl *ctl, u64 offset)
3842 spin_lock(&ctl->tree_lock);
3843 entry = tree_search_offset(ctl, offset, 1, 0);
3846 ctl->discardable_extents[BTRFS_STAT_CURR] +=
3848 ctl->discardable_bytes[BTRFS_STAT_CURR] += entry->bytes;
3853 spin_unlock(&ctl->tree_lock);
3856 static void end_trimming_bitmap(struct btrfs_free_space_ctl *ctl,
3861 ctl->discardable_extents[BTRFS_STAT_CURR] -=
3863 ctl->discardable_bytes[BTRFS_STAT_CURR] -= entry->bytes;
3876 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3881 u64 offset = offset_to_bitmap(ctl, start);
3888 mutex_lock(&ctl->cache_writeout_mutex);
3889 spin_lock(&ctl->tree_lock);
3891 if (ctl->free_space < minlen) {
3894 spin_unlock(&ctl->tree_lock);
3895 mutex_unlock(&ctl->cache_writeout_mutex);
3899 entry = tree_search_offset(ctl, offset, 1, 0);
3910 spin_unlock(&ctl->tree_lock);
3911 mutex_unlock(&ctl->cache_writeout_mutex);
3926 ret2 = search_bitmap(ctl, entry, &start, &bytes, false);
3933 end_trimming_bitmap(ctl, entry);
3936 spin_unlock(&ctl->tree_lock);
3937 mutex_unlock(&ctl->cache_writeout_mutex);
3947 spin_unlock(&ctl->tree_lock);
3948 mutex_unlock(&ctl->cache_writeout_mutex);
3954 spin_unlock(&ctl->tree_lock);
3955 mutex_unlock(&ctl->cache_writeout_mutex);
3970 bitmap_clear_bits(ctl, entry, start, bytes, true);
3972 free_bitmap(ctl, entry);
3974 spin_unlock(&ctl->tree_lock);
3977 list_add_tail(&trim_entry.list, &ctl->trimming_ranges);
3978 mutex_unlock(&ctl->cache_writeout_mutex);
3983 reset_trimming_bitmap(ctl, offset);
3990 offset += BITS_PER_BITMAP * ctl->unit;
3999 reset_trimming_bitmap(ctl, offset);
4017 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
4038 div64_u64_rem(end, BITS_PER_BITMAP * ctl->unit, &rem);
4041 reset_trimming_bitmap(ctl, offset_to_bitmap(ctl, end));
4188 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
4203 spin_lock(&ctl->tree_lock);
4207 ret = link_free_space(ctl, info);
4208 spin_unlock(&ctl->tree_lock);
4222 spin_lock(&ctl->tree_lock);
4223 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
4228 add_new_bitmap(ctl, info, offset);
4233 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes,
4238 spin_unlock(&ctl->tree_lock);
4258 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
4262 spin_lock(&ctl->tree_lock);
4263 info = tree_search_offset(ctl, offset, 0, 0);
4265 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
4278 bit_bytes = ctl->unit;
4279 ret = search_bitmap(ctl, info, &bit_off, &bit_bytes, false);
4331 spin_unlock(&ctl->tree_lock);