[PATCH 70/73] pre-process: Support long token and string expansions dynamically

[Bart Van Assche <bvanassche@acm.org>]

Dynamically resize token and string buffers in show_token_sequence(),
tokenize.c, and get_string_constant() in char.c, check allocation and size
bounds, increase MAX_STRING in token.h to 65535, and round oversized slab
allocations up to chunk multiples in allocate.c.

Prevent "too long token expansion" errors, 64 KB string literal truncation,
die("alloc too big") aborts, and fixed-buffer overflows when formatting,
stringifying, or concatenating deeply nested macro expansions such as those
found in modern Linux kernel headers.

Add a regression test in validation/long-string-expansion.c.

Fixes: fbc8230fa8c4 ("Larger buffer size for token concatenation")
Signed-off-by: Bart Van Assche <bvanassche@acm.org>
---
 allocate.c                         | 27 ++++++++---
 allocate.h                         |  1 +
 char.c                             | 46 +++++++++++-------
 pre-process.c                      | 58 ++++++++++++++++------
 token.h                            |  2 +-
 tokenize.c                         | 78 +++++++++++++++++++++---------
 validation/long-string-expansion.c | 30 ++++++++++++
 7 files changed, 179 insertions(+), 63 deletions(-)
 create mode 100644 validation/long-string-expansion.c

diff --git a/allocate.c b/allocate.c
index 2aca1815e5f2..75cd8f3befef 100644
--- a/allocate.c
+++ b/allocate.c
@@ -30,6 +30,7 @@
  * efficient: allocate larger "blobs", and give out individual
  * small bits and pieces of it with no maintenance overhead.
  */
+#include <limits.h>
 #include <stdlib.h>
 #include <stddef.h>
 #include <stdio.h>
@@ -60,7 +61,7 @@ void drop_all_allocations(struct allocator_struct *desc)
 	desc->freelist = NULL;
 	while (blob) {
 		struct allocation_blob *next = blob->next;
-		blob_free(blob, desc->chunking);
+		blob_free(blob, blob->size);
 		blob = next;
 	}
 }
@@ -97,22 +98,32 @@ void *allocate(struct allocator_struct *desc, unsigned int size)
 	desc->useful_bytes += size;
 	size = (size + alignment - 1) & ~(alignment-1);
 	if (!blob || blob->left < size) {
-		unsigned int offset, chunking = desc->chunking;
+		unsigned long offset, chunking = desc->chunking;
 		struct allocation_blob *newblob;
 
 		offset = offsetof(struct allocation_blob, data);
 		offset = (offset + alignment - 1) & ~(alignment-1);
-		if (size > chunking - offset)
-			die("alloc too big");
+		if (size > chunking - offset) {
+			unsigned long need = (unsigned long)size + offset;
+			chunking = (need + chunking - 1) & ~(chunking - 1);
+			if (chunking < need || chunking - offset > UINT_MAX)
+				die("alloc too big");
+		}
 		newblob = blob_alloc(chunking);
 		if (!newblob)
 			die("out of memory");
 		desc->total_bytes += chunking;
-		newblob->next = blob;
+		newblob->size = chunking;
+		newblob->left = chunking - offset;
+		newblob->offset = offset - offsetof(struct allocation_blob, data);
+		if (blob && blob->left > newblob->left - size) {
+			newblob->next = blob->next;
+			blob->next = newblob;
+		} else {
+			newblob->next = blob;
+			desc->blobs = newblob;
+		}
 		blob = newblob;
-		desc->blobs = newblob;
-		blob->left = chunking - offset;
-		blob->offset = offset - offsetof(struct allocation_blob, data);
 	}
 	retval = blob->data + blob->offset;
 	blob->offset += size;
diff --git a/allocate.h b/allocate.h
index a6d305371c28..be99d1053608 100644
--- a/allocate.h
+++ b/allocate.h
@@ -5,6 +5,7 @@
 
 struct allocation_blob {
 	struct allocation_blob *next;
+	unsigned long size;
 	unsigned int left, offset;
 	unsigned char data[];
 };
diff --git a/char.c b/char.c
index a0776b560e29..5614a887f095 100644
--- a/char.c
+++ b/char.c
@@ -1,3 +1,6 @@
+#include <limits.h>
+#include <stdint.h>
+#include <stdlib.h>
 #include <string.h>
 #include "target.h"
 #include "lib.h"
