Received: by 2002:ac0:a5a7:0:0:0:0:0 with SMTP id m36-v6csp26842imm; Tue, 17 Jul 2018 19:55:22 -0700 (PDT) X-Google-Smtp-Source: AAOMgpcGFz0+gLI6DASvN4oNiKohZv4JN7+Q8hkSM445R860EhCspgdsE7MRY5hhSyBtqxhxCfSC X-Received: by 2002:a17:902:5617:: with SMTP id h23-v6mr4055801pli.324.1531882522453; Tue, 17 Jul 2018 19:55:22 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1531882522; cv=none; d=google.com; s=arc-20160816; b=ELnX5O+MOV3xAMp8FASuK3IpY1KvpviVdGY4OqbesC/JlVKY3oEKyzzFW6vSXZduAA /YFl/iFyqG5b++RRXyJ2S4q03k+rWPvqnUN5U03Swv28atGtBXNp0YLZ5+68yttwPf+F dJNjq96vh1v5nOS+Rs50lG0ZHUgdemPHNLlGXV57tqU2BXpiNqAh56oPoXnT0NpKZ7+4 ng145F2PnjcbJCJZxnEMgJFCyN8GLqRJkVxzNDV0scp3+ZxjMUD9e4hZRr13tSIqlNHC 5euXhyC0QvtiulUlU8qySs4oqbrcMeLw2DpV0xI8cQbmB/gs94dgVKX7hI9v6/Co3ohI 4wRw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:mime-version:user-agent:references :message-id:in-reply-to:subject:cc:to:from:date:dkim-signature :arc-authentication-results; bh=JUE43aCGdIvBQ3zJiGYOJqLCeUH9k/YrYqqRjecWfSQ=; b=yIErSEzeBGjGEi9Y7g4LVOTtOzwRhx81CNVInP37AcdYqdMVa8s6p7uY19A8HMaPSe WjwJdESlA49XmrhrIOEG2NNAxpkQ3pcim//ZIaSmwRXBOjRaPPDgaevKNBBpN84wAveS 1Rj/jC2ItmEntm+lMa9WE7XcWvRMgKoGnCeWHPRq9sBffF8YPk0JcVHC7yfynw+k/yVw lTUuhomTo1z6KXSFrQOsiJm0DG2CcWczCF9V7impUAjAxXMVz3PMwToKxbelrcqCzuzz ieCK3qinAgIKdK9SbG33O9A2zOngl5CFq1TgXx3Kk0ISuviu5ziIio1ii9ye3chyTFY1 /b9Q== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=bA6TluEr; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id g12-v6si2278196pfh.346.2018.07.17.19.55.07; Tue, 17 Jul 2018 19:55:22 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=bA6TluEr; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731295AbeGRDaC (ORCPT + 99 others); Tue, 17 Jul 2018 23:30:02 -0400 Received: from mail-qk0-f194.google.com ([209.85.220.194]:43314 "EHLO mail-qk0-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730731AbeGRDaC (ORCPT ); Tue, 17 Jul 2018 23:30:02 -0400 Received: by mail-qk0-f194.google.com with SMTP id z74-v6so1661970qkb.10 for ; Tue, 17 Jul 2018 19:54:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=date:from:to:cc:subject:in-reply-to:message-id:references :user-agent:mime-version; bh=JUE43aCGdIvBQ3zJiGYOJqLCeUH9k/YrYqqRjecWfSQ=; b=bA6TluEr/cBsKQJg7YwhKngt98XnMDB0ed2pPyUGzDJm4Tpzwuoq3WYegklvJmZ3+5 HrTGSHKT9+P00gtbUDB8/eaQVsd64vmTSEF22a0iG1EmG4jheimux9n0Gz9j1VGHniSA nw44IHZ1emDVZ69YrbDATdHvGRoybz1SrTw8o= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:in-reply-to:message-id :references:user-agent:mime-version; bh=JUE43aCGdIvBQ3zJiGYOJqLCeUH9k/YrYqqRjecWfSQ=; b=kuj9CYm6OgyDUC+eF4XHsV3QZ2xI4WJK8FnPqDsgk3uOnELEhTMcHCjNrBFCehlHF6 LKnqoAG4OI3Rdhs0eT0IunB+aGTr1+55v3HmKtgoH6osbioD/zcokW4Kmg5DvBWV63Qp jAkZXCBj+QV0K2k6GU5UbQzqetm0HY8GGMudrD0t710O7C1PY5eHh36Cd6AGWh/d0+hP g8FDXoKtMrrV9jhmWJI6uElfbFDzO9PPpyKDTbAqK+xs71VBaIBfhcJSQXobDNkigtR+ esChreEEtrQAPOZ+HGcUnm2JzoitwZWeZHStZEbtRdMkad8h7xFh0et7d1baaTFE0bQO Ik7A== X-Gm-Message-State: AOUpUlFRKVgPew29o/OUoB+gg/aTZ+JB+BHMdifL8kfzMlaSH/dRfXIG 3tNepUD4mIwcpxGH77pLhNYBWA== X-Received: by 2002:a37:16c3:: with SMTP id 64-v6mr3876513qkw.381.1531882465181; Tue, 17 Jul 2018 19:54:25 -0700 (PDT) Received: from xanadu.home (modemcable228.104-82-70.mc.videotron.ca. [70.82.104.228]) by smtp.gmail.com with ESMTPSA id e21-v6sm1450716qtc.67.2018.07.17.19.54.24 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Tue, 17 Jul 2018 19:54:24 -0700 (PDT) Date: Tue, 17 Jul 2018 22:54:23 -0400 (EDT) From: Nicolas Pitre To: Adam Borowski cc: Greg Kroah-Hartman , Kees Cook , Geert Uytterhoeven , Dave Mielke , Samuel Thibault , linux-kernel@vger.kernel.org, linux-console@vger.kernel.org Subject: Re: [PATCH 1/3] vt: avoid a VLA in the unicode screen scroll function In-Reply-To: <20180718014813.ygcbgqxk4yo3ydbl@angband.pl> Message-ID: References: <20180718010242.5254-1-nicolas.pitre@linaro.org> <20180718010242.5254-2-nicolas.pitre@linaro.org> <20180718014813.ygcbgqxk4yo3ydbl@angband.pl> User-Agent: Alpine 2.21 (LFD 202 2017-01-01) MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="8323328-1964054974-1531882464=:11681" Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org This message is in MIME format. The first part should be readable text, while the remaining parts are likely unreadable without MIME-aware tools. --8323328-1964054974-1531882464=:11681 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8BIT On Wed, 18 Jul 2018, Adam Borowski wrote: > On Tue, Jul 17, 2018 at 09:02:40PM -0400, Nicolas Pitre wrote: > > The nr argument is typically small: most often nr == 1. However this > > could be abused with a very large explicit scroll in a resized screen. > > Make the code scroll lines one at a time in all cases to avoid the VLA. > > Anything smarter is most likely not warranted here. > > Even though nr can be 32767 at most, your new version is O(nr*nr) for no > reason. Instead of O(n) memory or O(n?) time, a variant of the original > that copies values one at a time would be shorter and faster. Well... even though nr _can_ be up to 32766 to be precise, it is most likely to be just 1 in 99.9% of the cases. So in that case, you'll execute the loop only once and the code is currently optimal with O(n). If nr > 1 then the current cost is O(n*nr) where n is the height of the scroll window i.e. relatively small in practice (typically between 25 and 60). There is no point optimizing for 32767 rows as that is rather silly. If we had then the best solution would be a linked list rather than an array. But still, if nr > 2 that means you need a temporary storage because the destination memory has to be preserved before the source memory can be moved there, and that destination memory content cannot be stored in the vacated source memory until the source content is moved. Copying values one at a time cannot work because the destination memory, the source memory, and the area where the previous content from the destination memory will end up don't overlap most of the time. That temporary storage was that VLA. We don't want VLAs. So how do we efficiently allocate and deallocate memory for, say, 25 words? Maybe that doesn't have to be efficient because that doesn't happen very often as we said, at which point we can just do it in a loop with a one-line increment instead, as this patch does. If you still have a more clever way of doing this then please propose it in code form (I'm genuinely curious of what you have in mind). But let's get the baseline working in an obvious "correct" way first. > > Requested-by: Kees Cook > > Signed-off-by: Nicolas Pitre > > --- > > drivers/tty/vt/vt.c | 18 ++++++++++-------- > > 1 file changed, 10 insertions(+), 8 deletions(-) > > > > diff --git a/drivers/tty/vt/vt.c b/drivers/tty/vt/vt.c > > index 2d14bb195d..03e79f7787 100644 > > --- a/drivers/tty/vt/vt.c > > +++ b/drivers/tty/vt/vt.c > > @@ -433,20 +433,22 @@ static void vc_uniscr_scroll(struct vc_data *vc, unsigned int t, unsigned int b, > > > > if (uniscr) { > > unsigned int s, d, rescue, clear; > > - char32_t *save[nr]; > > > > s = clear = t; > > - d = t + nr; > > - rescue = b - nr; > > + d = t + 1; > > + rescue = b - 1; > > if (dir == SM_UP) { > > swap(s, d); > > swap(clear, rescue); > > } > > - memcpy(save, uniscr->lines + rescue, nr * sizeof(*save)); > > - memmove(uniscr->lines + d, uniscr->lines + s, > > - (b - t - nr) * sizeof(*uniscr->lines)); > > - memcpy(uniscr->lines + clear, save, nr * sizeof(*save)); > > - vc_uniscr_clear_lines(vc, clear, nr); > > + while (nr--) { > > + char32_t *tmp; > > + tmp = uniscr->lines[rescue]; > > + memmove(uniscr->lines + d, uniscr->lines + s, > > + (b - t - 1) * sizeof(*uniscr->lines)); > > + uniscr->lines[clear] = tmp; > > + vc_uniscr_clear_lines(vc, clear, 1); > > + } > > } > > } > > What the function does is rotating an array (slice [t..b) here), by nr if > SM_DOWN or by -nr ie (b - t - nr) if SM_UP. A nice problem that almost every > "code interview questions" book includes :) > > Please say if you don't have time for such games, I've just refreshed what's > a good answer. :? > > > Meow. > -- > // If you believe in so-called "intellectual property", please immediately > // cease using counterfeit alphabets. Instead, contact the nearest temple > // of Amon, whose priests will provide you with scribal services for all > // your writing needs, for Reasonable And Non-Discriminatory prices. > --8323328-1964054974-1531882464=:11681--