dwelf: Add string table functions from ebl.

Move the strtab functions from libebl to libdw. Programs often want to
create ELF/DWARF string tables. We don't want (static) linking against
ebl since those are internal functions that might change.

This introduces dwelf_strtab_init, dwelf_strtab_add,
dwelf_strtab_add_len, dwelf_strtab_finalize, dwelf_strent_off,
dwelf_strent_str and dwelf_strtab_free. Documentation for each has
been added to libdwelf.h. The add fucntion got a variant that takes
the length explicitly and finalize was changed to return NULL on
out of memory instead of aborting. All code and tests now uses the
new functions.

Signed-off-by: Mark Wielaard <mjw@redhat.com>

4 files changed, 435 insertions, 2 deletions

diff --git a/libdwelf/ChangeLog b/libdwelf/ChangeLog
index fe8af1b4..4211023c 100644
--- a/libdwelf/ChangeLog
+++ b/libdwelf/ChangeLog
@@ -1,3 +1,17 @@
+2016-07-08  Mark Wielaard  <mjw@redhat.com>
+
+	* Makefile.am (libdwelf_a_SOURCES): Add dwelf_strtab.c.
+	* dwelf_strtab.c: New file.
+	* libdwelf.h (Dwelf_Strtab): New typedef.
+	(Dwelf_Strent): Likewise.
+	(dwelf_strtab_init): New function.
+	(dwelf_strtab_add): Likewise.
+	(dwelf_strtab_add_len): Likewise.
+	(dwelf_strtab_finalize): Likewise.
+	(dwelf_strent_off): Likewise.
+	(dwelf_strent_str): Likewise.
+	(dwelf_strtab_free): Likewise.
+
 2015-10-28  Mark Wielaard  <mjw@redhat.com>
 
 	* Makefile.am (libdwelf_a_SOURCES): Add
diff --git a/libdwelf/Makefile.am b/libdwelf/Makefile.am
index 4de4b2ed..7ca767a9 100644
--- a/libdwelf/Makefile.am
+++ b/libdwelf/Makefile.am
@@ -40,7 +40,8 @@ pkginclude_HEADERS = libdwelf.h
 noinst_HEADERS = libdwelfP.h
 
 libdwelf_a_SOURCES = dwelf_elf_gnu_debuglink.c dwelf_dwarf_gnu_debugaltlink.c \
-		     dwelf_elf_gnu_build_id.c dwelf_scn_gnu_compressed_size.c
+		     dwelf_elf_gnu_build_id.c dwelf_scn_gnu_compressed_size.c \
+		     dwelf_strtab.c
 
 libdwelf = $(libdw)
 
