| 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
| ||
|
Message-ID: <6149e97b0909081824h78c6744p4602b70a938670fa@mail.gmail.com>
Date: Wed, 9 Sep 2009 09:24:57 +0800
From: Peng Tao <bergwolf@...il.com>
To: Greg Freemyer <greg.freemyer@...il.com>
Cc: linux-ext4@...r.kernel.org
Subject: Re: [PATCH] e4defrag: fallocate donor file only once
On Tue, Sep 8, 2009 at 11:41 PM, Greg Freemyer<greg.freemyer@...il.com> wrote:
> On Sat, Sep 5, 2009 at 12:29 PM, Peng Tao<bergwolf@...il.com> wrote:
>> Greg Freemyer wrote:
>>> On Fri, Sep 4, 2009 at 12:56 PM, Peng Tao<bergwolf@...il.com> wrote:
>>>> Greg Freemyer wrote:
>>>>> On Thu, Sep 3, 2009 at 11:08 PM, Peng Tao<bergwolf@...il.com> wrote:
>>>>>> On Thu, Sep 3, 2009 at 5:30 PM, Greg Freemyer<greg.freemyer@...il.com> wrote:
>>>>>>> On Thu, Sep 3, 2009 at 4:00 AM, Peng Tao<bergwolf@...il.com> wrote:
>>>>>>>> On Thu, Sep 3, 2009 at 6:09 AM, Greg Freemyer<greg.freemyer@...il.com> wrote:
>>>>>>>>> On Wed, Sep 2, 2009 at 11:35 AM, Peng Tao<bergwolf@...il.com> wrote:
>>>>>>>>>> If we allocate the donor file once for all, it will have a better chance
>>>>>>>>>> to be continuous.
>>>>>>>>>>
>>>>>>>>>> Signed-off-by: "Peng Tao" <bergwolf@...il.com>
>>>>>>>>> Seems like an improvement, but I'm not seeing any special handling for
>>>>>>>>> sparse files. (Not before or after this patch.)
>>>>>>>>>
>>>>>>>>> Seems like there should be an outer loop that identifies contiguous
>>>>>>>>> data block sets in a sparse file and defrags them individually as
>>>>>>>>> opposed to trying to defrag the entire file at once.
>>>>>>>>>
>>>>>>>>> My impression is that with a large sparse file, e4defrag currently
>>>>>>>>> (with or without this patch) would fallocate a full non-sparse donor
>>>>>>>>> set of blocks the full size of the original file, then swap in just
>>>>>>>>> the truly allocated blocks?
>>>>>>>> Thanks for the reminder. The original code takes good care of sparse
>>>>>>>> files in join_extents(). Please ignore my patch.
>>>>>>>>
>>>>>>>> Sorry for the noise.
>>>>>>> RFC from a more ext4 knowledgeable person than me:
>>>>>>>
>>>>>>> The code in e4defrag still looks way to complex. I don't see why it
>>>>>>> needs to know so much about extents and groups.
>>>>>>>
>>>>>>> I just looked at util/copy_sparse.c
>>>>>>>
>>>>>>> It simply loops through all the blocks in the source file and calls
>>>>>>> ioctl(fd, FIBMAP, &b) to see if they are allocated vs. sparse,
>>>>>>>
>>>>>>> If allocated it copies the block from src to dest. Pretty straight
>>>>>>> forward and has none of the complexity of e4defrag.
>>>>>>>
>>>>>>> Seems to me e4defrag should have the actual defrag_file() rewritten to
>>>>>>> be something like:
>>>>>>>
>>>>>>> defrag_file() {
>>>>>>> loop through the blocks looking for the contiguous set of data blocks.
>>>>>>> defrag_contiguous_data(start_block, num_blocks)
>>>>>>> }
>>>>>>>
>>>>>>> defrag_contiguous_data(start_block, num_blocks) {
>>>>>>> // allocate one full extent at a time and donate the blocks to orig file
>>>>>>> for(start=start_block; start < start_block, num_blocks; start+=chunk) {
>>>>>>> fallocate(chunk);
>>>>>>> move_ext(orig, donor, start, 0, chunk);
>>>>>>> }
>>>>>>> }
>>>>>>>
>>>>>>> And then set chunk to be the max size of one extent. Maybe the
>>>>>>> "chunk" should be bigger than one extent?
>>>>>>>
>>>>>>> Also, I did not put any logic in above to show testing to see if the
>>>>>>> new file is less fragmented than the original. That will add to the
>>>>>>> complexity, but hopefully the actual defrag logic can be as relatively
>>>>>>> simple as the above instead of what it is now.
>>>>>>>
>>>>>>> Anyway, t would be a major change to e4defrag, but it seems that it
>>>>>>> would give ext4 a much better chance to reorganize itself by calling
>>>>>>> fallocate on full extent size chunks at minimum, instead of what the
>>>>>>> code currently does.
>>>>>> Hi, Greg,
>>>>>>
>>>>>> The current e4defrag is doing most of work exactly same as your RFC,
>>>>>> and in a nicer manner. If you look into the code path, you'll see that
>>>>>> its logic is very much like the RFC except that it first fallocates a
>>>>>> donor file to see if a defragmentation is really necessary so it won't
>>>>>> have to fall back during defragmentation, which IMO is a good design
>>>>>> point.
>>>>>>
>>>>>> Please correct me if I understand anything wrong.
>>>>> I've looked a lot more at the current code. I'm pretty sure this is right:
>>>>>
>>>>> First, assume defrag of a non-sparse 1TB file.
>>>>>
>>>>> The current code will walk the extent tree and create a single extent
>>>>> group that covers the full 1TB, then call fallocate to try to get 1TB
>>>>> of donor blocks. Then compare the number of extents in the original
>>>>> and the donor. If the donor has less it will swap in the donor
>>>>> blocks.
>>>>>
>>>>> It seems much smarter work on extent size chunks (or whatever best
>>>>> fits the kernels block structure.
>>>>>
>>>>> ie.
>>>>>
>>>>> for (start_block=0; start_block < max_blocks; start_block+=
>>>>> max_blocks_in_extent)
>>>>>
>>>>> current_extents = num_extents_in_block_range(start_block,
>>>>> start+max_blocks_in_extent);
>>>>>
>>>>> if (current_extents == 1) continue;
>>>>>
>>>>> // allocate a sparse file with perfectly aligned donor blocks as
>>>>> currently required by kernel
>>>>> fallocate(start_block * block_size, max_blocks_in_extent * block_size);
>>>>>
>>>>> donor_extents = num_extents_in_block_range(start_block,
>>>>> start+max_blocks_in_extent);
>>>>>
>>>>> if (donor_extents < current_extents)
>>>>> donate_donor_blocks_to_orig(start_block,
>>>>> start+max_blocks_in_extent);
>>>>>
>>>>> )
>>>>>
>>>>> And in the case of a sparse file, it seems much easier to understand
>>>>> if the above is called on each logically contiguous set or data
>>>>> blocks. Seriously, why bother the kernel by making it able to accept
>>>>> a block range that has holes in it.
>>>> Agreed. If the kernel doesn't have to deal with holes, the EXT4_IOC_MOVE_EXT
>>>> ioctl can be much simplified.
>>>>> It seems reasonable for the kernel to check the block range being
>>>>> passed in and if the orig files has a hole in the middle of it, then
>>>>> return an error.
>>>>>
>>>>> Back to e4defrag, even if the code is not greatly simplified, the
>>>>> above seems like it would use far less resources than the current
>>>>> code. Think about a large file that has the first 90% of the blocks
>>>>> defrag'ed. The above would cause just the tail to be defrag'ed, not
>>>>> the entire file.
>>>> Yes, it makes sense. Are you planning some patch for above changes?
>>>
>>> I'm "planning", but I doubt that I get to it for a few weeks. If you
>>> or someone else has time, that would be great.
>> I don't have time for it in a few weeks either. So if anyone is interested,
>> please drop in.
>>>
>>> Greg
>>
>>
>> --
>> Best Regards,
>> Peng Tao
>> State Key Laboratory of Networking and Switching Technology
>> Beijing Univ. of Posts and Telecoms.
>>
>
> If I take a shot at this, which branch should a base my patch against? Master?
Yes, I think so. I verified that e4defrag.c is the same in master and pu branch.
>
> Thanks
> Greg
>
--
Cheers,
Peng Tao
State Key Laboratory of Networking and Switching Technology
Beijing Univ. of Posts and Telecoms.
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Powered by blists - more mailing lists