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