[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: integer overflow in /bin/ls
From: |
Paul Eggert |
Subject: |
Re: integer overflow in /bin/ls |
Date: |
13 Oct 2003 16:37:41 -0700 |
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.3 |
Jim Meyering <address@hidden> writes:
> As you probably noticed, init_column_info allocates O(N^2)
> space when ls is invoked with `--width=N' and -x or -C.
> Eventually we may want to investigate change the algorithm, or --
> failing that -- limit N.
I don't offhand see how to change the algorithm without giving up its
optimality. However, we can easily limit N to the number of files in
the current directory, and I think that's good enough to foil the
denial of service attack in practical cases.
Here's a proposed patch to do that. With this patch, we don't have to
worry about the -w option; even 'ls -w 9223372036854775807' (on a
64-bit host) will do the right thing without exhausting memory (unless
you're in a directory that contains billions of file names....).
2003-10-13 Paul Eggert <address@hidden>
Fix to avoid a denial-of-service attack if the display width is
enormous. Also, clean up the code a bit by removing duplicate
code.
* src/ls.c (init_column_info): Remove forward decl; no longer needed.
(calculate_columns): New function, that contains code that used
to be common to print_many_per_line and print_horizontal.
(print_many_per_line, print_horizontal): Use it.
(decode_switches): Set max_idx here, not in calculate_columns.
(print_current_files): Don't call init_column_info; calculate_columns
now does that.
(init_column_info): Don't allocate a lot more space than is needed
to represent the current set of files. Allocate all the new
size_t cells in one call to xnmalloc, rather than a row at a time.
--- ls.c.~1.342.~ Mon Oct 13 15:25:08 2003
+++ ls.c Mon Oct 13 16:23:04 2003
@@ -264,7 +264,7 @@ static void extract_dirs_from_files (con
int ignore_dot_and_dot_dot);
static void get_link_name (const char *filename, struct fileinfo *f);
static void indent (size_t from, size_t to);
-static void init_column_info (void);
+static size_t calculate_columns (bool by_columns);
static void print_current_files (void);
static void print_dir (const char *name, const char *realname);
static void print_file_name_and_frills (const struct fileinfo *f);
@@ -1654,6 +1654,8 @@ decode_switches (int argc, char **argv)
}
}
+ max_idx = MAX (1, line_length / MIN_COLUMN_WIDTH);
+
filename_quoting_options = clone_quoting_options (NULL);
if (get_quoting_style (filename_quoting_options) == escape_quoting_style)
set_char_quoting (filename_quoting_options, ' ', 1);
@@ -2799,12 +2801,10 @@ print_current_files (void)
break;
case many_per_line:
- init_column_info ();
print_many_per_line ();
break;
case horizontal:
- init_column_info ();
print_horizontal ();
break;
@@ -3482,75 +3482,29 @@ length_of_file_name_and_frills (const st
return len;
}
-/* FIXME: the first 40+ lines of this function are nearly identical
- to those in the print_horizontal function. Fix that. */
static void
print_many_per_line (void)
{
- struct column_info *line_fmt;
- size_t filesno; /* Index into files. */
size_t row; /* Current row. */
- size_t max_name_length; /* Length of longest file name + frills. */
- size_t name_length; /* Length of each file name + frills. */
- size_t pos; /* Current character column. */
- size_t cols; /* Number of files across. */
- size_t rows; /* Maximum number of files down. */
- size_t max_cols;
-
- /* Normally the maximum number of columns is determined by the
- screen width. But if few files are available this might limit it
- as well. */
- max_cols = max_idx > files_index ? files_index : max_idx;
-
- /* Compute the maximum number of possible columns. */
- for (filesno = 0; filesno < files_index; ++filesno)
- {
- size_t i;
-
- name_length = length_of_file_name_and_frills (files + filesno);
-
- for (i = 0; i < max_cols; ++i)
- {
- if (column_info[i].valid_len)
- {
- size_t idx = filesno / ((files_index + i) / (i + 1));
- size_t real_length = name_length + (idx == i ? 0 : 2);
-
- if (real_length > column_info[i].col_arr[idx])
- {
- column_info[i].line_len += (real_length
- - column_info[i].col_arr[idx]);
- column_info[i].col_arr[idx] = real_length;
- column_info[i].valid_len = column_info[i].line_len <
line_length;
- }
- }
- }
- }
-
- /* Find maximum allowed columns. */
- for (cols = max_cols; cols > 1; --cols)
- {
- if (column_info[cols - 1].valid_len)
- break;
- }
-
- line_fmt = &column_info[cols - 1];
+ size_t cols = calculate_columns (true);
+ struct column_info const *line_fmt = &column_info[cols - 1];
/* Calculate the number of rows that will be in each column except possibly
for a short column on the right. */
- rows = files_index / cols + (files_index % cols != 0);
+ size_t rows = files_index / cols + (files_index % cols != 0);
for (row = 0; row < rows; row++)
{
size_t col = 0;
- filesno = row;
- pos = 0;
+ size_t filesno = row;
+ size_t pos = 0;
+
/* Print the next row. */
while (1)
{
+ size_t name_length = length_of_file_name_and_frills (files + filesno);
+ size_t max_name_length = line_fmt->col_arr[col++];
print_file_name_and_frills (files + filesno);
- name_length = length_of_file_name_and_frills (files + filesno);
- max_name_length = line_fmt->col_arr[col++];
filesno += rows;
if (filesno >= files_index)
@@ -3566,60 +3520,15 @@ print_many_per_line (void)
static void
print_horizontal (void)
{
- struct column_info *line_fmt;
size_t filesno;
- size_t max_name_length;
- size_t name_length;
- size_t cols;
- size_t pos;
- size_t max_cols;
-
- /* Normally the maximum number of columns is determined by the
- screen width. But if few files are available this might limit it
- as well. */
- max_cols = max_idx > files_index ? files_index : max_idx;
-
- /* Compute the maximum file name length. */
- max_name_length = 0;
- for (filesno = 0; filesno < files_index; ++filesno)
- {
- size_t i;
-
- name_length = length_of_file_name_and_frills (files + filesno);
-
- for (i = 0; i < max_cols; ++i)
- {
- if (column_info[i].valid_len)
- {
- size_t idx = filesno % (i + 1);
- size_t real_length = name_length + (idx == i ? 0 : 2);
-
- if (real_length > column_info[i].col_arr[idx])
- {
- column_info[i].line_len += (real_length
- - column_info[i].col_arr[idx]);
- column_info[i].col_arr[idx] = real_length;
- column_info[i].valid_len = column_info[i].line_len <
line_length;
- }
- }
- }
- }
-
- /* Find maximum allowed columns. */
- for (cols = max_cols; cols > 1; --cols)
- {
- if (column_info[cols - 1].valid_len)
- break;
- }
-
- line_fmt = &column_info[cols - 1];
-
- pos = 0;
+ size_t pos = 0;
+ size_t cols = calculate_columns (false);
+ struct column_info const *line_fmt = &column_info[cols - 1];
+ size_t name_length = length_of_file_name_and_frills (files);
+ size_t max_name_length = line_fmt->col_arr[0];
/* Print first entry. */
print_file_name_and_frills (files);
- name_length = length_of_file_name_and_frills (files);
- max_name_length = line_fmt->col_arr[0];
/* Now the rest. */
for (filesno = 1; filesno < files_index; ++filesno)
@@ -3722,38 +3631,126 @@ attach (char *dest, const char *dirname,
*dest = 0;
}
-/* FIXME: this code allocates allocates O(N^2) space when ls is invoked
- with `--width=N' and -x or -C. Either fix that or limit N. */
+/* Allocate enough column info suitable for the current number of
+ files and display columns, and initialize the info to represent the
+ narrowest possible columns. */
+
static void
init_column_info (void)
{
size_t i;
- int allocate = 0;
+ size_t max_cols = MIN (max_idx, files_index);
- max_idx = line_length / MIN_COLUMN_WIDTH;
- if (max_idx == 0)
- max_idx = 1;
+ /* Currently allocated columns in column_info. */
+ static size_t column_info_alloc;
- if (column_info == NULL)
+ if (column_info_alloc < max_cols)
{
- column_info = xnmalloc (max_idx, sizeof *column_info);
- allocate = 1;
+ size_t new_column_info_alloc;
+ size_t *p;
+
+ if (max_cols < max_idx / 2)
+ {
+ /* The number of columns is far less than the display width
+ allows. Grow the allocation, but only so that it's
+ double the current requirements. If the display is
+ extremely wide, this avoids allocating a lot of memory
+ that is never needed. */
+ column_info = xnrealloc (column_info, max_cols,
+ 2 * sizeof *column_info);
+ new_column_info_alloc = 2 * max_cols;
+ }
+ else
+ {
+ column_info = xnrealloc (column_info, max_idx, sizeof *column_info);
+ new_column_info_alloc = max_idx;
+ }
+
+ /* Allocate the new size_t objects by computing the triangle
+ formula n * (n + 1) / 2, except that we don't need to
+ allocate the part of the triangle that we've already
+ allocated. Check for address arithmetic overflow. */
+ {
+ size_t column_info_growth = new_column_info_alloc - column_info_alloc;
+ size_t s = column_info_alloc + 1 + new_column_info_alloc;
+ size_t t = s * column_info_growth;
+ if (s < new_column_info_alloc || t / column_info_growth != s)
+ xalloc_die ();
+ p = xnmalloc (t / 2, sizeof *p);
+ }
+
+ /* Grow the triangle by parceling out the cells just allocated. */
+ for (i = column_info_alloc; i < new_column_info_alloc; i++)
+ {
+ column_info[i].col_arr = p;
+ p += i + 1;
+ }
+
+ column_info_alloc = new_column_info_alloc;
}
- for (i = 0; i < max_idx; ++i)
+ for (i = 0; i < max_cols; ++i)
{
size_t j;
column_info[i].valid_len = true;
column_info[i].line_len = (i + 1) * MIN_COLUMN_WIDTH;
-
- if (allocate)
- column_info[i].col_arr = xnmalloc (i + 1,
- sizeof column_info[i].col_arr[0]);
-
for (j = 0; j <= i; ++j)
column_info[i].col_arr[j] = MIN_COLUMN_WIDTH;
}
+}
+
+/* Calculate the number of columns needed to represent the current set
+ of files in the current display width. */
+
+static size_t
+calculate_columns (bool by_columns)
+{
+ size_t filesno; /* Index into files. */
+ size_t cols; /* Number of files across. */
+
+ /* Normally the maximum number of columns is determined by the
+ screen width. But if few files are available this might limit it
+ as well. */
+ size_t max_cols = MIN (max_idx, files_index);
+
+ init_column_info ();
+
+ /* Compute the maximum number of possible columns. */
+ for (filesno = 0; filesno < files_index; ++filesno)
+ {
+ size_t name_length = length_of_file_name_and_frills (files + filesno);
+ size_t i;
+
+ for (i = 0; i < max_cols; ++i)
+ {
+ if (column_info[i].valid_len)
+ {
+ size_t idx = (by_columns
+ ? filesno / ((files_index + i) / (i + 1))
+ : filesno % (i + 1));
+ size_t real_length = name_length + (idx == i ? 0 : 2);
+
+ if (column_info[i].col_arr[idx] < real_length)
+ {
+ column_info[i].line_len += (real_length
+ - column_info[i].col_arr[idx]);
+ column_info[i].col_arr[idx] = real_length;
+ column_info[i].valid_len = (column_info[i].line_len
+ < line_length);
+ }
+ }
+ }
+ }
+
+ /* Find maximum allowed columns. */
+ for (cols = max_cols; 1 < cols; --cols)
+ {
+ if (column_info[cols - 1].valid_len)
+ break;
+ }
+
+ return cols;
}
void