Integer and memory overflow fixes for display code.

* dispextern.h (struct glyph_pool.nglyphs): Now ptrdiff_t, not int.
* dispnew.c (adjust_glyph_matrix, realloc_glyph_pool, scrolling_window):
Check for overflow in size calculations.
(line_draw_cost, realloc_glyph_pool, add_row_entry):
Don't assume glyph table len fits in int.
(struct row_entry.bucket, row_entry_pool_size, row_entry_idx)
(row_table_size): Now ptrdiff_t, not int.
(scrolling_window): Avoid overflow in size calculations.
Don't update size until allocation succeeds.
* fns.c (concat): Check for overflow in size calculations.
(next_almost_prime): Verify NEXT_ALMOST_PRIME_LIMIT.
* lisp.h (RANGED_INTEGERP, TYPE_RANGED_INTEGERP): New macros.
(NEXT_ALMOST_PRIME_LIMIT): New constant.

5 files changed, 103 insertions, 41 deletions

diff --git a/src/ChangeLog b/src/ChangeLog
index 78b3b97b2d7..d7d32e90089 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,5 +1,20 @@
 2011-07-28  Paul Eggert  <eggert@cs.ucla.edu>
 
+        Integer and memory overflow fixes for display code.
+        * dispextern.h (struct glyph_pool.nglyphs): Now ptrdiff_t, not int.
+        * dispnew.c (adjust_glyph_matrix, realloc_glyph_pool, scrolling_window):
+        Check for overflow in size calculations.
+        (line_draw_cost, realloc_glyph_pool, add_row_entry):
+        Don't assume glyph table len fits in int.
+        (struct row_entry.bucket, row_entry_pool_size, row_entry_idx)
+        (row_table_size): Now ptrdiff_t, not int.
+        (scrolling_window): Avoid overflow in size calculations.
+        Don't update size until allocation succeeds.
+        * fns.c (concat): Check for overflow in size calculations.
+        (next_almost_prime): Verify NEXT_ALMOST_PRIME_LIMIT.
+        * lisp.h (RANGED_INTEGERP, TYPE_RANGED_INTEGERP): New macros.
+        (NEXT_ALMOST_PRIME_LIMIT): New constant.
+
         * composite.c: Integer overflow fixes.
         (get_composition_id): Check for overflow in glyph length calculations.
 
diff --git a/src/dispextern.h b/src/dispextern.h
index 1d7bf5d53ec..70f426f95a6 100644
--- a/src/dispextern.h
+++ b/src/dispextern.h
@@ -575,7 +575,7 @@ struct glyph_pool
   struct glyph *glyphs;
 
   /* Allocated size of `glyphs'.  */
-  int nglyphs;
+  ptrdiff_t nglyphs;
 
   /* Number of rows and columns in a matrix.  */
   int nrows, ncolumns;
