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 
39 ELFTC_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 
46 struct _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 
66 struct _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 
75 static struct _Elftc_String_Table_Entry *
76 elftc_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 
101 static int
102 elftc_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 
128 Elftc_String_Table *
129 elftc_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 
162 void
163 elftc_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 
175 Elftc_String_Table *
176 elftc_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 
225 fail:
226 	if (st)
227 		(void) elftc_string_table_destroy(st);
228 
229 	return (NULL);
230 }
231 
232 const char *
233 elftc_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 
304 size_t
305 elftc_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 
336 size_t
337 elftc_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 
353 int
354 elftc_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 
373 const char *
374 elftc_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