← Back to branch summary

~ubuntu-branches/ubuntu/quantal/elfutils/quantal

« back to all changes in this revision

Viewing changes to libebl/eblstrtab.c

  • Committer: Bazaar Package Importer
  • Author(s): Kurt Roeckx
  • Date: 2006-08-27 15:48:23 UTC
  • Revision ID: james.westby@ubuntu.com-20060827154823-mjwd7ydlbxgwqn4u
Tags: upstream-0.123
Import upstream version 0.123

Show diffs side-by-side

added added

removed removed

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