diff --git a/libdwelf/dwelf_strtab.c b/libdwelf/dwelf_strtab.c
new file mode 100644
index 00000000..c1b93d4a
--- /dev/null
+++ b/libdwelf/dwelf_strtab.c
@@ -0,0 +1,365 @@
+/* ELF/DWARF string table handling.
+   Copyright (C) 2000, 2001, 2002, 2005, 2016 Red Hat, Inc.
+   This file is part of elfutils.
+   Written by Ulrich Drepper <drepper@redhat.com>, 2000.
+
+   This file is free software; you can redistribute it and/or modify
+   it under the terms of either
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at
+       your option) any later version
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at
+       your option) any later version
+
+   or both in parallel, as here.
+
+   elfutils is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see <http://www.gnu.org/licenses/>.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <assert.h>
+#include <inttypes.h>
+#include <libelf.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <sys/param.h>
+
+#include "libdwelfP.h"
+#include <system.h>
+
+#ifndef MIN
+# define MIN(a, b) ((a) < (b) ? (a) : (b))
+#endif
+
+
+struct Dwelf_Strent
+{
+  const char *string;
+  size_t len;
+  struct Dwelf_Strent *next;
+  struct Dwelf_Strent *left;
+  struct Dwelf_Strent *right;
+  size_t offset;
+  char reverse[0];
+};
+
+
+struct memoryblock
+{
+  struct memoryblock *next;
+  char memory[0];
+};
+
+
+struct Dwelf_Strtab
+{
+  struct Dwelf_Strent *root;
+  struct memoryblock *memory;
+  char *backp;
+  size_t left;
+  size_t total;
+  bool nullstr;
+
+  struct Dwelf_Strent null;
+};
+
+
+/* Cache for the pagesize.  */
+static size_t ps;
+/* We correct this value a bit so that `malloc' is not allocating more
+   than a page. */
+#define MALLOC_OVERHEAD (2 * sizeof (void *))
+
+
+Dwelf_Strtab *
+dwelf_strtab_init (bool nullstr)
+{
+  if (ps == 0)
+    {
+      ps = sysconf (_SC_PAGESIZE);
+      assert (sizeof (struct memoryblock) < ps - MALLOC_OVERHEAD);
+    }
+
+  Dwelf_Strtab *ret
+    = (Dwelf_Strtab *) calloc (1, sizeof (struct Dwelf_Strtab));
+  if (ret != NULL)
+    {
+      ret->nullstr = nullstr;
+
+      if (nullstr)
+	{
+	  ret->null.len = 1;
+	  ret->null.string = "";
+	}
+    }
+
+  return ret;
+}
+
+
+static int
+morememory (Dwelf_Strtab *st, size_t len)
+{
+  size_t overhead = offsetof (struct memoryblock, memory);
+  len += overhead + MALLOC_OVERHEAD;
+
+  /* Allocate nearest multiple of pagesize >= len.  */
+  len = ((len / ps) + (len % ps != 0)) * ps - MALLOC_OVERHEAD;
+
+  struct memoryblock *newmem = (struct memoryblock *) malloc (len);
+  if (newmem == NULL)
+    return 1;
+
+  newmem->next = st->memory;
+  st->memory = newmem;
+  st->backp = newmem->memory;
+  st->left = len - overhead;
+
+  return 0;
+}
+
+
+void
+dwelf_strtab_free (Dwelf_Strtab *st)
+{
+  struct memoryblock *mb = st->memory;
+
+  while (mb != NULL)
+    {
+      void *old = mb;
+      mb = mb->next;
+      free (old);
+    }
+
+  free (st);
+}
+
+
+static Dwelf_Strent *
+newstring (Dwelf_Strtab *st, const char *str, size_t len)
+{
+  /* Compute the amount of padding needed to make the structure aligned.  */
+  size_t align = ((__alignof__ (struct Dwelf_Strent)
+		   - (((uintptr_t) st->backp)
+		      & (__alignof__ (struct Dwelf_Strent) - 1)))
+		  & (__alignof__ (struct Dwelf_Strent) - 1));
+
+  /* Make sure there is enough room in the memory block.  */
+  if (st->left < align + sizeof (struct Dwelf_Strent) + len)
+    {
+      if (morememory (st, sizeof (struct Dwelf_Strent) + len))
+	return NULL;
+
+      align = 0;
+    }
+
+  /* Create the reserved string.  */
+  Dwelf_Strent *newstr = (Dwelf_Strent *) (st->backp + align);
+  newstr->string = str;
+  newstr->len = len;
+  newstr->next = NULL;
+  newstr->left = NULL;
+  newstr->right = NULL;
+  newstr->offset = 0;
+  for (int i = len - 2; i >= 0; --i)
+    newstr->reverse[i] = str[len - 2 - i];
+  newstr->reverse[len - 1] = '\0';
+  st->backp += align + sizeof (struct Dwelf_Strent) + len;
+  st->left -= align + sizeof (struct Dwelf_Strent) + len;
+
+  return newstr;
+}
+
+
+/* XXX This function should definitely be rewritten to use a balancing
+   tree algorith (AVL, red-black trees).  For now a simple, correct
+   implementation is enough.  */
+static Dwelf_Strent **
+searchstring (Dwelf_Strent **sep, Dwelf_Strent *newstr)
+{
+  /* More strings?  */
+  if (*sep == NULL)
+    {
+      *sep = newstr;
+      return sep;
+    }
+
+  /* Compare the strings.  */
+  int cmpres = memcmp ((*sep)->reverse, newstr->reverse,
+		       MIN ((*sep)->len, newstr->len) - 1);
+  if (cmpres == 0)
+    /* We found a matching string.  */
+    return sep;
+  else if (cmpres > 0)
+    return searchstring (&(*sep)->left, newstr);
+  else
+    return searchstring (&(*sep)->right, newstr);
+}
+
+
+/* Add new string.  The actual string is assumed to be permanent.  */
+static Dwelf_Strent *
+strtab_add (Dwelf_Strtab *st, const char *str, size_t len)
+{
+  /* Make sure all "" strings get offset 0 but only if the table was
+     created with a special null entry in mind.  */
+  if (len == 1 && st->null.string != NULL)
+    return &st->null;
+
+  /* Allocate memory for the new string and its associated information.  */
+  Dwelf_Strent *newstr = newstring (st, str, len);
+  if (newstr == NULL)
+    return NULL;
+
+  /* Search in the array for the place to insert the string.  If there
+     is no string with matching prefix and no string with matching
+     leading substring, create a new entry.  */
+  Dwelf_Strent **sep = searchstring (&st->root, newstr);
+  if (*sep != newstr)
+    {
+      /* This is not the same entry.  This means we have a prefix match.  */
+      if ((*sep)->len > newstr->len)
+	{
+	  /* Check whether we already know this string.  */
+	  for (Dwelf_Strent *subs = (*sep)->next; subs != NULL;
+	       subs = subs->next)
+	    if (subs->len == newstr->len)
+	      {
+		/* We have an exact match with a substring.  Free the memory
+		   we allocated.  */
+		st->left += st->backp - (char *) newstr;
+		st->backp = (char *) newstr;
+
+		return subs;
+	      }
+
+	  /* We have a new substring.  This means we don't need the reverse
+	     string of this entry anymore.  */
+	  st->backp -= newstr->len;
+	  st->left += newstr->len;
+
+	  newstr->next = (*sep)->next;
+	  (*sep)->next = newstr;
+	}
+      else if ((*sep)->len != newstr->len)
+	{
+	  /* When we get here it means that the string we are about to
+	     add has a common prefix with a string we already have but
+	     it is longer.  In this case we have to put it first.  */
+	  st->total += newstr->len - (*sep)->len;
+	  newstr->next = *sep;
+	  newstr->left = (*sep)->left;
+	  newstr->right = (*sep)->right;
+	  *sep = newstr;
+	}
+      else
+	{
+	  /* We have an exact match.  Free the memory we allocated.  */
+	  st->left += st->backp - (char *) newstr;
+	  st->backp = (char *) newstr;
+
+	  newstr = *sep;
+	}
+    }
+  else
+    st->total += newstr->len;
+
+  return newstr;
+}
+
+Dwelf_Strent *
+dwelf_strtab_add (Dwelf_Strtab *st, const char *str)
+{
+  return strtab_add (st, str, strlen (str) + 1);
+}
+
+Dwelf_Strent *
+dwelf_strtab_add_len (Dwelf_Strtab *st, const char *str, size_t len)
+{
+  return strtab_add (st, str, len);
+}
+
+static void
+copystrings (Dwelf_Strent *nodep, char **freep, size_t *offsetp)
+{
+  if (nodep->left != NULL)
+    copystrings (nodep->left, freep, offsetp);
+
+  /* Process the current node.  */
+  nodep->offset = *offsetp;
+  *freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
+  *offsetp += nodep->len;
+
+  for (Dwelf_Strent *subs = nodep->next; subs != NULL; subs = subs->next)
+    {
+      assert (subs->len < nodep->len);
+      subs->offset = nodep->offset + nodep->len - subs->len;
+      assert (subs->offset != 0 || subs->string[0] == '\0');
+    }
+
+  if (nodep->right != NULL)
+    copystrings (nodep->right, freep, offsetp);
+}
+
+
+Elf_Data *
+dwelf_strtab_finalize (Dwelf_Strtab *st, Elf_Data *data)
+{
+  size_t nulllen = st->nullstr ? 1 : 0;
+
+  /* Fill in the information.  */
+  data->d_buf = malloc (st->total + nulllen);
+  if (data->d_buf == NULL)
+    return NULL;
+
+  /* The first byte must always be zero if we created the table with a
+     null string.  */
+  if (st->nullstr)
+    *((char *) data->d_buf) = '\0';
+
+  data->d_type = ELF_T_BYTE;
+  data->d_size = st->total + nulllen;
+  data->d_off = 0;
+  data->d_align = 1;
+  data->d_version = EV_CURRENT;
+
+  /* Now run through the tree and add all the string while also updating
+     the offset members of the elfstrent records.  */
+  char *endp = (char *) data->d_buf + nulllen;
+  size_t copylen = nulllen;
+  if (st->root)
+    copystrings (st->root, &endp, &copylen);
+  assert (copylen == st->total + nulllen);
+
+  return data;
+}
+
+
+size_t
+dwelf_strent_off (Dwelf_Strent *se)
+{
+  return se->offset;
+}
+
+
+const char *
+dwelf_strent_str (Dwelf_Strent *se)
+{
+  return se->string;
+}
diff --git a/libdwelf/libdwelf.h b/libdwelf/libdwelf.h
index 7f7f679a..72089dbf 100644
--- a/libdwelf/libdwelf.h
+++ b/libdwelf/libdwelf.h
@@ -1,5 +1,5 @@
 /* Interfaces for libdwelf. DWARF ELF Low-level Functions.
-   Copyright (C) 2014, 2015 Red Hat, Inc.
+   Copyright (C) 2014, 2015, 2016 Red Hat, Inc.
    This file is part of elfutils.
 
    This file is free software; you can redistribute it and/or modify
@@ -72,6 +72,59 @@ extern ssize_t dwelf_elf_gnu_build_id (Elf *elf, const void **build_idp);
    error occured -1 is returned and elf_errno is set.  */
 extern ssize_t dwelf_scn_gnu_compressed_size (Elf_Scn *scn);
 
