1/* ELF string table handling.
2   Copyright (C) 2000, 2001, 2002 Red Hat, Inc.
3   This file is part of elfutils.
4   Written by Ulrich Drepper <drepper@redhat.com>, 2000.
5
6   This file is free software; you can redistribute it and/or modify
7   it under the terms of either
8
9     * the GNU Lesser General Public License as published by the Free
10       Software Foundation; either version 3 of the License, or (at
11       your option) any later version
12
13   or
14
15     * the GNU General Public License as published by the Free
16       Software Foundation; either version 2 of the License, or (at
17       your option) any later version
18
19   or both in parallel, as here.
20
21   elfutils is distributed in the hope that it will be useful, but
22   WITHOUT ANY WARRANTY; without even the implied warranty of
23   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24   General Public License for more details.
25
26   You should have received copies of the GNU General Public License and
27   the GNU Lesser General Public License along with this program.  If
28   not, see <http://www.gnu.org/licenses/>.  */
29
30#ifdef HAVE_CONFIG_H
31# include <config.h>
32#endif
33
34#include <assert.h>
35#include <inttypes.h>
36#include <libelf.h>
37#include <stddef.h>
38#include <stdlib.h>
39#include <string.h>
40#include <unistd.h>
41#include <wchar.h>
42#include <sys/param.h>
43
44#include "libebl.h"
45#include <system.h>
46
47#ifndef MIN
48# define MIN(a, b) ((a) < (b) ? (a) : (b))
49#endif
50
51
52struct Ebl_WStrent
53{
54  const wchar_t *string;
55  size_t len;
56  struct Ebl_WStrent *next;
57  struct Ebl_WStrent *left;
58  struct Ebl_WStrent *right;
59  size_t offset;
60  wchar_t reverse[0];
61};
62
63
64struct memoryblock
65{
66  struct memoryblock *next;
67  char memory[0];
68};
69
70
71struct Ebl_WStrtab
72{
73  struct Ebl_WStrent *root;
74  struct memoryblock *memory;
75  char *backp;
76  size_t left;
77  size_t total;
78  bool nullstr;
79
80  struct Ebl_WStrent null;
81};
82
83
84/* Cache for the pagesize.  We correct this value a bit so that `malloc'
85   is not allocating more than a page.  */
86static size_t ps;
87
88
89struct Ebl_WStrtab *
90ebl_wstrtabinit (bool nullstr)
91{
92  struct Ebl_WStrtab *ret;
93
94  if (ps == 0)
95    {
96      ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
97      assert (sizeof (struct memoryblock) < ps);
98    }
99
100  ret = (struct Ebl_WStrtab *) calloc (1, sizeof (struct Ebl_WStrtab));
101  if (ret != NULL)
102    {
103      ret->nullstr = nullstr;
104      if (nullstr)
105	{
106	  ret->null.len = 1;
107	  ret->null.string = L"";
108	}
109    }
110  return ret;
111}
112
113
114static int
115morememory (struct Ebl_WStrtab *st, size_t len)
116{
117  struct memoryblock *newmem;
118
119  if (len < ps)
120    len = ps;
121  newmem = (struct memoryblock *) malloc (len);
122  if (newmem == NULL)
123    return 1;
124
125  newmem->next = st->memory;
126  st->memory = newmem;
127  st->backp = newmem->memory;
128  st->left = len - offsetof (struct memoryblock, memory);
129
130  return 0;
131}
132
133
134void
135ebl_wstrtabfree (struct Ebl_WStrtab *st)
136{
137  struct memoryblock *mb = st->memory;
138
139  while (mb != NULL)
140    {
141      void *old = mb;
142      mb = mb->next;
143      free (old);
144    }
145
146  free (st);
147}
148
149
150static struct Ebl_WStrent *
151newstring (struct Ebl_WStrtab *st, const wchar_t *str, size_t len)
152{
153  struct Ebl_WStrent *newstr;
154  size_t align;
155  int i;
156
157  /* Compute the amount of padding needed to make the structure aligned.  */
158  align = ((__alignof__ (struct Ebl_WStrent)
159	    - (((uintptr_t) st->backp)
160	       & (__alignof__ (struct Ebl_WStrent) - 1)))
161	   & (__alignof__ (struct Ebl_WStrent) - 1));
162
163  /* Make sure there is enough room in the memory block.  */
164  if (st->left < align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t))
165    {
166      if (morememory (st,
167		      sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t)))
168	return NULL;
169
170      align = 0;
171    }
172
173  /* Create the reserved string.  */
174  newstr = (struct Ebl_WStrent *) (st->backp + align);
175  newstr->string = str;
176  newstr->len = len;
177  newstr->next = NULL;
178  newstr->left = NULL;
179  newstr->right = NULL;
180  newstr->offset = 0;
181  for (i = len - 2; i >= 0; --i)
182    newstr->reverse[i] = str[len - 2 - i];
183  newstr->reverse[len - 1] = L'\0';
184  st->backp += align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t);
185  st->left -= align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t);
186
187  return newstr;
188}
189
190
191/* XXX This function should definitely be rewritten to use a balancing
192   tree algorith (AVL, red-black trees).  For now a simple, correct
193   implementation is enough.  */
194static struct Ebl_WStrent **
195searchstring (struct Ebl_WStrent **sep, struct Ebl_WStrent *newstr)
196{
197  int cmpres;
198
199  /* More strings?  */
200  if (*sep == NULL)
201    {
202      *sep = newstr;
203      return sep;
204    }
205
206  /* Compare the strings.  */
207  cmpres = wmemcmp ((*sep)->reverse, newstr->reverse,
208		    MIN ((*sep)->len, newstr->len) - 1);
209  if (cmpres == 0)
210    /* We found a matching string.  */
211    return sep;
212  else if (cmpres > 0)
213    return searchstring (&(*sep)->left, newstr);
214  else
215    return searchstring (&(*sep)->right, newstr);
216}
217
218
219/* Add new string.  The actual string is assumed to be permanent.  */
220struct Ebl_WStrent *
221ebl_wstrtabadd (struct Ebl_WStrtab *st, const wchar_t *str, size_t len)
222{
223  struct Ebl_WStrent *newstr;
224  struct Ebl_WStrent **sep;
225
226  /* Compute the string length if the caller doesn't know it.  */
227  if (len == 0)
228    len = wcslen (str) + 1;
229
230  /* Make sure all "" strings get offset 0 but only if the table was
231     created with a special null entry in mind.  */
232  if (len == 1 && st->null.string != NULL)
233    return &st->null;
234
235  /* Allocate memory for the new string and its associated information.  */
236  newstr = newstring (st, str, len);
237  if (newstr == NULL)
238    return NULL;
239
240  /* Search in the array for the place to insert the string.  If there
241     is no string with matching prefix and no string with matching
242     leading substring, create a new entry.  */
243  sep = searchstring (&st->root, newstr);
244  if (*sep != newstr)
245    {
246      /* This is not the same entry.  This means we have a prefix match.  */
247      if ((*sep)->len > newstr->len)
248	{
249	  struct Ebl_WStrent *subs;
250
251	  /* Check whether we already know this string.  */
252	  for (subs = (*sep)->next; subs != NULL; subs = subs->next)
253	    if (subs->len == newstr->len)
254	      {
255		/* We have an exact match with a substring.  Free the memory
256		   we allocated.  */
257		st->left += st->backp - (char *) newstr;
258		st->backp = (char *) newstr;
259
260		return subs;
261	      }
262
263	  /* We have a new substring.  This means we don't need the reverse
264	     string of this entry anymore.  */
265	  st->backp -= newstr->len;
266	  st->left += newstr->len;
267
268	  newstr->next = (*sep)->next;
269	  (*sep)->next = newstr;
270	}
271      else if ((*sep)->len != newstr->len)
272	{
273	  /* When we get here it means that the string we are about to
274	     add has a common prefix with a string we already have but
275	     it is longer.  In this case we have to put it first.  */
276	  st->total += newstr->len - (*sep)->len;
277	  newstr->next = *sep;
278	  newstr->left = (*sep)->left;
279	  newstr->right = (*sep)->right;
280	  *sep = newstr;
281	}
282      else
283	{
284	  /* We have an exact match.  Free the memory we allocated.  */
285	  st->left += st->backp - (char *) newstr;
286	  st->backp = (char *) newstr;
287
288	  newstr = *sep;
289	}
290    }
291  else
292    st->total += newstr->len;
293
294  return newstr;
295}
296
297
298static void
299copystrings (struct Ebl_WStrent *nodep, wchar_t **freep, size_t *offsetp)
300{
301  struct Ebl_WStrent *subs;
302
303  if (nodep->left != NULL)
304    copystrings (nodep->left, freep, offsetp);
305
306  /* Process the current node.  */
307  nodep->offset = *offsetp;
308  *freep = wmempcpy (*freep, nodep->string, nodep->len);
309  *offsetp += nodep->len * sizeof (wchar_t);
310
311  for (subs = nodep->next; subs != NULL; subs = subs->next)
312    {
313      assert (subs->len < nodep->len);
314      subs->offset = nodep->offset + nodep->len - subs->len;
315      assert (subs->offset != 0 || subs->string[0] == '\0');
316    }
317
318  if (nodep->right != NULL)
319    copystrings (nodep->right, freep, offsetp);
320}
321
322
323void
324ebl_wstrtabfinalize (struct Ebl_WStrtab *st, Elf_Data *data)
325{
326  size_t copylen;
327  wchar_t *endp;
328  size_t nulllen = st->nullstr ? 1 : 0;
329
330  /* Fill in the information.  */
331  data->d_buf = malloc ((st->total + nulllen) * sizeof (wchar_t));
332  if (data->d_buf == NULL)
333    abort ();
334
335  /* The first byte must always be zero if we created the table with a
336     null string.  */
337  if (st->nullstr)
338    *((wchar_t *) data->d_buf) = L'\0';
339
340  data->d_type = ELF_T_BYTE;
341  data->d_size = st->total + nulllen;
342  data->d_off = 0;
343  data->d_align = 1;
344  data->d_version = EV_CURRENT;
345
346  /* Now run through the tree and add all the string while also updating
347     the offset members of the elfstrent records.  */
348  endp = (wchar_t *) data->d_buf + nulllen;
349  copylen = sizeof (wchar_t) * nulllen;
350  copystrings (st->root, &endp, &copylen);
351  assert (copylen == (st->total + nulllen) * sizeof (wchar_t));
352}
353
354
355size_t
356ebl_wstrtaboffset (struct Ebl_WStrent *se)
357{
358  return se->offset;
359}
360