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             :  * mb_debug() dynamic printk msgs could be used to debug mballoc code.
      28             :  */
      29             : #ifdef CONFIG_EXT4_DEBUG
      30             : #define mb_debug(sb, fmt, ...)                                          \
      31             :         pr_debug("[%s/%d] EXT4-fs (%s): (%s, %d): %s: " fmt,          \
      32             :                 current->comm, task_pid_nr(current), sb->s_id,            \
      33             :                __FILE__, __LINE__, __func__, ##__VA_ARGS__)
      34             : #else
      35             : #define mb_debug(sb, fmt, ...)  no_printk(fmt, ##__VA_ARGS__)
      36             : #endif
      37             : 
      38             : #define EXT4_MB_HISTORY_ALLOC           1       /* allocation */
      39             : #define EXT4_MB_HISTORY_PREALLOC        2       /* preallocated blocks used */
      40             : 
      41             : /*
      42             :  * How long mballoc can look for a best extent (in found extents)
      43             :  */
      44             : #define MB_DEFAULT_MAX_TO_SCAN          200
      45             : 
      46             : /*
      47             :  * How long mballoc must look for a best extent
      48             :  */
      49             : #define MB_DEFAULT_MIN_TO_SCAN          10
      50             : 
      51             : /*
      52             :  * with 's_mb_stats' allocator will collect stats that will be
      53             :  * shown at umount. The collecting costs though!
      54             :  */
      55             : #define MB_DEFAULT_STATS                0
      56             : 
      57             : /*
      58             :  * files smaller than MB_DEFAULT_STREAM_THRESHOLD are served
      59             :  * by the stream allocator, which purpose is to pack requests
      60             :  * as close each to other as possible to produce smooth I/O traffic
      61             :  * We use locality group prealloc space for stream request.
      62             :  * We can tune the same via /proc/fs/ext4/<partition>/stream_req
      63             :  */
      64             : #define MB_DEFAULT_STREAM_THRESHOLD     16      /* 64K */
      65             : 
      66             : /*
      67             :  * for which requests use 2^N search using buddies
      68             :  */
      69             : #define MB_DEFAULT_ORDER2_REQS          2
      70             : 
      71             : /*
      72             :  * default group prealloc size 512 blocks
      73             :  */
      74             : #define MB_DEFAULT_GROUP_PREALLOC       512
      75             : 
      76             : /*
      77             :  * Number of groups to search linearly before performing group scanning
      78             :  * optimization.
      79             :  */
      80             : #define MB_DEFAULT_LINEAR_LIMIT         4
      81             : 
      82             : /*
      83             :  * Minimum number of groups that should be present in the file system to perform
      84             :  * group scanning optimizations.
      85             :  */
      86             : #define MB_DEFAULT_LINEAR_SCAN_THRESHOLD        16
      87             : 
      88             : /*
      89             :  * The maximum order upto which CR_BEST_AVAIL_LEN can trim a particular
      90             :  * allocation request. Example, if we have an order 7 request and max trim order
      91             :  * of 3, we can trim this request upto order 4.
      92             :  */
      93             : #define MB_DEFAULT_BEST_AVAIL_TRIM_ORDER        3
      94             : 
      95             : /*
      96             :  * Number of valid buddy orders
      97             :  */
      98             : #define MB_NUM_ORDERS(sb)               ((sb)->s_blocksize_bits + 2)
      99             : 
     100             : struct ext4_free_data {
     101             :         /* this links the free block information from sb_info */
     102             :         struct list_head                efd_list;
     103             : 
     104             :         /* this links the free block information from group_info */
     105             :         struct rb_node                  efd_node;
     106             : 
     107             :         /* group which free block extent belongs */
     108             :         ext4_group_t                    efd_group;
     109             : 
     110             :         /* free block extent */
     111             :         ext4_grpblk_t                   efd_start_cluster;
     112             :         ext4_grpblk_t                   efd_count;
     113             : 
     114             :         /* transaction which freed this extent */
     115             :         tid_t                           efd_tid;
     116             : };
     117             : 
     118             : struct ext4_prealloc_space {
     119             :         union {
     120             :                 struct rb_node  inode_node;             /* for inode PA rbtree */
     121             :                 struct list_head        lg_list;        /* for lg PAs */
     122             :         } pa_node;
     123             :         struct list_head        pa_group_list;
     124             :         union {
     125             :                 struct list_head pa_tmp_list;
     126             :                 struct rcu_head pa_rcu;
     127             :         } u;
     128             :         spinlock_t              pa_lock;
     129             :         atomic_t                pa_count;
     130             :         unsigned                pa_deleted;
     131             :         ext4_fsblk_t            pa_pstart;      /* phys. block */
     132             :         ext4_lblk_t             pa_lstart;      /* log. block */
     133             :         ext4_grpblk_t           pa_len;         /* len of preallocated chunk */
     134             :         ext4_grpblk_t           pa_free;        /* how many blocks are free */
     135             :         unsigned short          pa_type;        /* pa type. inode or group */
     136             :         union {
     137             :                 rwlock_t                *inode_lock;    /* locks the rbtree holding this PA */
     138             :                 spinlock_t              *lg_lock;       /* locks the lg list holding this PA */
     139             :         } pa_node_lock;
     140             :         struct inode            *pa_inode;      /* used to get the inode during group discard */
     141             : };
     142             : 
     143             : enum {
     144             :         MB_INODE_PA = 0,
     145             :         MB_GROUP_PA = 1
     146             : };
     147             : 
     148             : struct ext4_free_extent {
     149             :         ext4_lblk_t fe_logical;
     150             :         ext4_grpblk_t fe_start; /* In cluster units */
     151             :         ext4_group_t fe_group;
     152             :         ext4_grpblk_t fe_len;   /* In cluster units */
     153             : };
     154             : 
     155             : /*
     156             :  * Locality group:
     157             :  *   we try to group all related changes together
     158             :  *   so that writeback can flush/allocate them together as well
     159             :  *   Size of lg_prealloc_list hash is determined by MB_DEFAULT_GROUP_PREALLOC
     160             :  *   (512). We store prealloc space into the hash based on the pa_free blocks
     161             :  *   order value.ie, fls(pa_free)-1;
     162             :  */
     163             : #define PREALLOC_TB_SIZE 10
     164             : struct ext4_locality_group {
     165             :         /* for allocator */
     166             :         /* to serialize allocates */
     167             :         struct mutex            lg_mutex;
     168             :         /* list of preallocations */
     169             :         struct list_head        lg_prealloc_list[PREALLOC_TB_SIZE];
     170             :         spinlock_t              lg_prealloc_lock;
     171             : };
     172             : 
     173             : struct ext4_allocation_context {
     174             :         struct inode *ac_inode;
     175             :         struct super_block *ac_sb;
     176             : 
     177             :         /* original request */
     178             :         struct ext4_free_extent ac_o_ex;
     179             : 
     180             :         /* goal request (normalized ac_o_ex) */
     181             :         struct ext4_free_extent ac_g_ex;
     182             : 
     183             :         /* the best found extent */
     184             :         struct ext4_free_extent ac_b_ex;
     185             : 
     186             :         /* copy of the best found extent taken before preallocation efforts */
     187             :         struct ext4_free_extent ac_f_ex;
     188             : 
     189             :         /*
     190             :          * goal len can change in CR1.5, so save the original len. This is
     191             :          * used while adjusting the PA window and for accounting.
     192             :          */
     193             :         ext4_grpblk_t   ac_orig_goal_len;
     194             : 
     195             :         __u32 ac_groups_considered;
     196             :         __u32 ac_flags;         /* allocation hints */
     197             :         __u16 ac_groups_scanned;
     198             :         __u16 ac_groups_linear_remaining;
     199             :         __u16 ac_found;
     200             :         __u16 ac_cX_found[EXT4_MB_NUM_CRS];
     201             :         __u16 ac_tail;
     202             :         __u16 ac_buddy;
     203             :         __u8 ac_status;
     204             :         __u8 ac_criteria;
     205             :         __u8 ac_2order;         /* if request is to allocate 2^N blocks and
     206             :                                  * N > 0, the field stores N, otherwise 0 */
     207             :         __u8 ac_op;             /* operation, for history only */
     208             :         struct page *ac_bitmap_page;
     209             :         struct page *ac_buddy_page;
     210             :         struct ext4_prealloc_space *ac_pa;
     211             :         struct ext4_locality_group *ac_lg;
     212             : };
     213             : 
     214             : #define AC_STATUS_CONTINUE      1
     215             : #define AC_STATUS_FOUND         2
     216             : #define AC_STATUS_BREAK         3
     217             : 
     218             : struct ext4_buddy {
     219             :         struct page *bd_buddy_page;
     220             :         void *bd_buddy;
     221             :         struct page *bd_bitmap_page;
     222             :         void *bd_bitmap;
     223             :         struct ext4_group_info *bd_info;
     224             :         struct super_block *bd_sb;
     225             :         __u16 bd_blkbits;
     226             :         ext4_group_t bd_group;
     227             : };
     228             : 
     229           0 : static inline ext4_fsblk_t ext4_grp_offs_to_block(struct super_block *sb,
     230             :                                         struct ext4_free_extent *fex)
     231             : {
     232           0 :         return ext4_group_first_block_no(sb, fex->fe_group) +
     233           0 :                 (fex->fe_start << EXT4_SB(sb)->s_cluster_bits);
     234             : }
     235             : 
     236             : typedef int (*ext4_mballoc_query_range_fn)(
     237             :         struct super_block              *sb,
     238             :         ext4_group_t                    agno,
     239             :         ext4_grpblk_t                   start,
     240             :         ext4_grpblk_t                   len,
     241             :         void                            *priv);
     242             : 
     243             : int
     244             : ext4_mballoc_query_range(
     245             :         struct super_block              *sb,
     246             :         ext4_group_t                    agno,
     247             :         ext4_grpblk_t                   start,
     248             :         ext4_grpblk_t                   end,
     249             :         ext4_mballoc_query_range_fn     formatter,
     250             :         void                            *priv);
     251             : 
     252             : #endif