xref: /illumos-gate/usr/src/cmd/mandoc/dba.c (revision a40ea1a7)
1 /*	$Id: dba.c,v 1.10 2017/02/17 14:43:54 schwarze Exp $ */
2 /*
3  * Copyright (c) 2016, 2017 Ingo Schwarze <schwarze@openbsd.org>
4  *
5  * Permission to use, copy, modify, and distribute this software for any
6  * purpose with or without fee is hereby granted, provided that the above
7  * copyright notice and this permission notice appear in all copies.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16  *
17  * Allocation-based version of the mandoc database, for read-write access.
18  * The interface is defined in "dba.h".
19  */
20 #include "config.h"
21 
22 #include <sys/types.h>
23 #if HAVE_ENDIAN
24 #include <endian.h>
25 #elif HAVE_SYS_ENDIAN
26 #include <sys/endian.h>
27 #elif HAVE_NTOHL
28 #include <arpa/inet.h>
29 #endif
30 #include <errno.h>
31 #include <stddef.h>
32 #include <stdint.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include <unistd.h>
36 
37 #include "mandoc_aux.h"
38 #include "mandoc_ohash.h"
39 #include "mansearch.h"
40 #include "dba_write.h"
41 #include "dba_array.h"
42 #include "dba.h"
43 
44 struct macro_entry {
45 	struct dba_array	*pages;
46 	char			 value[];
47 };
48 
49 static void	*prepend(const char *, char);
50 static void	 dba_pages_write(struct dba_array *);
51 static int	 compare_names(const void *, const void *);
52 static int	 compare_strings(const void *, const void *);
53 
54 static struct macro_entry
55 		*get_macro_entry(struct ohash *, const char *, int32_t);
56 static void	 dba_macros_write(struct dba_array *);
57 static void	 dba_macro_write(struct ohash *);
58 static int	 compare_entries(const void *, const void *);
59 
60 
61 /*** top-level functions **********************************************/
62 
63 struct dba *
dba_new(int32_t npages)64 dba_new(int32_t npages)
65 {
66 	struct dba	*dba;
67 	struct ohash	*macro;
68 	int32_t		 im;
69 
70 	dba = mandoc_malloc(sizeof(*dba));
71 	dba->pages = dba_array_new(npages, DBA_GROW);
72 	dba->macros = dba_array_new(MACRO_MAX, 0);
73 	for (im = 0; im < MACRO_MAX; im++) {
74 		macro = mandoc_malloc(sizeof(*macro));
75 		mandoc_ohash_init(macro, 4,
76 		    offsetof(struct macro_entry, value));
77 		dba_array_set(dba->macros, im, macro);
78 	}
79 	return dba;
80 }
81 
82 void
dba_free(struct dba * dba)83 dba_free(struct dba *dba)
84 {
85 	struct dba_array	*page;
86 	struct ohash		*macro;
87 	struct macro_entry	*entry;
88 	unsigned int		 slot;
89 
90 	dba_array_FOREACH(dba->macros, macro) {
91 		for (entry = ohash_first(macro, &slot); entry != NULL;
92 		     entry = ohash_next(macro, &slot)) {
93 			dba_array_free(entry->pages);
94 			free(entry);
95 		}
96 		ohash_delete(macro);
97 		free(macro);
98 	}
99 	dba_array_free(dba->macros);
100 
101 	dba_array_undel(dba->pages);
102 	dba_array_FOREACH(dba->pages, page) {
103 		dba_array_free(dba_array_get(page, DBP_NAME));
104 		dba_array_free(dba_array_get(page, DBP_SECT));
105 		dba_array_free(dba_array_get(page, DBP_ARCH));
106 		free(dba_array_get(page, DBP_DESC));
107 		dba_array_free(dba_array_get(page, DBP_FILE));
108 		dba_array_free(page);
109 	}
110 	dba_array_free(dba->pages);
111 
112 	free(dba);
113 }
114 
115 /*
116  * Write the complete mandoc database to disk; the format is:
117  * - One integer each for magic and version.
118  * - One pointer each to the macros table and to the final magic.
119  * - The pages table.
120  * - The macros table.
121  * - And at the very end, the magic integer again.
122  */
123 int
dba_write(const char * fname,struct dba * dba)124 dba_write(const char *fname, struct dba *dba)
125 {
126 	int	 save_errno;
127 	int32_t	 pos_end, pos_macros, pos_macros_ptr;
128 
129 	if (dba_open(fname) == -1)
130 		return -1;
131 	dba_int_write(MANDOCDB_MAGIC);
132 	dba_int_write(MANDOCDB_VERSION);
133 	pos_macros_ptr = dba_skip(1, 2);
134 	dba_pages_write(dba->pages);
135 	pos_macros = dba_tell();
136 	dba_macros_write(dba->macros);
137 	pos_end = dba_tell();
138 	dba_int_write(MANDOCDB_MAGIC);
139 	dba_seek(pos_macros_ptr);
140 	dba_int_write(pos_macros);
141 	dba_int_write(pos_end);
142 	if (dba_close() == -1) {
143 		save_errno = errno;
144 		unlink(fname);
145 		errno = save_errno;
146 		return -1;
147 	}
148 	return 0;
149 }
150 
151 
152 /*** functions for handling pages *************************************/
153 
154 /*
155  * Create a new page and append it to the pages table.
156  */
157 struct dba_array *
dba_page_new(struct dba_array * pages,const char * arch,const char * desc,const char * file,enum form form)158 dba_page_new(struct dba_array *pages, const char *arch,
159     const char *desc, const char *file, enum form form)
160 {
161 	struct dba_array *page, *entry;
162 
163 	page = dba_array_new(DBP_MAX, 0);
164 	entry = dba_array_new(1, DBA_STR | DBA_GROW);
165 	dba_array_add(page, entry);
166 	entry = dba_array_new(1, DBA_STR | DBA_GROW);
167 	dba_array_add(page, entry);
168 	if (arch != NULL && *arch != '\0') {
169 		entry = dba_array_new(1, DBA_STR | DBA_GROW);
170 		dba_array_add(entry, (void *)arch);
171 	} else
172 		entry = NULL;
173 	dba_array_add(page, entry);
174 	dba_array_add(page, mandoc_strdup(desc));
175 	entry = dba_array_new(1, DBA_STR | DBA_GROW);
176 	dba_array_add(entry, prepend(file, form));
177 	dba_array_add(page, entry);
178 	dba_array_add(pages, page);
179 	return page;
180 }
181 
182 /*
183  * Add a section, architecture, or file name to an existing page.
184  * Passing the NULL pointer for the architecture makes the page MI.
185  * In that case, any earlier or later architectures are ignored.
186  */
187 void
dba_page_add(struct dba_array * page,int32_t ie,const char * str)188 dba_page_add(struct dba_array *page, int32_t ie, const char *str)
189 {
190 	struct dba_array	*entries;
191 	char			*entry;
192 
193 	entries = dba_array_get(page, ie);
194 	if (ie == DBP_ARCH) {
195 		if (entries == NULL)
196 			return;
197 		if (str == NULL || *str == '\0') {
198 			dba_array_free(entries);
199 			dba_array_set(page, DBP_ARCH, NULL);
200 			return;
201 		}
202 	}
203 	if (*str == '\0')
204 		return;
205 	dba_array_FOREACH(entries, entry) {
206 		if (ie == DBP_FILE && *entry < ' ')
207 			entry++;
208 		if (strcmp(entry, str) == 0)
209 			return;
210 	}
211 	dba_array_add(entries, (void *)str);
212 }
213 
214 /*
215  * Add an additional name to an existing page.
216  */
217 void
dba_page_alias(struct dba_array * page,const char * name,uint64_t mask)218 dba_page_alias(struct dba_array *page, const char *name, uint64_t mask)
219 {
220 	struct dba_array	*entries;
221 	char			*entry;
222 	char			 maskbyte;
223 
224 	if (*name == '\0')
225 		return;
226 	maskbyte = mask & NAME_MASK;
227 	entries = dba_array_get(page, DBP_NAME);
228 	dba_array_FOREACH(entries, entry) {
229 		if (strcmp(entry + 1, name) == 0) {
230 			*entry |= maskbyte;
231 			return;
232 		}
233 	}
234 	dba_array_add(entries, prepend(name, maskbyte));
235 }
236 
237 /*
238  * Return a pointer to a temporary copy of instr with inbyte prepended.
239  */
240 static void *
prepend(const char * instr,char inbyte)241 prepend(const char *instr, char inbyte)
242 {
243 	static char	*outstr = NULL;
244 	static size_t	 outlen = 0;
245 	size_t		 newlen;
246 
247 	newlen = strlen(instr) + 1;
248 	if (newlen > outlen) {
249 		outstr = mandoc_realloc(outstr, newlen + 1);
250 		outlen = newlen;
251 	}
252 	*outstr = inbyte;
253 	memcpy(outstr + 1, instr, newlen);
254 	return outstr;
255 }
256 
257 /*
258  * Write the pages table to disk; the format is:
259  * - One integer containing the number of pages.
260  * - For each page, five pointers to the names, sections,
261  *   architectures, description, and file names of the page.
262  *   MI pages write 0 instead of the architecture pointer.
263  * - One list each for names, sections, architectures, descriptions and
264  *   file names.  The description for each page ends with a NUL byte.
265  *   For all the other lists, each string ends with a NUL byte,
266  *   and the last string for a page ends with two NUL bytes.
267  * - To assure alignment of following integers,
268  *   the end is padded with NUL bytes up to a multiple of four bytes.
269  */
270 static void
dba_pages_write(struct dba_array * pages)271 dba_pages_write(struct dba_array *pages)
272 {
273 	struct dba_array	*page, *entry;
274 	int32_t			 pos_pages, pos_end;
275 
276 	pos_pages = dba_array_writelen(pages, 5);
277 	dba_array_FOREACH(pages, page) {
278 		dba_array_setpos(page, DBP_NAME, dba_tell());
279 		entry = dba_array_get(page, DBP_NAME);
280 		dba_array_sort(entry, compare_names);
281 		dba_array_writelst(entry);
282 	}
283 	dba_array_FOREACH(pages, page) {
284 		dba_array_setpos(page, DBP_SECT, dba_tell());
285 		entry = dba_array_get(page, DBP_SECT);
286 		dba_array_sort(entry, compare_strings);
287 		dba_array_writelst(entry);
288 	}
289 	dba_array_FOREACH(pages, page) {
290 		if ((entry = dba_array_get(page, DBP_ARCH)) != NULL) {
291 			dba_array_setpos(page, DBP_ARCH, dba_tell());
292 			dba_array_sort(entry, compare_strings);
293 			dba_array_writelst(entry);
294 		} else
295 			dba_array_setpos(page, DBP_ARCH, 0);
296 	}
297 	dba_array_FOREACH(pages, page) {
298 		dba_array_setpos(page, DBP_DESC, dba_tell());
299 		dba_str_write(dba_array_get(page, DBP_DESC));
300 	}
301 	dba_array_FOREACH(pages, page) {
302 		dba_array_setpos(page, DBP_FILE, dba_tell());
303 		dba_array_writelst(dba_array_get(page, DBP_FILE));
304 	}
305 	pos_end = dba_align();
306 	dba_seek(pos_pages);
307 	dba_array_FOREACH(pages, page)
308 		dba_array_writepos(page);
309 	dba_seek(pos_end);
310 }
311 
312 static int
compare_names(const void * vp1,const void * vp2)313 compare_names(const void *vp1, const void *vp2)
314 {
315 	const char	*cp1, *cp2;
316 	int		 diff;
317 
318 	cp1 = *(const char * const *)vp1;
319 	cp2 = *(const char * const *)vp2;
320 	return (diff = *cp2 - *cp1) ? diff :
321 	    strcasecmp(cp1 + 1, cp2 + 1);
322 }
323 
324 static int
compare_strings(const void * vp1,const void * vp2)325 compare_strings(const void *vp1, const void *vp2)
326 {
327 	const char	*cp1, *cp2;
328 
329 	cp1 = *(const char * const *)vp1;
330 	cp2 = *(const char * const *)vp2;
331 	return strcmp(cp1, cp2);
332 }
333 
334 /*** functions for handling macros ************************************/
335 
336 /*
337  * In the hash table for a single macro, look up an entry by
338  * the macro value or add an empty one if it doesn't exist yet.
339  */
340 static struct macro_entry *
get_macro_entry(struct ohash * macro,const char * value,int32_t np)341 get_macro_entry(struct ohash *macro, const char *value, int32_t np)
342 {
343 	struct macro_entry	*entry;
344 	size_t			 len;
345 	unsigned int		 slot;
346 
347 	slot = ohash_qlookup(macro, value);
348 	if ((entry = ohash_find(macro, slot)) == NULL) {
349 		len = strlen(value) + 1;
350 		entry = mandoc_malloc(sizeof(*entry) + len);
351 		memcpy(&entry->value, value, len);
352 		entry->pages = dba_array_new(np, DBA_GROW);
353 		ohash_insert(macro, slot, entry);
354 	}
355 	return entry;
356 }
357 
358 /*
359  * In addition to get_macro_entry(), add multiple page references,
360  * converting them from the on-disk format (byte offsets in the file)
361  * to page pointers in memory.
362  */
363 void
dba_macro_new(struct dba * dba,int32_t im,const char * value,const int32_t * pp)364 dba_macro_new(struct dba *dba, int32_t im, const char *value,
365     const int32_t *pp)
366 {
367 	struct macro_entry	*entry;
368 	const int32_t		*ip;
369 	int32_t			 np;
370 
371 	np = 0;
372 	for (ip = pp; *ip; ip++)
373 		np++;
374 
375 	entry = get_macro_entry(dba_array_get(dba->macros, im), value, np);
376 	for (ip = pp; *ip; ip++)
377 		dba_array_add(entry->pages, dba_array_get(dba->pages,
378 		    be32toh(*ip) / 5 / sizeof(*ip) - 1));
379 }
380 
381 /*
382  * In addition to get_macro_entry(), add one page reference,
383  * directly taking the in-memory page pointer as an argument.
384  */
385 void
dba_macro_add(struct dba_array * macros,int32_t im,const char * value,struct dba_array * page)386 dba_macro_add(struct dba_array *macros, int32_t im, const char *value,
387     struct dba_array *page)
388 {
389 	struct macro_entry	*entry;
390 
391 	if (*value == '\0')
392 		return;
393 	entry = get_macro_entry(dba_array_get(macros, im), value, 1);
394 	dba_array_add(entry->pages, page);
395 }
396 
397 /*
398  * Write the macros table to disk; the format is:
399  * - The number of macro tables (actually, MACRO_MAX).
400  * - That number of pointers to the individual macro tables.
401  * - The individual macro tables.
402  */
403 static void
dba_macros_write(struct dba_array * macros)404 dba_macros_write(struct dba_array *macros)
405 {
406 	struct ohash		*macro;
407 	int32_t			 im, pos_macros, pos_end;
408 
409 	pos_macros = dba_array_writelen(macros, 1);
410 	im = 0;
411 	dba_array_FOREACH(macros, macro) {
412 		dba_array_setpos(macros, im++, dba_tell());
413 		dba_macro_write(macro);
414 	}
415 	pos_end = dba_tell();
416 	dba_seek(pos_macros);
417 	dba_array_writepos(macros);
418 	dba_seek(pos_end);
419 }
420 
421 /*
422  * Write one individual macro table to disk; the format is:
423  * - The number of entries in the table.
424  * - For each entry, two pointers, the first one to the value
425  *   and the second one to the list of pages.
426  * - A list of values, each ending in a NUL byte.
427  * - To assure alignment of following integers,
428  *   padding with NUL bytes up to a multiple of four bytes.
429  * - A list of pointers to pages, each list ending in a 0 integer.
430  */
431 static void
dba_macro_write(struct ohash * macro)432 dba_macro_write(struct ohash *macro)
433 {
434 	struct macro_entry	**entries, *entry;
435 	struct dba_array	 *page;
436 	int32_t			 *kpos, *dpos;
437 	unsigned int		  ie, ne, slot;
438 	int			  use;
439 	int32_t			  addr, pos_macro, pos_end;
440 
441 	/* Temporary storage for filtering and sorting. */
442 
443 	ne = ohash_entries(macro);
444 	entries = mandoc_reallocarray(NULL, ne, sizeof(*entries));
445 	kpos = mandoc_reallocarray(NULL, ne, sizeof(*kpos));
446 	dpos = mandoc_reallocarray(NULL, ne, sizeof(*dpos));
447 
448 	/* Build a list of non-empty entries and sort it. */
449 
450 	ne = 0;
451 	for (entry = ohash_first(macro, &slot); entry != NULL;
452 	     entry = ohash_next(macro, &slot)) {
453 		use = 0;
454 		dba_array_FOREACH(entry->pages, page)
455 			if (dba_array_getpos(page))
456 				use = 1;
457 		if (use)
458 			entries[ne++] = entry;
459 	}
460 	qsort(entries, ne, sizeof(*entries), compare_entries);
461 
462 	/* Number of entries, and space for the pointer pairs. */
463 
464 	dba_int_write(ne);
465 	pos_macro = dba_skip(2, ne);
466 
467 	/* String table. */
468 
469 	for (ie = 0; ie < ne; ie++) {
470 		kpos[ie] = dba_tell();
471 		dba_str_write(entries[ie]->value);
472 	}
473 	dba_align();
474 
475 	/* Pages table. */
476 
477 	for (ie = 0; ie < ne; ie++) {
478 		dpos[ie] = dba_tell();
479 		dba_array_FOREACH(entries[ie]->pages, page)
480 			if ((addr = dba_array_getpos(page)))
481 				dba_int_write(addr);
482 		dba_int_write(0);
483 	}
484 	pos_end = dba_tell();
485 
486 	/* Fill in the pointer pairs. */
487 
488 	dba_seek(pos_macro);
489 	for (ie = 0; ie < ne; ie++) {
490 		dba_int_write(kpos[ie]);
491 		dba_int_write(dpos[ie]);
492 	}
493 	dba_seek(pos_end);
494 
495 	free(entries);
496 	free(kpos);
497 	free(dpos);
498 }
499 
500 static int
compare_entries(const void * vp1,const void * vp2)501 compare_entries(const void *vp1, const void *vp2)
502 {
503 	const struct macro_entry *ep1, *ep2;
504 
505 	ep1 = *(const struct macro_entry * const *)vp1;
506 	ep2 = *(const struct macro_entry * const *)vp2;
507 	return strcmp(ep1->value, ep2->value);
508 }
509