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.
> Requested-by: Kees Cook <keescook@xxxxxxxxxxxx>
> Signed-off-by: Nicolas Pitre <nico@xxxxxxxxxx>
> ---
> 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.
--
To unsubscribe from this list: send the line "unsubscribe linux-console" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