+/* ELF/DWARF string table handling.  */
+typedef struct Dwelf_Strtab Dwelf_Strtab;
+typedef struct Dwelf_Strent Dwelf_Strent;
+
+/* Create a new ELF/DWARF string table object in memory.  ELF string
+   tables have a required zero length null string at offset zero.
+   DWARF string tables don't require such a null entry (unless they
+   are shared with an ELF string table).  If NULLSTR is true then a
+   null entry is always created (even if the string table is empty
+   otherwise).  */
+extern Dwelf_Strtab *dwelf_strtab_init (bool nullstr);
+
+/* Add string STR to string table ST.  Returns NULL if no memory could
+   be allocated.  The given STR is owned by the called and must be
+   valid till dwelf_strtab_free is called.  dwelf_strtab_finalize
+   might copy the string into the final table and dwelf_strent_str
+   might return it, or a reference to an identical copy/substring
+   added to the string table.  */
+extern Dwelf_Strent *dwelf_strtab_add (Dwelf_Strtab *st, const char *str)
+  __nonnull_attribute__ (1, 2);
+
+/* This is an optimized version of dwelf_strtab_add if the length of
+   the string is already known.  LEN is the length of STR including
+   zero terminator.  Calling dwelf_strtab_add (st, str) is similar to
+   calling dwelf_strtab_len (st, str, strlen (str) + 1).  */
+extern Dwelf_Strent *dwelf_strtab_add_len (Dwelf_Strtab *st,
+					   const char *str, size_t len)
+  __nonnull_attribute__ (1, 2);
+
+/* Finalize string table ST and store size and memory location
+   information in DATA d_size and d_buf.  DATA d_type will be set to
+   ELF_T_BYTE, d_off will be zero, d_align will be 1 and d_version
+   will be set to EV_CURRENT.  If no memory could be allocated NULL is
+   returned and DATA->d_buf will be set to NULL.  Otherwise DATA will
+   be returned.  */
+extern Elf_Data *dwelf_strtab_finalize (Dwelf_Strtab *st,
+					Elf_Data *data)
+  __nonnull_attribute__ (1, 2);
+
+/* Get offset in string table for string associated with entry.  Only
+   valid after dwelf_strtab_finalize has been called.  */
+extern size_t dwelf_strent_off (Dwelf_Strent *se)
+  __nonnull_attribute__ (1);
+
+/* Return the string associated with the entry.  */
+extern const char *dwelf_strent_str (Dwelf_Strent *se)
+  __nonnull_attribute__ (1);
+
+/* Free resources allocated for the string table.  This invalidates
+   any Dwelf_Strent references returned earlier. */
+extern void dwelf_strtab_free (Dwelf_Strtab *st)
+  __nonnull_attribute__ (1);
+
 #ifdef __cplusplus
 }
 #endif