Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 1 | /* |
| 2 | * fs/ext4/mballoc.h |
| 3 | * |
| 4 | * Written by: Alex Tomas <alex@clusterfs.com> |
| 5 | * |
| 6 | */ |
| 7 | #ifndef _EXT4_MBALLOC_H |
| 8 | #define _EXT4_MBALLOC_H |
| 9 | |
| 10 | #include <linux/time.h> |
| 11 | #include <linux/fs.h> |
| 12 | #include <linux/namei.h> |
| 13 | #include <linux/quotaops.h> |
| 14 | #include <linux/buffer_head.h> |
| 15 | #include <linux/module.h> |
| 16 | #include <linux/swap.h> |
| 17 | #include <linux/proc_fs.h> |
| 18 | #include <linux/pagemap.h> |
| 19 | #include <linux/seq_file.h> |
Theodore Ts'o | 8a0aba7 | 2008-10-16 10:06:27 -0400 | [diff] [blame] | 20 | #include <linux/blkdev.h> |
Aneesh Kumar K.V | 920313a | 2009-01-05 21:36:19 -0500 | [diff] [blame] | 21 | #include <linux/mutex.h> |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 22 | #include "ext4_jbd2.h" |
| 23 | #include "ext4.h" |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 24 | |
| 25 | /* |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 26 | */ |
Theodore Ts'o | 6ba495e | 2009-09-18 13:38:55 -0400 | [diff] [blame] | 27 | #ifdef CONFIG_EXT4_DEBUG |
Theodore Ts'o | a0b30c1 | 2013-02-09 16:28:20 -0500 | [diff] [blame] | 28 | extern ushort ext4_mballoc_debug; |
Theodore Ts'o | 6ba495e | 2009-09-18 13:38:55 -0400 | [diff] [blame] | 29 | |
| 30 | #define mb_debug(n, fmt, a...) \ |
| 31 | do { \ |
Theodore Ts'o | a0b30c1 | 2013-02-09 16:28:20 -0500 | [diff] [blame] | 32 | if ((n) <= ext4_mballoc_debug) { \ |
Theodore Ts'o | 6ba495e | 2009-09-18 13:38:55 -0400 | [diff] [blame] | 33 | printk(KERN_DEBUG "(%s, %d): %s: ", \ |
| 34 | __FILE__, __LINE__, __func__); \ |
| 35 | printk(fmt, ## a); \ |
| 36 | } \ |
| 37 | } while (0) |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 38 | #else |
Patrick Palka | 024949e | 2014-02-17 20:50:59 -0500 | [diff] [blame] | 39 | #define mb_debug(n, fmt, a...) no_printk(fmt, ## a) |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 40 | #endif |
| 41 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 42 | #define EXT4_MB_HISTORY_ALLOC 1 /* allocation */ |
| 43 | #define EXT4_MB_HISTORY_PREALLOC 2 /* preallocated blocks used */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 44 | |
| 45 | /* |
| 46 | * How long mballoc can look for a best extent (in found extents) |
| 47 | */ |
| 48 | #define MB_DEFAULT_MAX_TO_SCAN 200 |
| 49 | |
| 50 | /* |
| 51 | * How long mballoc must look for a best extent |
| 52 | */ |
| 53 | #define MB_DEFAULT_MIN_TO_SCAN 10 |
| 54 | |
| 55 | /* |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 56 | * with 'ext4_mb_stats' allocator will collect stats that will be |
| 57 | * shown at umount. The collecting costs though! |
| 58 | */ |
Theodore Ts'o | 90576c0 | 2009-09-29 15:51:30 -0400 | [diff] [blame] | 59 | #define MB_DEFAULT_STATS 0 |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 60 | |
| 61 | /* |
| 62 | * files smaller than MB_DEFAULT_STREAM_THRESHOLD are served |
| 63 | * by the stream allocator, which purpose is to pack requests |
| 64 | * as close each to other as possible to produce smooth I/O traffic |
| 65 | * We use locality group prealloc space for stream request. |
| 66 | * We can tune the same via /proc/fs/ext4/<parition>/stream_req |
| 67 | */ |
| 68 | #define MB_DEFAULT_STREAM_THRESHOLD 16 /* 64K */ |
| 69 | |
| 70 | /* |
| 71 | * for which requests use 2^N search using buddies |
| 72 | */ |
| 73 | #define MB_DEFAULT_ORDER2_REQS 2 |
| 74 | |
| 75 | /* |
| 76 | * default group prealloc size 512 blocks |
| 77 | */ |
| 78 | #define MB_DEFAULT_GROUP_PREALLOC 512 |
| 79 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 80 | |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 81 | struct ext4_free_data { |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 82 | /* MUST be the first member */ |
| 83 | struct ext4_journal_cb_entry efd_jce; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 84 | |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 85 | /* ext4_free_data private data starts from here */ |
| 86 | |
| 87 | /* this links the free block information from group_info */ |
| 88 | struct rb_node efd_node; |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 89 | |
| 90 | /* group which free block extent belongs */ |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 91 | ext4_group_t efd_group; |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 92 | |
| 93 | /* free block extent */ |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 94 | ext4_grpblk_t efd_start_cluster; |
| 95 | ext4_grpblk_t efd_count; |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 96 | |
| 97 | /* transaction which freed this extent */ |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 98 | tid_t efd_tid; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 99 | }; |
| 100 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 101 | struct ext4_prealloc_space { |
| 102 | struct list_head pa_inode_list; |
| 103 | struct list_head pa_group_list; |
| 104 | union { |
| 105 | struct list_head pa_tmp_list; |
| 106 | struct rcu_head pa_rcu; |
| 107 | } u; |
| 108 | spinlock_t pa_lock; |
| 109 | atomic_t pa_count; |
| 110 | unsigned pa_deleted; |
| 111 | ext4_fsblk_t pa_pstart; /* phys. block */ |
| 112 | ext4_lblk_t pa_lstart; /* log. block */ |
Eric Sandeen | a36b449 | 2009-08-25 22:36:45 -0400 | [diff] [blame] | 113 | ext4_grpblk_t pa_len; /* len of preallocated chunk */ |
| 114 | ext4_grpblk_t pa_free; /* how many blocks are free */ |
Aneesh Kumar K.V | cc0fb9a | 2009-03-27 17:16:58 -0400 | [diff] [blame] | 115 | unsigned short pa_type; /* pa type. inode or group */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 116 | spinlock_t *pa_obj_lock; |
| 117 | struct inode *pa_inode; /* hack, for history only */ |
| 118 | }; |
| 119 | |
Aneesh Kumar K.V | cc0fb9a | 2009-03-27 17:16:58 -0400 | [diff] [blame] | 120 | enum { |
| 121 | MB_INODE_PA = 0, |
| 122 | MB_GROUP_PA = 1 |
| 123 | }; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 124 | |
| 125 | struct ext4_free_extent { |
| 126 | ext4_lblk_t fe_logical; |
Theodore Ts'o | 53accfa | 2011-09-09 18:48:51 -0400 | [diff] [blame] | 127 | ext4_grpblk_t fe_start; /* In cluster units */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 128 | ext4_group_t fe_group; |
Theodore Ts'o | 53accfa | 2011-09-09 18:48:51 -0400 | [diff] [blame] | 129 | ext4_grpblk_t fe_len; /* In cluster units */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 130 | }; |
| 131 | |
| 132 | /* |
| 133 | * Locality group: |
| 134 | * we try to group all related changes together |
| 135 | * so that writeback can flush/allocate them together as well |
Aneesh Kumar K.V | 6be2ded | 2008-07-23 14:14:05 -0400 | [diff] [blame] | 136 | * Size of lg_prealloc_list hash is determined by MB_DEFAULT_GROUP_PREALLOC |
| 137 | * (512). We store prealloc space into the hash based on the pa_free blocks |
| 138 | * order value.ie, fls(pa_free)-1; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 139 | */ |
Aneesh Kumar K.V | 6be2ded | 2008-07-23 14:14:05 -0400 | [diff] [blame] | 140 | #define PREALLOC_TB_SIZE 10 |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 141 | struct ext4_locality_group { |
| 142 | /* for allocator */ |
Aneesh Kumar K.V | 6be2ded | 2008-07-23 14:14:05 -0400 | [diff] [blame] | 143 | /* to serialize allocates */ |
| 144 | struct mutex lg_mutex; |
| 145 | /* list of preallocations */ |
| 146 | struct list_head lg_prealloc_list[PREALLOC_TB_SIZE]; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 147 | spinlock_t lg_prealloc_lock; |
| 148 | }; |
| 149 | |
| 150 | struct ext4_allocation_context { |
| 151 | struct inode *ac_inode; |
| 152 | struct super_block *ac_sb; |
| 153 | |
| 154 | /* original request */ |
| 155 | struct ext4_free_extent ac_o_ex; |
| 156 | |
Coly Li | 58696f3 | 2011-02-24 14:10:00 -0500 | [diff] [blame] | 157 | /* goal request (normalized ac_o_ex) */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 158 | struct ext4_free_extent ac_g_ex; |
| 159 | |
| 160 | /* the best found extent */ |
| 161 | struct ext4_free_extent ac_b_ex; |
| 162 | |
Robin Dong | ff3fc17 | 2011-10-31 18:55:50 -0400 | [diff] [blame] | 163 | /* copy of the best found extent taken before preallocation efforts */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 164 | struct ext4_free_extent ac_f_ex; |
| 165 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 166 | __u16 ac_groups_scanned; |
| 167 | __u16 ac_found; |
| 168 | __u16 ac_tail; |
| 169 | __u16 ac_buddy; |
| 170 | __u16 ac_flags; /* allocation hints */ |
| 171 | __u8 ac_status; |
| 172 | __u8 ac_criteria; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 173 | __u8 ac_2order; /* if request is to allocate 2^N blocks and |
| 174 | * N > 0, the field stores N, otherwise 0 */ |
| 175 | __u8 ac_op; /* operation, for history only */ |
| 176 | struct page *ac_bitmap_page; |
| 177 | struct page *ac_buddy_page; |
| 178 | struct ext4_prealloc_space *ac_pa; |
| 179 | struct ext4_locality_group *ac_lg; |
| 180 | }; |
| 181 | |
| 182 | #define AC_STATUS_CONTINUE 1 |
| 183 | #define AC_STATUS_FOUND 2 |
| 184 | #define AC_STATUS_BREAK 3 |
| 185 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 186 | struct ext4_buddy { |
| 187 | struct page *bd_buddy_page; |
| 188 | void *bd_buddy; |
| 189 | struct page *bd_bitmap_page; |
| 190 | void *bd_bitmap; |
| 191 | struct ext4_group_info *bd_info; |
| 192 | struct super_block *bd_sb; |
| 193 | __u16 bd_blkbits; |
| 194 | ext4_group_t bd_group; |
| 195 | }; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 196 | |
Aneesh Kumar K.V | c3a326a | 2008-11-25 15:11:52 -0500 | [diff] [blame] | 197 | static inline ext4_fsblk_t ext4_grp_offs_to_block(struct super_block *sb, |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 198 | struct ext4_free_extent *fex) |
| 199 | { |
Theodore Ts'o | 3212a80 | 2011-09-09 18:46:51 -0400 | [diff] [blame] | 200 | return ext4_group_first_block_no(sb, fex->fe_group) + |
| 201 | (fex->fe_start << EXT4_SB(sb)->s_cluster_bits); |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 202 | } |
| 203 | #endif |