Re: [PATCH 1/1] ext4: fix potential negative array index in do_split()

[Lukas Czerner <lczerner@redhat.com>]

On Fri, Jun 19, 2020 at 08:42:23AM -0500, Eric Sandeen wrote:
> On 6/19/20 2:08 AM, Lukas Czerner wrote:
> > On Fri, Jun 19, 2020 at 08:41:22AM +0200, Lukas Czerner wrote:
> >> On Wed, Jun 17, 2020 at 02:19:04PM -0500, Eric Sandeen wrote:
> >>> If for any reason a directory passed to do_split() does not have enough
> >>> active entries to exceed half the size of the block, we can end up
> >>> iterating over all "count" entries without finding a split point.
> >>>
> >>> In this case, count == move, and split will be zero, and we will
> >>> attempt a negative index into map[].
> >>>
> >>> Guard against this by detecting this case, and falling back to
> >>> split-to-half-of-count instead; in this case we will still have
> >>> plenty of space (> half blocksize) in each split block.
> >>>
> >>> Fixes: ef2b02d3e617 ("ext34: ensure do_split leaves enough free space in both blocks")
> >>> Signed-off-by: Eric Sandeen <sandeen@redhat.com>
> >>> ---
> >>>
> >>> diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
> >>> index a8aca4772aaa..8b60881f07ee 100644
> >>> --- a/fs/ext4/namei.c
> >>> +++ b/fs/ext4/namei.c
> >>> @@ -1858,7 +1858,7 @@ static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
> >>>  			     blocksize, hinfo, map);
> >>>  	map -= count;
> >>>  	dx_sort_map(map, count);
> >>> -	/* Split the existing block in the middle, size-wise */
> >>> +	/* Ensure that neither split block is over half full */
> >>>  	size = 0;
> >>>  	move = 0;
> >>>  	for (i = count-1; i >= 0; i--) {
> >>> @@ -1868,8 +1868,18 @@ static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
> >>>  		size += map[i].size;
> >>>  		move++;
> >>>  	}
> >>> -	/* map index at which we will split */
> >>> -	split = count - move;
> >>> +	/*
> >>> +	 * map index at which we will split
> >>> +	 *
> >>> +	 * If the sum of active entries didn't exceed half the block size, just
> >>> +	 * split it in half by count; each resulting block will have at least
> >>> +	 * half the space free.
> >>> +	 */
> >>> +	if (i > 0)
> >>> +		split = count - move;
> >>> +	else
> >>> +		split = count/2;
> >>
> >> Won't we have exactly the same problem as we did before your commit
> >> ef2b02d3e617cb0400eedf2668f86215e1b0e6af ? Since we do not know how much
> >> space we actually moved we might have not made enough space for the new
> >> entry ?
> >>
> >> Also since we have the move == count when the problem appears then it's
> >> clear that we never hit the condition
> >>
> >> 1865 →       →       /* is more than half of this entry in 2nd half of the block? */
> >> 1866 →       →       if (size + map[i].size/2 > blocksize/2)
> >> 1867 →       →       →       break;
> >>
> >> in the loop. This is surprising but it means the the entries must have
> >> gaps between them that are small enough that we can't fit the entry
> >> right in ? Should not we try to compact it before splitting, or is it
> >> the case that this should have been done somewhere else ?
> > 
> > The other possibility is that map[i].size is not right and indeed there
> > seems to be a bug in dx_make_map()
> > 
> > map_tail->size = le16_to_cpu(de->rec_len);
> > 
> > should be
> > 
> > map_tail->size = ext4_rec_len_from_disk(de->rec_len, blocksize));
> > 
> > right ? Otherwise with large enough records the size will be smaller
> > than it really is.
> 
> well, those are the same thing unless (PAGE_SIZE >= 65536) so I don't
> think that's the issue here.
> 
> static inline unsigned int
> ext4_rec_len_from_disk(__le16 dlen, unsigned blocksize)
> {
>         unsigned len = le16_to_cpu(dlen);
> 
> #if (PAGE_SIZE >= 65536)
> ...
> #else
>         return len;
> #endif
> }

Ah you're right. The reproducer for this is kind of unreliable as well
so that's why it looked to be fxied with this I guess.

> 
> Should be fixed for consistency, but seems to not be a root cause here.

Agreed.

-Lukas

> 
> > A quick look at fs/ext4/namei.c reveals couple of places there rec_len
> > is used without the conversion and we should check whether it needs
> > fixing.
> 
> ...
>