1/*-
2 * Copyright (c) 2013, Joseph Koshy
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer
10 *    in this position and unchanged.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include <sys/param.h>
28#include <sys/queue.h>
29
30#include <assert.h>
31#include <errno.h>
32#include <gelf.h>
33#include <stdlib.h>
34#include <string.h>
35
36#include "libelftc.h"
37#include "_libelftc.h"
38
39ELFTC_VCSID("$Id: elftc_string_table.c 3750 2019-06-28 01:12:10Z emaste $");
40
41#define	ELFTC_STRING_TABLE_DEFAULT_SIZE			(4*1024)
42#define ELFTC_STRING_TABLE_EXPECTED_STRING_SIZE		16
43#define ELFTC_STRING_TABLE_EXPECTED_CHAIN_LENGTH	8
44#define	ELFTC_STRING_TABLE_POOL_SIZE_INCREMENT		(4*1024)
45
46struct _Elftc_String_Table_Entry {
47	ssize_t		ste_idx;
48	SLIST_ENTRY(_Elftc_String_Table_Entry) ste_next;
49};
50
51#define	ELFTC_STRING_TABLE_COMPACTION_FLAG	0x1
52#define	ELFTC_STRING_TABLE_LENGTH(st)		((st)->st_len >> 1)
53#define	ELFTC_STRING_TABLE_CLEAR_COMPACTION_FLAG(st) do {		\
54		(st)->st_len &= ~ELFTC_STRING_TABLE_COMPACTION_FLAG;	\
55	} while (0)
56#define	ELFTC_STRING_TABLE_SET_COMPACTION_FLAG(st) do {			\
57		(st)->st_len |= ELFTC_STRING_TABLE_COMPACTION_FLAG;	\
58	} while (0)
59#define	ELFTC_STRING_TABLE_UPDATE_LENGTH(st, len) do {		\
60		(st)->st_len =					\
61		    ((st)->st_len &				\
62			ELFTC_STRING_TABLE_COMPACTION_FLAG) |	\
63		    ((len) << 1);				\
64	} while (0)
65
66struct _Elftc_String_Table {
67	size_t		st_len; /* length and flags */
68	int		st_nbuckets;
69	size_t		st_string_pool_size;
70	char		*st_string_pool;
71	SLIST_HEAD(_Elftc_String_Table_Bucket,
72	    _Elftc_String_Table_Entry) st_buckets[];
73};
74
75static struct _Elftc_String_Table_Entry *
76elftc_string_table_find_hash_entry(Elftc_String_Table *st, const char *string,
77    int *rhashindex)
78{
79	struct _Elftc_String_Table_Entry *ste;
80	int hashindex;
81	char *s;
82
83	hashindex = libelftc_hash_string(string) % st->st_nbuckets;
84
85	if (rhashindex)
86		*rhashindex = hashindex;
87
88	SLIST_FOREACH(ste, &st->st_buckets[hashindex], ste_next) {
89		s = st->st_string_pool + labs(ste->ste_idx);
90
91		assert(s > st->st_string_pool &&
92		    s < st->st_string_pool + st->st_string_pool_size);
93
94		if (strcmp(s, string) == 0)
95			return (ste);
96	}
97
98	return (NULL);
99}
100
101static int
102elftc_string_table_add_to_pool(Elftc_String_Table *st, const char *string)
103{
104	char *newpool;
105	size_t len, newsize, stlen;
106
107	len = strlen(string) + 1; /* length, including the trailing NUL */
108	stlen = ELFTC_STRING_TABLE_LENGTH(st);
109
110	/* Resize the pool, if needed. */
111	if (stlen + len >= st->st_string_pool_size) {
112		newsize = roundup(st->st_string_pool_size +
113		    ELFTC_STRING_TABLE_POOL_SIZE_INCREMENT,
114		    ELFTC_STRING_TABLE_POOL_SIZE_INCREMENT);
115		if ((newpool = realloc(st->st_string_pool, newsize)) ==
116		    NULL)
117			return (0);
118		st->st_string_pool = newpool;
119		st->st_string_pool_size = newsize;
120	}
121
122	memcpy(st->st_string_pool + stlen, string, len);
123	ELFTC_STRING_TABLE_UPDATE_LENGTH(st, stlen + len);
124
125	return (stlen);
126}
127
128Elftc_String_Table *
129elftc_string_table_create(size_t sizehint)
130{
131	struct _Elftc_String_Table *st;
132	int n, nbuckets, tablesize;
133
134	if (sizehint < ELFTC_STRING_TABLE_DEFAULT_SIZE)
135		sizehint = ELFTC_STRING_TABLE_DEFAULT_SIZE;
136
137	nbuckets = sizehint / (ELFTC_STRING_TABLE_EXPECTED_CHAIN_LENGTH *
138	    ELFTC_STRING_TABLE_EXPECTED_STRING_SIZE);
139
140	tablesize = sizeof(struct _Elftc_String_Table) +
141	    nbuckets * sizeof(struct _Elftc_String_Table_Bucket);
142
143	if ((st = malloc(tablesize)) == NULL)
144		return (NULL);
145	if ((st->st_string_pool = malloc(sizehint)) == NULL) {
146		free(st);
147		return (NULL);
148	}
149
150	for (n = 0; n < nbuckets; n++)
151		SLIST_INIT(&st->st_buckets[n]);
152
153	st->st_len = 0;
154	st->st_nbuckets = nbuckets;
155	st->st_string_pool_size = sizehint;
156	*st->st_string_pool = '\0';
157	ELFTC_STRING_TABLE_UPDATE_LENGTH(st, 1);
158
159	return (st);
160}
161
162void
163elftc_string_table_destroy(Elftc_String_Table *st)
164{
165	int n;
166	struct _Elftc_String_Table_Entry *s, *t;
167
168	for (n = 0; n < st->st_nbuckets; n++)
169		SLIST_FOREACH_SAFE(s, &st->st_buckets[n], ste_next, t)
170			free(s);
171	free(st->st_string_pool);
172	free(st);
173}
174
175Elftc_String_Table *
176elftc_string_table_from_section(Elf_Scn *scn, size_t sizehint)
177{
178	Elf_Data *d;
179	GElf_Shdr sh;
180	const char *s, *end;
181	Elftc_String_Table *st;
182	size_t len;
183
184	/* Verify the type of the section passed in. */
185	if (gelf_getshdr(scn, &sh) == NULL ||
186	    sh.sh_type != SHT_STRTAB) {
187		errno = EINVAL;
188		return (NULL);
189	}
190
191	if ((d = elf_getdata(scn, NULL)) == NULL ||
192	    d->d_size == 0) {
193		errno = EINVAL;
194		return (NULL);
195	}
196
197	if ((st = elftc_string_table_create(sizehint)) == NULL)
198		return (NULL);
199
200	s = d->d_buf;
201
202	/*
203	 * Verify that the first byte of the data buffer is '\0'.
204	 */
205	if (*s != '\0') {
206		errno = EINVAL;
207		goto fail;
208	}
209
210	end = s + d->d_size;
211
212	/*
213	 * Skip the first '\0' and insert the strings in the buffer,
214	 * in order.
215	 */
216	for (s += 1; s < end; s += len) {
217		if (elftc_string_table_insert(st, s) == 0)
218			goto fail;
219
220		len = strlen(s) + 1; /* Include space for the trailing NUL. */
221	}
222
223	return (st);
224
225fail:
226	if (st)
227		(void) elftc_string_table_destroy(st);
228
229	return (NULL);
230}
231
232const char *
233elftc_string_table_image(Elftc_String_Table *st, size_t *size)
234{
235	char *r, *s, *end;
236	struct _Elftc_String_Table_Entry *ste;
237	struct _Elftc_String_Table_Bucket *head;
238	size_t copied, offset, length, newsize;
239	int hashindex;
240
241	/*
242	 * For the common case of a string table has not seen
243	 * a string deletion, we can just export the current
244	 * pool.
245	 */
246	if ((st->st_len & ELFTC_STRING_TABLE_COMPACTION_FLAG) == 0) {
247		if (size)
248			*size = ELFTC_STRING_TABLE_LENGTH(st);
249		return (st->st_string_pool);
250	}
251
252	/*
253	 * Otherwise, compact the string table in-place.
254	 */
255	assert(*st->st_string_pool == '\0');
256
257	newsize = 1;
258	end = st->st_string_pool + ELFTC_STRING_TABLE_LENGTH(st);
259
260	for (r = s = st->st_string_pool + 1;
261	     s < end;
262	     s += length, r += copied) {
263
264		copied = 0;
265		length = strlen(s) + 1;
266
267		ste = elftc_string_table_find_hash_entry(st, s,
268		    &hashindex);
269		head = &st->st_buckets[hashindex];
270
271		assert(ste != NULL);
272
273		/* Ignore deleted strings. */
274		if (ste->ste_idx < 0) {
275			SLIST_REMOVE(head, ste, _Elftc_String_Table_Entry,
276			    ste_next);
277			free(ste);
278			continue;
279		}
280
281		/* Move 'live' strings up. */
282		offset = newsize;
283		newsize += length;
284		copied = length;
285
286		if (r == s)	/* Nothing removed yet. */
287			continue;
288
289		memmove(r, s, copied);
290
291		/* Update the index for this entry. */
292		ste->ste_idx = offset;
293	}
294
295	ELFTC_STRING_TABLE_CLEAR_COMPACTION_FLAG(st);
296	ELFTC_STRING_TABLE_UPDATE_LENGTH(st, newsize);
297
298	if (size)
299		*size = newsize;
300
301	return (st->st_string_pool);
302}
303
304size_t
305elftc_string_table_insert(Elftc_String_Table *st, const char *string)
306{
307	struct _Elftc_String_Table_Entry *ste;
308	ssize_t idx;
309	int hashindex;
310
311	hashindex = 0;
312
313	ste = elftc_string_table_find_hash_entry(st, string, &hashindex);
314
315	assert(hashindex >= 0 && hashindex < st->st_nbuckets);
316
317	if (ste == NULL) {
318		if ((ste = malloc(sizeof(*ste))) == NULL)
319			return (0);
320		if ((ste->ste_idx = elftc_string_table_add_to_pool(st,
321		    string)) == 0) {
322			free(ste);
323			return (0);
324		}
325
326		SLIST_INSERT_HEAD(&st->st_buckets[hashindex], ste, ste_next);
327	}
328
329	idx = ste->ste_idx;
330	if (idx < 0) 		/* Undelete. */
331		ste->ste_idx = idx = -idx;
332
333	return (idx);
334}
335
336size_t
337elftc_string_table_lookup(Elftc_String_Table *st, const char *string)
338{
339	struct _Elftc_String_Table_Entry *ste;
340	ssize_t idx;
341	int hashindex;
342
343	ste = elftc_string_table_find_hash_entry(st, string, &hashindex);
344
345	assert(hashindex >= 0 && hashindex < st->st_nbuckets);
346
347	if (ste == NULL || (idx = ste->ste_idx) < 0)
348		return (0);
349
350	return (idx);
351}
352
353int
354elftc_string_table_remove(Elftc_String_Table *st, const char *string)
355{
356	struct _Elftc_String_Table_Entry *ste;
357	ssize_t idx;
358
359	ste = elftc_string_table_find_hash_entry(st, string, NULL);
360
361	if (ste == NULL || (idx = ste->ste_idx) < 0)
362		return (ELFTC_FAILURE);
363
364	assert(idx > 0 && (size_t)idx < ELFTC_STRING_TABLE_LENGTH(st));
365
366	ste->ste_idx = -idx;
367
368	ELFTC_STRING_TABLE_SET_COMPACTION_FLAG(st);
369
370	return (ELFTC_SUCCESS);
371}
372
373const char *
374elftc_string_table_to_string(Elftc_String_Table *st, size_t offset)
375{
376	const char *s;
377
378	s = st->st_string_pool + offset;
379
380	/*
381	 * Check for:
382	 * - An offset value within pool bounds.
383	 * - A non-NUL byte at the specified offset.
384	 * - The end of the prior string at offset - 1.
385	 */
386	if (offset == 0 || offset >= ELFTC_STRING_TABLE_LENGTH(st) ||
387	    *s == '\0' || *(s - 1) != '\0') {
388		errno = EINVAL;
389		return (NULL);
390	}
391
392	return (s);
393}
394