linux-kernel - Re: [PATCH 0/5] *** Introduce new space allocation algorithm ***

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CANubcdWwg3OB_YV4CteC7ZZBaQXOuvFG1oS7uN+TpabS=Z=Z2Q@mail.gmail.com>
Date: Mon, 4 Nov 2024 09:49:32 +0800
From: Stephen Zhang <starzhangzsd@...il.com>
To: djwong@...nel.org, dchinner@...hat.com, leo.lilong@...wei.com, 
	wozizhi@...wei.com, osandov@...com, xiang@...nel.org, 
	zhangjiachen.jaycee@...edance.com
Cc: linux-xfs@...r.kernel.org, linux-kernel@...r.kernel.org, 
	zhangshida@...inos.cn
Subject: Re: [PATCH 0/5] *** Introduce new space allocation algorithm ***

Hi all,

I just send the scripts to test these series here.

Cheers,
Shida

zhangshida <starzhangzsd@...il.com> 于2024年11月4日周一 09:44写道：
>
> From: Shida Zhang <zhangshida@...inos.cn>
>
> Hi all,
>
> Recently, we've been encounter xfs problems from our two
> major users continuously.
> They are all manifested as the same phonomenon: a xfs
> filesystem can't touch new file when there are nearly
> half of the available space even with sparse inode enabled.
>
> It turns out that the filesystem is too fragmented to have
> enough continuous free space to create a new file.
>
> Life still has to goes on.
> But from our users' perspective, worse than the situation
> that xfs is hard to use is that xfs is non-able to use,
> since even one single file can't be created now.
>
> So we try to introduce a new space allocation algorithm to
> solve this.
>
> To achieve that, we try to propose a new concept:
>    Allocation Fields, where its name is borrowed from the
> mathmatical concepts(Groups,Rings,Fields), will be
> abbrivated as AF in the rest of the article.
>
> what is a AF?
> An one-pic-to-say-it-all version of explaination:
>
> |<--------+ af 0 +-------->|<--+ af 1 +-->| af 2|
> |------------------------------------------------+
> | ag 0 | ag 1 | ag 2 | ag 3| ag 4 | ag 5 | ag 6 |
> +------------------------------------------------+
>
> A text-based definition of AF:
> 1.An AF is a incore-only concept comparing with the on-disk
>   AG concept.
> 2.An AF is consisted of a continuous series of AGs.
> 3.Lower AFs will NEVER go to higher AFs for allocation if
>   it can complete it in the current AF.
>
> Rule 3 can serve as a barrier between the AF to slow down
> the over-speed extending of fragmented pieces.
>
> With these patches applied, the code logic will be exactly
> the same as the original code logic, unless you run with the
> extra mount opiton. For example:
>    mount -o af1=1 $dev $mnt
>
> That will change the default AF layout:
>
> |<--------+ af 0 +--------->|
> |----------------------------
> | ag 0 | ag 1 | ag 2 | ag 3 |
> +----------------------------
>
> to :
>
> |<-----+ af 0 +----->|<af 1>|
> |----------------------------
> | ag 0 | ag 1 | ag 2 | ag 3 |
> +----------------------------
>
> So the 'af1=1' here means the start agno is one ag away from
> the m_sb.agcount.
>
> We did some tests verify it. You can verify it yourself
> by running the following the command:
>
> 1. Create an 1g sized img file and formated it as xfs:
>   dd if=/dev/zero of=test.img bs=1M count=1024
>   mkfs.xfs -f test.img
>   sync
> 2. Make a mount directory:
>   mkdir mnt
> 3. Run the auto_frag.sh script, which will call another scripts
>   frag.sh. These scripts will be attached in the mail.
>   To enable the AF, run:
>     ./auto_frag.sh 1
>   To disable the AF, run:
>     ./auto_frag.sh 0
>
> Please feel free to communicate with us if you have any thoughts
> about these problems.
>
> Cheers,
> Shida
>
>
> Shida Zhang (5):
>   xfs: add two wrappers for iterating ags in a AF
>   xfs: add two mp member to record the alloction field layout
>   xfs: add mount options as a way to change the AF layout
>   xfs: add infrastructure to support AF allocation algorithm
>   xfs: modify the logic to comply with AF rules
>
>  fs/xfs/libxfs/xfs_ag.h         | 17 ++++++++++++
>  fs/xfs/libxfs/xfs_alloc.c      | 20 ++++++++++++++-
>  fs/xfs/libxfs/xfs_alloc.h      |  2 ++
>  fs/xfs/libxfs/xfs_bmap.c       | 47 ++++++++++++++++++++++++++++++++--
>  fs/xfs/libxfs/xfs_bmap_btree.c |  2 ++
>  fs/xfs/xfs_mount.h             |  3 +++
>  fs/xfs/xfs_super.c             | 12 ++++++++-
>  7 files changed, 99 insertions(+), 4 deletions(-)
>
> --
> 2.33.0
>

Download attachment "auto_frag.sh" of type "application/x-shellscript" (593 bytes)

Download attachment "frag.sh" of type "application/x-shellscript" (2087 bytes)