Branch data     Line data    Source code

       1                 :            : // SPDX-License-Identifier: GPL-2.0
       2                 :            : /*
       3                 :            :  *  fs/ext4/mballoc.h
       4                 :            :  *
       5                 :            :  *  Written by: Alex Tomas <alex@clusterfs.com>
       6                 :            :  *
       7                 :            :  */
       8                 :            : #ifndef _EXT4_MBALLOC_H
       9                 :            : #define _EXT4_MBALLOC_H
      10                 :            : 
      11                 :            : #include <linux/time.h>
      12                 :            : #include <linux/fs.h>
      13                 :            : #include <linux/namei.h>
      14                 :            : #include <linux/quotaops.h>
      15                 :            : #include <linux/buffer_head.h>
      16                 :            : #include <linux/module.h>
      17                 :            : #include <linux/swap.h>
      18                 :            : #include <linux/proc_fs.h>
      19                 :            : #include <linux/pagemap.h>
      20                 :            : #include <linux/seq_file.h>
      21                 :            : #include <linux/blkdev.h>
      22                 :            : #include <linux/mutex.h>
      23                 :            : #include "ext4_jbd2.h"
      24                 :            : #include "ext4.h"
      25                 :            : 
      26                 :            : /*
      27                 :            :  */
      28                 :            : #ifdef CONFIG_EXT4_DEBUG
      29                 :            : extern ushort ext4_mballoc_debug;
      30                 :            : 
      31                 :            : #define mb_debug(n, fmt, ...)                                           \
      32                 :            : do {                                                                    \
      33                 :            :         if ((n) <= ext4_mballoc_debug) {                             \
      34                 :            :                 printk(KERN_DEBUG "(%s, %d): %s: " fmt,                       \
      35                 :            :                        __FILE__, __LINE__, __func__, ##__VA_ARGS__);    \
      36                 :            :         }                                                               \
      37                 :            : } while (0)
      38                 :            : #else
      39                 :            : #define mb_debug(n, fmt, ...)   no_printk(fmt, ##__VA_ARGS__)
      40                 :            : #endif
      41                 :            : 
      42                 :            : #define EXT4_MB_HISTORY_ALLOC           1       /* allocation */
      43                 :            : #define EXT4_MB_HISTORY_PREALLOC        2       /* preallocated blocks used */
      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                 :            : /*
      56                 :            :  * with 'ext4_mb_stats' allocator will collect stats that will be
      57                 :            :  * shown at umount. The collecting costs though!
      58                 :            :  */
      59                 :            : #define MB_DEFAULT_STATS                0
      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                 :            : 
      80                 :            : 
      81                 :            : struct ext4_free_data {
      82                 :            :         /* this links the free block information from sb_info */
      83                 :            :         struct list_head                efd_list;
      84                 :            : 
      85                 :            :         /* this links the free block information from group_info */
      86                 :            :         struct rb_node                  efd_node;
      87                 :            : 
      88                 :            :         /* group which free block extent belongs */
      89                 :            :         ext4_group_t                    efd_group;
      90                 :            : 
      91                 :            :         /* free block extent */
      92                 :            :         ext4_grpblk_t                   efd_start_cluster;
      93                 :            :         ext4_grpblk_t                   efd_count;
      94                 :            : 
      95                 :            :         /* transaction which freed this extent */
      96                 :            :         tid_t                           efd_tid;
      97                 :            : };
      98                 :            : 
      99                 :            : struct ext4_prealloc_space {
     100                 :            :         struct list_head        pa_inode_list;
     101                 :            :         struct list_head        pa_group_list;
     102                 :            :         union {
     103                 :            :                 struct list_head pa_tmp_list;
     104                 :            :                 struct rcu_head pa_rcu;
     105                 :            :         } u;
     106                 :            :         spinlock_t              pa_lock;
     107                 :            :         atomic_t                pa_count;
     108                 :            :         unsigned                pa_deleted;
     109                 :            :         ext4_fsblk_t            pa_pstart;      /* phys. block */
     110                 :            :         ext4_lblk_t             pa_lstart;      /* log. block */
     111                 :            :         ext4_grpblk_t           pa_len;         /* len of preallocated chunk */
     112                 :            :         ext4_grpblk_t           pa_free;        /* how many blocks are free */
     113                 :            :         unsigned short          pa_type;        /* pa type. inode or group */
     114                 :            :         spinlock_t              *pa_obj_lock;
     115                 :            :         struct inode            *pa_inode;      /* hack, for history only */
     116                 :            : };
     117                 :            : 
     118                 :            : enum {
     119                 :            :         MB_INODE_PA = 0,
     120                 :            :         MB_GROUP_PA = 1
     121                 :            : };
     122                 :            : 
     123                 :            : struct ext4_free_extent {
     124                 :            :         ext4_lblk_t fe_logical;
     125                 :            :         ext4_grpblk_t fe_start; /* In cluster units */
     126                 :            :         ext4_group_t fe_group;
     127                 :            :         ext4_grpblk_t fe_len;   /* In cluster units */
     128                 :            : };
     129                 :            : 
     130                 :            : /*
     131                 :            :  * Locality group:
     132                 :            :  *   we try to group all related changes together
     133                 :            :  *   so that writeback can flush/allocate them together as well
     134                 :            :  *   Size of lg_prealloc_list hash is determined by MB_DEFAULT_GROUP_PREALLOC
     135                 :            :  *   (512). We store prealloc space into the hash based on the pa_free blocks
     136                 :            :  *   order value.ie, fls(pa_free)-1;
     137                 :            :  */
     138                 :            : #define PREALLOC_TB_SIZE 10
     139                 :            : struct ext4_locality_group {
     140                 :            :         /* for allocator */
     141                 :            :         /* to serialize allocates */
     142                 :            :         struct mutex            lg_mutex;
     143                 :            :         /* list of preallocations */
     144                 :            :         struct list_head        lg_prealloc_list[PREALLOC_TB_SIZE];
     145                 :            :         spinlock_t              lg_prealloc_lock;
     146                 :            : };
     147                 :            : 
     148                 :            : struct ext4_allocation_context {
     149                 :            :         struct inode *ac_inode;
     150                 :            :         struct super_block *ac_sb;
     151                 :            : 
     152                 :            :         /* original request */
     153                 :            :         struct ext4_free_extent ac_o_ex;
     154                 :            : 
     155                 :            :         /* goal request (normalized ac_o_ex) */
     156                 :            :         struct ext4_free_extent ac_g_ex;
     157                 :            : 
     158                 :            :         /* the best found extent */
     159                 :            :         struct ext4_free_extent ac_b_ex;
     160                 :            : 
     161                 :            :         /* copy of the best found extent taken before preallocation efforts */
     162                 :            :         struct ext4_free_extent ac_f_ex;
     163                 :            : 
     164                 :            :         __u16 ac_groups_scanned;
     165                 :            :         __u16 ac_found;
     166                 :            :         __u16 ac_tail;
     167                 :            :         __u16 ac_buddy;
     168                 :            :         __u16 ac_flags;         /* allocation hints */
     169                 :            :         __u8 ac_status;
     170                 :            :         __u8 ac_criteria;
     171                 :            :         __u8 ac_2order;         /* if request is to allocate 2^N blocks and
     172                 :            :                                  * N > 0, the field stores N, otherwise 0 */
     173                 :            :         __u8 ac_op;             /* operation, for history only */
     174                 :            :         struct page *ac_bitmap_page;
     175                 :            :         struct page *ac_buddy_page;
     176                 :            :         struct ext4_prealloc_space *ac_pa;
     177                 :            :         struct ext4_locality_group *ac_lg;
     178                 :            : };
     179                 :            : 
     180                 :            : #define AC_STATUS_CONTINUE      1
     181                 :            : #define AC_STATUS_FOUND         2
     182                 :            : #define AC_STATUS_BREAK         3
     183                 :            : 
     184                 :            : struct ext4_buddy {
     185                 :            :         struct page *bd_buddy_page;
     186                 :            :         void *bd_buddy;
     187                 :            :         struct page *bd_bitmap_page;
     188                 :            :         void *bd_bitmap;
     189                 :            :         struct ext4_group_info *bd_info;
     190                 :            :         struct super_block *bd_sb;
     191                 :            :         __u16 bd_blkbits;
     192                 :            :         ext4_group_t bd_group;
     193                 :            : };
     194                 :            : 
     195                 :            : static inline ext4_fsblk_t ext4_grp_offs_to_block(struct super_block *sb,
     196                 :            :                                         struct ext4_free_extent *fex)
     197                 :            : {
     198                 :     244758 :         return ext4_group_first_block_no(sb, fex->fe_group) +
     199                 :     122379 :                 (fex->fe_start << EXT4_SB(sb)->s_cluster_bits);
     200                 :            : }
     201                 :            : 
     202                 :            : typedef int (*ext4_mballoc_query_range_fn)(
     203                 :            :         struct super_block              *sb,
     204                 :            :         ext4_group_t                    agno,
     205                 :            :         ext4_grpblk_t                   start,
     206                 :            :         ext4_grpblk_t                   len,
     207                 :            :         void                            *priv);
     208                 :            : 
     209                 :            : int
     210                 :            : ext4_mballoc_query_range(
     211                 :            :         struct super_block              *sb,
     212                 :            :         ext4_group_t                    agno,
     213                 :            :         ext4_grpblk_t                   start,
     214                 :            :         ext4_grpblk_t                   end,
     215                 :            :         ext4_mballoc_query_range_fn     formatter,
     216                 :            :         void                            *priv);
     217                 :            : 
     218                 :            : #endif