@@ -171,6 +174,22 @@ void get_char_constant(struct token *token, unsigned long long *val)
 	*val = v;
 }
 
+static void append_string_byte(char **buf, size_t *cap, size_t *len, char ch)
+{
+	if (*len >= INT_MAX - sizeof(struct string))
+		die("string too large");
+	if (*len + 1 > *cap) {
+		size_t new_cap = *cap ? *cap * 2 : 4096;
+		if (new_cap < *len + 1)
+			new_cap = *len + 1;
+		*buf = realloc(*buf, new_cap);
+		if (!*buf)
+			die("out of memory");
+		*cap = new_cap;
+	}
+	(*buf)[(*len)++] = ch;
+}
+
 struct token *get_string_constant(struct token *token, struct expression *expr)
 {
 	struct string *string = token->string;
@@ -178,8 +197,9 @@ struct token *get_string_constant(struct token *token, struct expression *expr)
 	int stringtype = token_type(token);
 	int is_wide = stringtype == TOKEN_WIDE_STRING;
 	int is_utf8 = stringtype == TOKEN_UTF8_STRING;
-	static char buffer[MAX_STRING];
-	int len = 0;
+	static char *buffer;
+	static size_t buf_size;
+	size_t len = 0;
 	int bits;
 	int esc_count = 0;
 
@@ -219,29 +239,21 @@ struct token *get_string_constant(struct token *token, struct expression *expr)
 			if (is_ucn && !is_wide) {
 				char utf8[4];
 				int i, n = encode_utf8(v, utf8);
-				for (i = 0; i < n; i++) {
-					if (len < MAX_STRING)
-						buffer[len] = utf8[i];
-					len++;
-				}
+				for (i = 0; i < n; i++)
+					append_string_byte(&buffer, &buf_size, &len, utf8[i]);
 			} else {
-				if (len < MAX_STRING)
-					buffer[len] = v;
-				len++;
+				append_string_byte(&buffer, &buf_size, &len, v);
 			}
 		}
 		token = token->next;
 	}
-	if (len > MAX_STRING) {
-		warning(token->pos, "trying to concatenate %d-character string (%d bytes max)", len, MAX_STRING);
-		len = MAX_STRING;
-	}
 
 	if (esc_count || len >= string->length) {
 		if (string->immutable || len >= string->length)	/* can't cannibalize */
-			string = __alloc_string(len+1);
-		string->length = len+1;
-		memcpy(string->data, buffer, len);
+			string = __alloc_string(len + 1);
+		string->length = len + 1;
+		if (len)
+			memcpy(string->data, buffer, len);
 		string->data[len] = '\0';
 	}
 	expr->string = string;
diff --git a/pre-process.c b/pre-process.c
index 8eb70ca7a1a4..1ea6c71b9a7e 100644
--- a/pre-process.c
+++ b/pre-process.c
@@ -34,6 +34,7 @@
 #include <unistd.h>
 #include <fcntl.h>
 #include <limits.h>
+#include <stdint.h>
 #include <time.h>
 #include <errno.h>
 #include <sys/stat.h>