diff --git a/src/dispnew.c b/src/dispnew.c
index b2f416701c3..4cc101d98bf 100644
--- a/src/dispnew.c
+++ b/src/dispnew.c
@@ -499,7 +499,10 @@ adjust_glyph_matrix (struct window *w, struct glyph_matrix *matrix, int x, int y
   /* Enlarge MATRIX->rows if necessary.  New rows are cleared.  */
   if (matrix->rows_allocated < dim.height)
     {
-      ptrdiff_t size = dim.height * sizeof (struct glyph_row);
+      ptrdiff_t size;
+      if (min (PTRDIFF_MAX, SIZE_MAX) / sizeof (struct glyph_row) < dim.height)
+        memory_full (SIZE_MAX);
+      size = dim.height * sizeof (struct glyph_row);
       new_rows = dim.height - matrix->rows_allocated;
       matrix->rows = (struct glyph_row *) xrealloc (matrix->rows, size);
       memset (matrix->rows + matrix->rows_allocated, 0,
@@ -573,6 +576,9 @@ adjust_glyph_matrix (struct window *w, struct glyph_matrix *matrix, int x, int y
           struct glyph_row *row = matrix->rows;
           struct glyph_row *end = row + matrix->rows_allocated;
 
+          if (min (PTRDIFF_MAX, SIZE_MAX) / sizeof (struct glyph) < dim.width)
+            memory_full (SIZE_MAX);
+
           while (row < end)
             {
               row->glyphs[LEFT_MARGIN_AREA]
@@ -1217,7 +1223,7 @@ line_draw_cost (struct glyph_matrix *matrix, int vpos)
   struct glyph *end = beg + row->used[TEXT_AREA];
   int len;
   Lisp_Object *glyph_table_base = GLYPH_TABLE_BASE;
-  int glyph_table_len = GLYPH_TABLE_LENGTH;
+  ptrdiff_t glyph_table_len = GLYPH_TABLE_LENGTH;
 
   /* Ignore trailing and leading spaces if we can.  */
   if (!FRAME_MUST_WRITE_SPACES (SELECTED_FRAME ())) /* XXX Is SELECTED_FRAME OK here? */
@@ -1391,31 +1397,26 @@ free_glyph_pool (struct glyph_pool *pool)
 static int
 realloc_glyph_pool (struct glyph_pool *pool, struct dim matrix_dim)
 {
-  int needed;
+  ptrdiff_t needed;
   int changed_p;
 
   changed_p = (pool->glyphs == 0
                || matrix_dim.height != pool->nrows
                || matrix_dim.width != pool->ncolumns);
 
+  if (min (PTRDIFF_MAX, SIZE_MAX) / sizeof (struct glyph) / matrix_dim.width
+      < matrix_dim.height)
+    memory_full (SIZE_MAX);
+
   /* Enlarge the glyph pool.  */
-  needed = matrix_dim.width * matrix_dim.height;
+  needed = matrix_dim.width;
+  needed *= matrix_dim.height;
   if (needed > pool->nglyphs)
     {
       ptrdiff_t size = needed * sizeof (struct glyph);
-
-      if (pool->glyphs)
-        {
-          pool->glyphs = (struct glyph *) xrealloc (pool->glyphs, size);
-          memset (pool->glyphs + pool->nglyphs, 0,
-                  size - pool->nglyphs * sizeof (struct glyph));
-        }
-      else
-        {
-          pool->glyphs = (struct glyph *) xmalloc (size);
-          memset (pool->glyphs, 0, size);
-        }
-
+      pool->glyphs = (struct glyph *) xrealloc (pool->glyphs, size);
+      memset (pool->glyphs + pool->nglyphs, 0,
+              size - pool->nglyphs * sizeof (struct glyph));
       pool->nglyphs = needed;
     }
 
@@ -4166,7 +4167,7 @@ struct row_entry
   int new_line_number;
 
   /* Bucket index of this row_entry in the hash table row_table.  */
-  int bucket;
+  ptrdiff_t bucket;
 
   /* The row described by this entry.  */
   struct glyph_row *row;
@@ -4180,18 +4181,18 @@ struct row_entry
    that we need a larger one.  */
 
 static struct row_entry *row_entry_pool;
-static int row_entry_pool_size;
+static ptrdiff_t row_entry_pool_size;
 
 /* Index of next free entry in row_entry_pool.  */
 
-static int row_entry_idx;
+static ptrdiff_t row_entry_idx;
 
 /* The hash table used during scrolling, and the table's size.  This
    table is used to quickly identify equal rows in the desired and
    current matrix.  */
 
 static struct row_entry **row_table;
-static int row_table_size;
+static ptrdiff_t row_table_size;
 
 /* Vectors of pointers to row_entry structures belonging to the
    current and desired matrix, and the size of the vectors.  */
@@ -4214,7 +4215,7 @@ static inline struct row_entry *
 add_row_entry (struct glyph_row *row)
 {
   struct row_entry *entry;
-  int i = row->hash % row_table_size;
+  ptrdiff_t i = row->hash % row_table_size;
 
   entry = row_table[i];
   while (entry && !row_equal_p (entry->row, row, 1))
@@ -4267,9 +4268,10 @@ scrolling_window (struct window *w, int header_line_p)
   struct glyph_matrix *desired_matrix = w->desired_matrix;
   struct glyph_matrix *current_matrix = w->current_matrix;
   int yb = window_text_bottom_y (w);
-  int i, j, first_old, first_new, last_old, last_new;
-  int nruns, n, run_idx;
-  ptrdiff_t nbytes;
+  ptrdiff_t i;
+  int j, first_old, first_new, last_old, last_new;
+  int nruns, run_idx;
+  ptrdiff_t n, nbytes;
   struct row_entry *entry;
   struct redisplay_interface *rif = FRAME_RIF (XFRAME (WINDOW_FRAME (w)));
 
@@ -4354,45 +4356,77 @@ scrolling_window (struct window *w, int header_line_p)
   if (last_new == first_new)
     return 0;
 
+  /* Check for integer overflow in xrealloc size calculation.
+
+     If next_almost_prime checks (N) for divisibility by 2..10, then
+     it can return at most N + 10, e.g., next_almost_prime (1) == 11.
+     So, set next_almost_prime_increment_max to 10.
+
+     It's just a coincidence that next_almost_prime_increment_max ==
+     NEXT_ALMOST_PRIME_LIMIT - 1.  If NEXT_ALMOST_PRIME_LIMIT were
+     13, then next_almost_prime_increment_max would be 14, e.g.,
+     because next_almost_prime (113) would be 127.  */
+  {
+    verify (NEXT_ALMOST_PRIME_LIMIT == 11);
+    enum { next_almost_prime_increment_max = 10 };
+    ptrdiff_t alloc_max = min (PTRDIFF_MAX, SIZE_MAX);
+    ptrdiff_t row_table_max =
+      ((alloc_max - next_almost_prime_increment_max)
+       / (3 * sizeof *row_table));
+    ptrdiff_t row_entry_pool_max = alloc_max / sizeof *row_entry_pool;
+    int n_max = min (INT_MAX, min (row_table_max, row_entry_pool_max));
+    ptrdiff_t old_lines_max = alloc_max / sizeof *old_lines;
+    int current_nrows_max = min (n_max - desired_matrix->nrows, old_lines_max);
+    int desired_nrows_max =
+      min (INT_MAX,
+           alloc_max / max (sizeof *new_lines,
+                            max (sizeof *runs, sizeof *run_pool)));
+    if (current_nrows_max < current_matrix->nrows
+        || desired_nrows_max < desired_matrix->nrows)
+      memory_full (SIZE_MAX);
+  }
+
   /* Reallocate vectors, tables etc. if necessary.  */
 
   if (current_matrix->nrows > old_lines_size)
     {
-      old_lines_size = current_matrix->nrows;
-      nbytes = old_lines_size * sizeof *old_lines;
+      nbytes = current_matrix->nrows * sizeof *old_lines;
       old_lines = (struct row_entry **) xrealloc (old_lines, nbytes);
+      old_lines_size = current_matrix->nrows;
     }
 
   if (desired_matrix->nrows > new_lines_size)
     {
-      new_lines_size = desired_matrix->nrows;
-      nbytes = new_lines_size * sizeof *new_lines;
+      nbytes = desired_matrix->nrows * sizeof *new_lines;
       new_lines = (struct row_entry **) xrealloc (new_lines, nbytes);
+      new_lines_size = desired_matrix->nrows;
     }
 
-  n = desired_matrix->nrows + current_matrix->nrows;
-  if (3 * n > row_table_size)
+  n = desired_matrix->nrows;
+  n += current_matrix->nrows;
+  if (row_table_size / 3 < n)
     {
-      row_table_size = next_almost_prime (3 * n);
-      nbytes = row_table_size * sizeof *row_table;
+      ptrdiff_t size = next_almost_prime (3 * n);
+      nbytes = size * sizeof *row_table;
       row_table = (struct row_entry **) xrealloc (row_table, nbytes);
+      row_table_size = size;
       memset (row_table, 0, nbytes);
     }
 
   if (n > row_entry_pool_size)
     {
-      row_entry_pool_size = n;
-      nbytes = row_entry_pool_size * sizeof *row_entry_pool;
+      nbytes = n * sizeof *row_entry_pool;
       row_entry_pool = (struct row_entry *) xrealloc (row_entry_pool, nbytes);
+      row_entry_pool_size = n;
     }
 
   if (desired_matrix->nrows > runs_size)
     {
-      runs_size = desired_matrix->nrows;
-      nbytes = runs_size * sizeof *runs;
+      nbytes = desired_matrix->nrows * sizeof *runs;
       runs = (struct run **) xrealloc (runs, nbytes);
-      nbytes = runs_size * sizeof *run_pool;
+      nbytes = desired_matrix->nrows * sizeof *run_pool;
       run_pool = (struct run *) xrealloc (run_pool, nbytes);
+      runs_size = desired_matrix->nrows;
     }
 
   nruns = run_idx = 0;
diff --git a/src/fns.c b/src/fns.c
index fdaffe947ac..e5538d6acbc 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -602,7 +602,12 @@ concat (ptrdiff_t nargs, Lisp_Object *args,
 
   prev = Qnil;
   if (STRINGP (val))
-    SAFE_ALLOCA (textprops, struct textprop_rec *, sizeof (struct textprop_rec) * nargs);
+    {
+      if (min (PTRDIFF_MAX, SIZE_MAX) / sizeof *textprops < nargs)
+        memory_full (SIZE_MAX);
+      SAFE_ALLOCA (textprops, struct textprop_rec *,
+                   sizeof *textprops * nargs);
+    }
 
   for (argnum = 0; argnum < nargs; argnum++)
     {
@@ -3395,11 +3400,13 @@ check_hash_table (Lisp_Object obj)
 
 
 /* Value is the next integer I >= N, N >= 0 which is "almost" a prime
-   number.  */
+   number.  A number is "almost" a prime number if it is not divisible
+   by any integer in the range 2 .. (NEXT_ALMOST_PRIME_LIMIT - 1).  */
 
 EMACS_INT
 next_almost_prime (EMACS_INT n)
 {
+  verify (NEXT_ALMOST_PRIME_LIMIT == 11);
   for (n |= 1; ; n += 2)
     if (n % 3 != 0 && n % 5 != 0 && n % 7 != 0)
       return n;
diff --git a/src/lisp.h b/src/lisp.h
index 2d326043614..267bfe1b21f 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -1704,6 +1704,11 @@ typedef struct {
 #define NUMBERP(x) (INTEGERP (x) || FLOATP (x))
 #define NATNUMP(x) (INTEGERP (x) && XINT (x) >= 0)
 
+#define RANGED_INTEGERP(lo, x, hi) \
+  (INTEGERP (x) && (lo) <= XINT (x) && XINT (x) <= (hi))
+#define TYPE_RANGED_INTEGERP(type, x) \
+  RANGED_INTEGERP (TYPE_MINIMUM (type), x, TYPE_MAXIMUM (type))
+
 #define INTEGERP(x) (LISP_INT_TAG_P (XTYPE ((x))))
 #define SYMBOLP(x) (XTYPE ((x)) == Lisp_Symbol)
 #define MISCP(x) (XTYPE ((x)) == Lisp_Misc)
@@ -2551,6 +2556,7 @@ extern void syms_of_syntax (void);
 
 /* Defined in fns.c */
 extern Lisp_Object QCrehash_size, QCrehash_threshold;
+enum { NEXT_ALMOST_PRIME_LIMIT = 11 };
 extern EMACS_INT next_almost_prime (EMACS_INT);
 extern Lisp_Object larger_vector (Lisp_Object, EMACS_INT, Lisp_Object);
 extern void sweep_weak_hash_tables (void);