From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.2 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_SANE_1 autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8EEFFC433E0 for ; Fri, 19 Jun 2020 13:39:56 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 783F320DD4 for ; Fri, 19 Jun 2020 13:39:56 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732993AbgFSNj4 (ORCPT ); Fri, 19 Jun 2020 09:39:56 -0400 Received: from sandeen.net ([63.231.237.45]:41186 "EHLO sandeen.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1731806AbgFSNjz (ORCPT ); Fri, 19 Jun 2020 09:39:55 -0400 Received: from [10.0.0.4] (liberator [10.0.0.4]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by sandeen.net (Postfix) with ESMTPSA id 262F44CEBDF; Fri, 19 Jun 2020 08:39:30 -0500 (CDT) Subject: Re: [PATCH 1/1] ext4: fix potential negative array index in do_split() To: Lukas Czerner , Eric Sandeen Cc: "linux-ext4@vger.kernel.org" References: <20200619064122.vj346xptid5viogv@work> From: Eric Sandeen Autocrypt: addr=sandeen@sandeen.net; prefer-encrypt=mutual; keydata= mQINBE6x99QBEADMR+yNFBc1Y5avoUhzI/sdR9ANwznsNpiCtZlaO4pIWvqQJCjBzp96cpCs nQZV32nqJBYnDpBDITBqTa/EF+IrHx8gKq8TaSBLHUq2ju2gJJLfBoL7V3807PQcI18YzkF+ WL05ODFQ2cemDhx5uLghHEeOxuGj+1AI+kh/FCzMedHc6k87Yu2ZuaWF+Gh1W2ix6hikRJmQ vj5BEeAx7xKkyBhzdbNIbbjV/iGi9b26B/dNcyd5w2My2gxMtxaiP7q5b6GM2rsQklHP8FtW ZiYO7jsg/qIppR1C6Zr5jK1GQlMUIclYFeBbKggJ9mSwXJH7MIftilGQ8KDvNuV5AbkronGC sEEHj2khs7GfVv4pmUUHf1MRIvV0x3WJkpmhuZaYg8AdJlyGKgp+TQ7B+wCjNTdVqMI1vDk2 BS6Rg851ay7AypbCPx2w4d8jIkQEgNjACHVDU89PNKAjScK1aTnW+HNUqg9BliCvuX5g4z2j gJBs57loTWAGe2Ve3cMy3VoQ40Wt3yKK0Eno8jfgzgb48wyycINZgnseMRhxc2c8hd51tftK LKhPj4c7uqjnBjrgOVaVBupGUmvLiePlnW56zJZ51BR5igWnILeOJ1ZIcf7KsaHyE6B1mG+X dmYtjDhjf3NAcoBWJuj8euxMB6TcQN2MrSXy5wSKaw40evooGwARAQABtCVFcmljIFIuIFNh bmRlZW4gPHNhbmRlZW5Ac2FuZGVlbi5uZXQ+iQI7BBMBAgAlAhsDBgsJCAcDAgYVCAIJCgsE FgIDAQIeAQIXgAUCUzMzbAIZAQAKCRAgrhaS4T3e4Fr7D/wO+fenqVvHjq21SCjDCrt8HdVj aJ28B1SqSU2toxyg5I160GllAxEHpLFGdbFAhQfBtnmlY9eMjwmJb0sCIrkrB6XNPSPA/B2B UPISh0z2odJv35/euJF71qIFgWzp2czJHkHWwVZaZpMWWNvsLIroXoR+uA9c2V1hQFVAJZyk EE4xzfm1+oVtjIC12B9tTCuS00pY3AUy21yzNowT6SSk7HAzmtG/PJ/uSB5wEkwldB6jVs2A sjOg1wMwVvh/JHilsQg4HSmDfObmZj1d0RWlMWcUE7csRnCE0ZWBMp/ttTn+oosioGa09HAS 9jAnauznmYg43oQ5Akd8iQRxz5I58F/+JsdKvWiyrPDfYZtFS+UIgWD7x+mHBZ53Qjazszox gjwO9ehZpwUQxBm4I0lPDAKw3HJA+GwwiubTSlq5PS3P7QoCjaV8llH1bNFZMz2o8wPANiDx 5FHgpRVgwLHakoCU1Gc+LXHXBzDXt7Cj02WYHdFzMm2hXaslRdhNGowLo1SXZFXa41KGTlNe 4di53y9CK5ynV0z+YUa+5LR6RdHrHtgywdKnjeWdqhoVpsWIeORtwWGX8evNOiKJ7j0RsHha WrePTubr5nuYTDsQqgc2r4aBIOpeSRR2brlT/UE3wGgy9LY78L4EwPR0MzzecfE1Ws60iSqw Pu3vhb7h3bkCDQROsffUARAA0DrUifTrXQzqxO8aiQOC5p9Tz25Np/Tfpv1rofOwL8VPBMvJ X4P5l1V2yd70MZRUVgjmCydEyxLJ6G2YyHO2IZTEajUY0Up+b3ErOpLpZwhvgWatjifpj6bB SKuDXeThqFdkphF5kAmgfVAIkan5SxWK3+S0V2F/oxstIViBhMhDwI6XsRlnVBoLLYcEilxA 2FlRUS7MOZGmRJkRtdGD5koVZSM6xVZQSmfEBaYQ/WJBGJQdPy94nnlAVn3lH3+N7pXvNUuC GV+t4YUt3tLcRuIpYBCOWlc7bpgeCps5Xa0dIZgJ8Louu6OBJ5vVXjPxTlkFdT0S0/uerCG5 1u8p6sGRLnUeAUGkQfIUqGUjW2rHaXgWNvzOV6i3tf9YaiXKl3avFaNW1kKBs0T5M1cnlWZU Utl6k04lz5OjoNY9J/bGyV3DSlkblXRMK87iLYQSrcV6cFz9PRl4vW1LGff3xRQHngeN5fPx ze8X5NE3hb+SSwyMSEqJxhVTXJVfQWWW0dQxP7HNwqmOWYF/6m+1gK/Y2gY3jAQnsWTru4RV TZGnKwEPmOCpSUvsTRXsVHgsWJ70qd0yOSjWuiv4b8vmD3+QFgyvCBxPMdP3xsxN5etheLMO gRwWpLn6yNFq/xtgs+ECgG+gR78yXQyA7iCs5tFs2OrMqV5juSMGmn0kxJUAEQEAAYkCHwQY AQIACQUCTrH31AIbDAAKCRAgrhaS4T3e4BKwD/0ZOOmUNOZCSOLAMjZx3mtYtjYgfUNKi0ki YPveGoRWTqbis8UitPtNrG4XxgzLOijSdOEzQwkdOIp/QnZhGNssMejCnsluK0GQd+RkFVWN mcQT78hBeGcnEMAXZKq7bkIKzvc06GFmkMbX/gAl6DiNGv0UNAX+5FYh+ucCJZSyAp3sA+9/ LKjxnTedX0aygXA6rkpX0Y0FvN/9dfm47+LGq7WAqBOyYTU3E6/+Z72bZoG/cG7ANLxcPool LOrU43oqFnD8QwcN56y4VfFj3/jDF2MX3xu4v2OjglVjMEYHTCxP3mpxesGHuqOit/FR+mF0 MP9JGfj6x+bj/9JMBtCW1bY/aPeMdPGTJvXjGtOVYblGZrSjXRn5++Uuy36CvkcrjuziSDG+ JEexGxczWwN4mrOQWhMT5Jyb+18CO+CWxJfHaYXiLEW7dI1AynL4jjn4W0MSiXpWDUw+fsBO Pk6ah10C4+R1Jc7dyUsKksMfvvhRX1hTIXhth85H16706bneTayZBhlZ/hK18uqTX+s0onG/ m1F3vYvdlE4p2ts1mmixMF7KajN9/E5RQtiSArvKTbfsB6Two4MthIuLuf+M0mI4gPl9SPlf fWCYVPhaU9o83y1KFbD/+lh1pjP7bEu/YudBvz7F2Myjh4/9GUAijrCTNeDTDAgvIJDjXuLX pA== Message-ID: <04a5b98c-4bb7-4861-76c3-dd0b0c6a6610@sandeen.net> Date: Fri, 19 Jun 2020 08:39:53 -0500 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:68.0) Gecko/20100101 Thunderbird/68.9.0 MIME-Version: 1.0 In-Reply-To: <20200619064122.vj346xptid5viogv@work> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit Sender: linux-ext4-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-ext4@vger.kernel.org On 6/19/20 1:41 AM, 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. ... >> + /* >> + * 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 ? I don't think so - while we don't have the original reproducer, I assume that it was the case where the block was very full, and splitting by count left us with one of the split blocks still over half full (because ensuring that we split in half by size seemed to fix it) In this case, the sum of the active entries was <= half the block size. So if we split by count, we're guaranteed to have >= half the block size free in each side of the split. > 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 ? Yes, that's exactly what happened - see my 0/1 cover letter. Maybe that should be in the patch description itself. ALso, yes compaction would help but I was unclear as to whether that should be done here, is the side effect of some other bug, etc. In general, we do seem to do compaction elsewhere and I don't know how we got to this point. > If we really want ot be fair and we want to split it right in the middle > of the entries size-wise then we need to keep track of of sum of the > entries and decide based on that, not blocksize/2. But maybe the problem > could be solved by compacting the entries together because the condition > seems to rely on that. I thought about that as well, but it took a bit more code to do; we could make make_map() return both count and total size, for example. But based on my theory above that both sides of the split will have >= half block free, it didn't seem necessary, particularly since this seems like an edge case? -Eric > -Lukas > >> + >> hash2 = map[split].hash; >> continued = hash2 == map[split - 1].hash; >> dxtrace(printk(KERN_INFO "Split block %lu at %x, %i/%i\n", >> >> >