@@ -420,38 +421,65 @@ static struct token *dup_list(struct token *list)
 
 static const char *show_token_sequence(struct token *token, int quote)
 {
-	static char buffer[MAX_STRING];
-	char *ptr = buffer;
-	int whitespace = 0;
+	static char *buffer;
+	static size_t buf_size;
+	size_t offset = 0;
+	size_t whitespace = 0;
 
 	if (!token && !quote)
 		return "<none>";
 	while (!eof_token(token)) {
 		const char *val = quote ? quote_token(token) : show_token(token);
-		int len = strlen(val);
-
-		if (ptr + whitespace + len >= buffer + sizeof(buffer)) {
-			sparse_error(token->pos, "too long token expansion");
-			break;
+		size_t len = strlen(val);
+		size_t needed;
+
+		if (len > SIZE_MAX - offset - whitespace - 1)
+			die("out of memory");
+		needed = offset + whitespace + len + 1;
+
+		if (needed > buf_size) {
+			size_t new_size = buf_size ? buf_size : 65536;
+			while (new_size < needed) {
+				if (new_size > SIZE_MAX / 2) {
+					new_size = needed;
+					break;
+				}
+				new_size *= 2;
+			}
+			buffer = realloc(buffer, new_size);
+			if (!buffer)
+				die("out of memory");
+			buf_size = new_size;
 		}
 
 		if (whitespace)
-			*ptr++ = ' ';
-		memcpy(ptr, val, len);
-		ptr += len;
+			buffer[offset++] = ' ';
+		memcpy(buffer + offset, val, len);
+		offset += len;
 		token = token->next;
 		whitespace = token->pos.whitespace;
 	}
-	*ptr = 0;
+	if (!buffer) {
+		buf_size = 64;
+		buffer = malloc(buf_size);
+		if (!buffer)
+			die("out of memory");
+	}
+	buffer[offset] = 0;
 	return buffer;
 }
 
 static struct token *stringify(struct token *arg)
 {
 	const char *s = show_token_sequence(arg, 1);
-	int size = strlen(s)+1;
-	struct token *token = __alloc_token(0);
-	struct string *string = __alloc_string(size);
+	size_t size = strlen(s) + 1;
+	struct token *token;
+	struct string *string;
+
+	if (size > INT_MAX - sizeof(struct string))
+		die("string too large");
+	token = __alloc_token(0);
+	string = __alloc_string(size);
 
 	memcpy(string->data, s, size);
 	string->length = size;
diff --git a/token.h b/token.h
index 998d83a123c9..e8276757ca5f 100644
--- a/token.h
+++ b/token.h
@@ -206,7 +206,7 @@ struct token {
 	};
 };
 
-#define MAX_STRING 8191
+#define MAX_STRING 65535
 
 static inline struct token *containing_token(struct token **p)
 {
diff --git a/tokenize.c b/tokenize.c
index 775c54667af7..95dad56a8096 100644
--- a/tokenize.c
+++ b/tokenize.c
@@ -30,6 +30,7 @@
 #include <string.h>
 #include <ctype.h>
 #include <unistd.h>
+#include <limits.h>
 #include <stdint.h>
 
 #include "lib.h"
@@ -110,6 +111,25 @@ const char *show_ident(const struct ident *ident)
 	return buffer;
 }
 
+static char *grow_buffer(char **buf, size_t *cap, size_t needed)
+{
+	if (needed > *cap) {
+		size_t new_cap = *cap ? *cap : 4096;
+		while (new_cap < needed) {
+			if (new_cap > SIZE_MAX / 2) {
+				new_cap = needed;
+				break;
+			}
+			new_cap *= 2;
+		}
+		*buf = realloc(*buf, new_cap);
+		if (!*buf)
+			die("out of memory");
+		*cap = new_cap;
+	}
+	return *buf;
+}
+
 static char *charstr(char *ptr, unsigned char c, unsigned char escape, unsigned char next)
 {
 	if (isprint(c)) {
@@ -135,13 +155,18 @@ static char *charstr(char *ptr, unsigned char c, unsigned char escape, unsigned
 
 const char *show_string(const struct string *string)
 {
-	static char buffer[4 * MAX_STRING + 3];
+	static char *buffer;
+	static size_t buf_size;
+	size_t len;
 	char *ptr;
 	int i;
 
 	if (!string || !string->length)
 		return "<bad_string>";
-	ptr = buffer;
+	len = string->length;
+	if (len > (SIZE_MAX - 3) / 4)
+		die("out of memory");
+	ptr = grow_buffer(&buffer, &buf_size, 4 * len + 3);
 	*ptr++ = '"';
 	for (i = 0; i < string->length-1; i++) {
 		const char *p = string->data + i;
@@ -155,10 +180,15 @@ const char *show_string(const struct string *string)
 static const char *show_char(const char *s, size_t len, const char *prefix,
 			     char delim)
 {
-	static char buffer[MAX_STRING + 8];
-	char *p = buffer;
-	if (prefix) {
-		size_t plen = strlen(prefix);
+	static char *buffer;
+	static size_t buf_size;
+	size_t plen = prefix ? strlen(prefix) : 0;
+	char *p;
+
+	if (len > SIZE_MAX - plen - 3)
+		die("out of memory");
+	p = grow_buffer(&buffer, &buf_size, plen + len + 3);
+	if (plen) {
 		memcpy(p, prefix, plen);
 		p += plen;
 	}
@@ -173,11 +203,16 @@ static const char *show_char(const char *s, size_t len, const char *prefix,
 static const char *quote_char(const char *s, size_t len, const char *prefix,
 			      char delim)
 {
-	static char buffer[2 * MAX_STRING + 8];
+	static char *buffer;
+	static size_t buf_size;
+	size_t plen = prefix ? strlen(prefix) : 0;
 	size_t i;
-	char *p = buffer;
-	if (prefix) {
-		size_t plen = strlen(prefix);
+	char *p;
+
+	if (len > (SIZE_MAX - plen - 6) / 2)
+		die("out of memory");
+	p = grow_buffer(&buffer, &buf_size, plen + 2 * len + 6);
+	if (plen) {
 		memcpy(p, prefix, plen);
 		p += plen;
 	}
@@ -661,18 +696,20 @@ static int get_one_number(int c, int next, stream_t *stream)
 
 static int eat_string(int next, stream_t *stream, enum token_type type)
 {
-	static char buffer[MAX_STRING];
+	static char *buffer;
+	static size_t buf_size;
 	struct string *string;
 	struct token *token = stream->token;
-	int len = 0;
+	size_t len = 0;
 	int escape;
 	int want_hex = 0;
 	char delim = type < TOKEN_STRING ? '\'' : '"';
 
 	for (escape = 0; escape || next != delim; next = nextchar(stream)) {
-		if (len < MAX_STRING)
-			buffer[len] = next;
-		len++;
+		if (len >= INT_MAX - sizeof(struct string))
+			die("string too large");
+		grow_buffer(&buffer, &buf_size, len + 4 < 64 ? 64 : len + 4);
+		buffer[len++] = next;
 		if (next == '\n') {
 			warning(stream_pos(stream),
 				"missing terminating %c character", delim);
@@ -698,20 +735,17 @@ static int eat_string(int next, stream_t *stream, enum token_type type)
 	if (want_hex)
 		warning(stream_pos(stream),
 			"\\x used with no following hex digits");
-	if (len > MAX_STRING) {
-		warning(stream_pos(stream), "string too long (%d bytes, %d bytes max)", len, MAX_STRING);
-		len = MAX_STRING;
-	}
 	if (delim == '\'' && len && len <= 4) {
 		token_type(token) = type + len;
 		memset(buffer + len, '\0', 4 - len);
 		memcpy(token->embedded, buffer, 4);
 	} else {
 		token_type(token) = type;
-		string = __alloc_string(len+1);
-		memcpy(string->data, buffer, len);
+		string = __alloc_string(len + 1);
+		if (len)
+			memcpy(string->data, buffer, len);
 		string->data[len] = '\0';
-		string->length = len+1;
+		string->length = len + 1;
 		token->string = string;
 	}
 
diff --git a/validation/long-string-expansion.c b/validation/long-string-expansion.c
new file mode 100644
index 000000000000..5523ae966c74
--- /dev/null
+++ b/validation/long-string-expansion.c
@@ -0,0 +1,30 @@
+#define S16 "0123456789abcdef"
+#define S64 S16 S16 S16 S16
+#define S256 S64 S64 S64 S64
+#define S1024 S256 S256 S256 S256
+#define S4096 S1024 S1024 S1024 S1024
+#define S16384 S4096 S4096 S4096 S4096
+#define S65536 S16384 S16384 S16384 S16384
+
+#define STR_INNER(x) #x
+#define STR(x) STR_INNER(x)
+
+#define T4 a+a+a+a
+#define T16 T4+T4+T4+T4
+#define T64 T16+T16+T16+T16
+#define T256 T64+T64+T64+T64
+#define T1024 T256+T256+T256+T256
+#define T4096 T1024+T1024+T1024+T1024
+#define T16384 T4096+T4096+T4096+T4096
+#define T65536 T16384+T16384+T16384+T16384
+
+/* Concatenated string literal > 65535 bytes */
+_Static_assert(sizeof(S65536 S16) == 65536 + 16 + 1, "concat > 64KB");
+
+/* Stringified macro expansion with escaped quotes > 65535 bytes */
+_Static_assert(sizeof(STR("q" T65536)) > 130000, "stringify > 64KB");
+
+/*
+ * check-name: long-string-expansion
+ * check-command: sparse $file
+ */