From e69f59c6710c8861c2be95699e6e7806b1de2941 Mon Sep 17 00:00:00 2001 From: Mark Wielaard Date: Fri, 22 May 2015 23:33:56 +0200 Subject: [PATCH] libdw: Limit stack usage of temporary dir, file and line lists. Limit stack usage of lines with MAX_STACK_LINES, files with MAX_STACK_LINES and dirs with MAX_STACK_DIRS. Calculate number of dirs needed first, then create dirarray directly, without needing the next field. Free not stack allocated lines and files at the end. Use preallocated stack arrays for all instead of calling alloca to help compiler see actual stack usage. The current stack allocation limits are 4096 lines, 1024 files in 256 dirs per CU. For GCC 4.8 libstdc++.so has on average 512 lines per CU. With these settings read_srclines uses max 228K of stack on x86_64. Signed-off-by: Mark Wielaard --- libdw/ChangeLog | 8 +++ libdw/dwarf_getsrclines.c | 150 +++++++++++++++++++++++++++------------------- 2 files changed, 98 insertions(+), 60 deletions(-) diff --git a/libdw/ChangeLog b/libdw/ChangeLog index b833ab2..2757093 100644 --- a/libdw/ChangeLog +++ b/libdw/ChangeLog @@ -1,3 +1,11 @@ +2015-05-22 Mark Wielaard + + * dwarf_getsrclines.c (read_srclines): Limit stack usage of lines + with MAX_STACK_LINES, files with MAX_STACK_LINES and dirs with + MAX_STACK_DIRS. Calculate number of dirs needed first, then + create dirarray directly, without needing the next field. Free + not stack allocated lines and files at the end. + 2015-05-19 Mark Wielaard * dwarf_getlocation.c (__libdw_intern_expression): Create a stack diff --git a/libdw/dwarf_getsrclines.c b/libdw/dwarf_getsrclines.c index 5c85fd4..d49aedc 100644 --- a/libdw/dwarf_getsrclines.c +++ b/libdw/dwarf_getsrclines.c @@ -88,12 +88,16 @@ read_srclines (Dwarf *dbg, struct linelist *linelist = NULL; size_t nlinelist = 0; + size_t nfilelist = 0; + unsigned int ndirlist = 0; - /* If there are a large number of lines don't blow up the stack. - Keep track of the last malloced linelist record and free them - through the next pointer at the end. */ + /* If there are a large number of lines, files or dirs don't blow up + the stack. Stack allocate some entries, only dynamically malloc + when more than MAX. */ #define MAX_STACK_ALLOC 4096 - struct linelist *malloc_linelist = NULL; +#define MAX_STACK_LINES MAX_STACK_ALLOC +#define MAX_STACK_FILES (MAX_STACK_ALLOC / 4) +#define MAX_STACK_DIRS (MAX_STACK_ALLOC / 16) if (unlikely (linep + 4 > lineendp)) { @@ -174,40 +178,64 @@ read_srclines (Dwarf *dbg, { const char *dir; size_t len; - struct dirlist *next; } comp_dir_elem = { .dir = comp_dir, .len = comp_dir ? strlen (comp_dir) : 0, - .next = NULL }; - struct dirlist *dirlist = &comp_dir_elem; - unsigned int ndirlist = 1; + ndirlist = 1; - // XXX Directly construct array to conserve memory? - while (*linep != 0) + /* First count the entries. */ + const unsigned char *dirp = linep; + while (*dirp != 0) { - struct dirlist *new_dir = - (struct dirlist *) alloca (sizeof (*new_dir)); - - new_dir->dir = (char *) linep; - uint8_t *endp = memchr (linep, '\0', lineendp - linep); + uint8_t *endp = memchr (dirp, '\0', lineendp - dirp); if (endp == NULL) goto invalid_data; - new_dir->len = endp - linep; - new_dir->next = dirlist; - dirlist = new_dir; ++ndirlist; + dirp = endp + 1; + } + + /* Arrange the list in array form. */ + struct dirlist dirstack[MAX_STACK_DIRS]; + struct dirlist *dirarray; + if (ndirlist < MAX_STACK_DIRS) + dirarray = dirstack; + else + { + dirarray = (struct dirlist *) malloc (ndirlist * sizeof (*dirarray)); + if (unlikely (dirarray == NULL)) + { + no_mem: + __libdw_seterrno (DWARF_E_NOMEM); + goto out; + } + } + dirarray[0] = comp_dir_elem; + for (unsigned int n = 1; n < ndirlist; n++) + { + dirarray[n].dir = (char *) linep; + uint8_t *endp = memchr (linep, '\0', lineendp - linep); + assert (endp != NULL); + dirarray[n].len = endp - linep; linep = endp + 1; } /* Skip the final NUL byte. */ ++linep; - /* Rearrange the list in array form. */ - struct dirlist **dirarray - = (struct dirlist **) alloca (ndirlist * sizeof (*dirarray)); - for (unsigned int n = ndirlist; n-- > 0; dirlist = dirlist->next) - dirarray[n] = dirlist; + /* Allocate memory for a new file. For the first MAX_STACK_FILES + entries just return a slot in the preallocated stack array. */ + struct filelist flstack[MAX_STACK_FILES]; +#define NEW_FILE() ({ \ + struct filelist *fl = (nfilelist < MAX_STACK_FILES \ + ? &flstack[nfilelist] \ + : malloc (sizeof (struct filelist))); \ + if (unlikely (fl == NULL)) \ + goto no_mem; \ + ++nfilelist; \ + fl->next = filelist; \ + filelist = fl; \ + fl; }) /* Now read the files. */ struct filelist null_file = @@ -221,14 +249,13 @@ read_srclines (Dwarf *dbg, .next = NULL }; struct filelist *filelist = &null_file; - unsigned int nfilelist = 1; + nfilelist = 1; if (unlikely (linep >= lineendp)) goto invalid_data; while (*linep != 0) { - struct filelist *new_file = - (struct filelist *) alloca (sizeof (*new_file)); + struct filelist *new_file = NEW_FILE (); /* First comes the file name. */ char *fname = (char *) linep; @@ -255,22 +282,22 @@ read_srclines (Dwarf *dbg, else { new_file->info.name = libdw_alloc (dbg, char, 1, - dirarray[diridx]->len + 1 + dirarray[diridx].len + 1 + fnamelen + 1); char *cp = new_file->info.name; - if (dirarray[diridx]->dir != NULL) + if (dirarray[diridx].dir != NULL) { /* This value could be NULL in case the DW_AT_comp_dir was not present. We cannot do much in this case. The easiest thing is to convert the path in an absolute path. */ - cp = stpcpy (cp, dirarray[diridx]->dir); + cp = stpcpy (cp, dirarray[diridx].dir); } *cp++ = '/'; strcpy (cp, fname); assert (strlen (new_file->info.name) - < dirarray[diridx]->len + 1 + fnamelen + 1); + < dirarray[diridx].len + 1 + fnamelen + 1); } /* Next comes the modification time. */ @@ -282,10 +309,6 @@ read_srclines (Dwarf *dbg, if (unlikely (linep >= lineendp)) goto invalid_data; get_uleb128 (new_file->info.length, linep, lineendp); - - new_file->next = filelist; - filelist = new_file; - ++nfilelist; } /* Skip the final NUL byte. */ ++linep; @@ -323,15 +346,16 @@ read_srclines (Dwarf *dbg, /* Process the instructions. */ - /* Adds a new line to the matrix. - We cannot simply define a function because we want to use alloca. */ + /* Adds a new line to the matrix. For the first MAX_STACK_LINES + entries just return a slot in the preallocated stack array. */ + struct linelist llstack[MAX_STACK_LINES]; #define NEW_LINE(end_seq) \ do { \ - struct linelist *ll = (nlinelist < MAX_STACK_ALLOC \ - ? alloca (sizeof (struct linelist)) \ + struct linelist *ll = (nlinelist < MAX_STACK_LINES \ + ? &llstack[nlinelist] \ : malloc (sizeof (struct linelist))); \ - if (nlinelist >= MAX_STACK_ALLOC) \ - malloc_linelist = ll; \ + if (unlikely (ll == NULL)) \ + goto no_mem; \ if (unlikely (add_new_line (ll, end_seq))) \ goto invalid_data; \ } while (0) @@ -484,33 +508,29 @@ read_srclines (Dwarf *dbg, goto invalid_data; get_uleb128 (filelength, linep, lineendp); - struct filelist *new_file = - (struct filelist *) alloca (sizeof (*new_file)); + struct filelist *new_file = NEW_FILE (); if (fname[0] == '/') new_file->info.name = fname; else { new_file->info.name = - libdw_alloc (dbg, char, 1, (dirarray[diridx]->len + 1 + libdw_alloc (dbg, char, 1, (dirarray[diridx].len + 1 + fnamelen + 1)); char *cp = new_file->info.name; - if (dirarray[diridx]->dir != NULL) + if (dirarray[diridx].dir != NULL) /* This value could be NULL in case the DW_AT_comp_dir was not present. We cannot do much in this case. The easiest thing is to convert the path in an absolute path. */ - cp = stpcpy (cp, dirarray[diridx]->dir); + cp = stpcpy (cp, dirarray[diridx].dir); *cp++ = '/'; strcpy (cp, fname); } new_file->info.mtime = mtime; new_file->info.length = filelength; - new_file->next = filelist; - filelist = new_file; - ++nfilelist; } break; @@ -688,18 +708,19 @@ read_srclines (Dwarf *dbg, 1); const char **dirs = (void *) &files->info[nfilelist]; + struct filelist *fileslist = filelist; files->nfiles = nfilelist; - while (nfilelist-- > 0) + for (size_t n = nfilelist; n > 0; n--) { - files->info[nfilelist] = filelist->info; - filelist = filelist->next; + files->info[n - 1] = fileslist->info; + fileslist = fileslist->next; } - assert (filelist == NULL); + assert (fileslist == NULL); /* Put all the directory strings in an array. */ files->ndirs = ndirlist; for (unsigned int i = 0; i < ndirlist; ++i) - dirs[i] = dirarray[i]->dir; + dirs[i] = dirarray[i].dir; dirs[ndirlist] = NULL; /* Pass the file data structure to the caller. */ @@ -719,12 +740,13 @@ read_srclines (Dwarf *dbg, /* The list is in LIFO order and usually they come in clumps with ascending addresses. So fill from the back to probably start with runs already in order before we sort. */ + struct linelist *lineslist = linelist; for (size_t i = nlinelist; i-- > 0; ) { - sortlines[i] = linelist; - linelist = linelist->next; + sortlines[i] = lineslist; + lineslist = lineslist->next; } - assert (linelist == NULL); + assert (lineslist == NULL); /* Sort by ascending address. */ qsort (sortlines, nlinelist, sizeof sortlines[0], &compare_lines); @@ -755,11 +777,19 @@ read_srclines (Dwarf *dbg, out: /* Free malloced line records, if any. */ - for (size_t i = MAX_STACK_ALLOC; i < nlinelist; i++) + for (size_t i = MAX_STACK_LINES; i < nlinelist; i++) + { + struct linelist *ll = linelist->next; + free (linelist); + linelist = ll; + } + if (ndirlist >= MAX_STACK_DIRS) + free (dirarray); + for (size_t i = MAX_STACK_FILES; i < nfilelist; i++) { - struct linelist *ll = malloc_linelist->next; - free (malloc_linelist); - malloc_linelist = ll; + struct filelist *fl = filelist->next; + free (filelist); + filelist = fl; } return res; -- 2.7.4