1 /* Create simple DB database from textual input.
2 Copyright (C) 1996-2020 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Ulrich Drepper <drepper@cygnus.com>, 1996.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, see
18 <https://www.gnu.org/licenses/>. */
37 #include <sys/param.h>
40 #include "nss_db/nss_db.h"
42 /* Get libc version number. */
43 #include "../version.h"
45 /* The hashing function we use. */
46 #include "../intl/hash-string.h"
48 /* SELinux support. */
50 # include <selinux/selinux.h>
54 # define MAP_POPULATE 0
57 #define PACKAGE _libc_intl_domainname
59 /* List of data bases. */
64 struct database *next;
73 static size_t ndatabases;
74 static size_t nhashentries_total;
75 static size_t valstrlen;
76 static void *valstrtree;
77 static char *valstrtab;
78 static size_t extrastrlen;
88 /* Stored string entry. */
97 /* True if any entry has been added. */
98 static bool any_dbentry;
100 /* If non-zero convert key to lower case. */
101 static int to_lowercase;
103 /* If non-zero print content of input file, one entry per line. */
106 /* If non-zero do not print informational messages. */
109 /* Name of output file. */
110 static const char *output_name;
112 /* Name and version of program. */
113 static void print_version (FILE *stream, struct argp_state *state);
114 void (*argp_program_version_hook) (FILE *, struct argp_state *) = print_version;
116 /* Definitions of arguments for argp functions. */
117 static const struct argp_option options[] =
119 { "fold-case", 'f', NULL, 0, N_("Convert key to lower case") },
120 { "output", 'o', N_("NAME"), 0, N_("Write output to file NAME") },
121 { "quiet", 'q', NULL, 0,
122 N_("Do not print messages while building database") },
123 { "undo", 'u', NULL, 0,
124 N_("Print content of database file, one entry a line") },
125 { "generated", 'g', N_("CHAR"), 0,
126 N_("Generated line not part of iteration") },
127 { NULL, 0, NULL, 0, NULL }
130 /* Short description of program. */
131 static const char doc[] = N_("Create simple database from textual input.");
133 /* Strings for arguments in help texts. */
134 static const char args_doc[] = N_("\
135 INPUT-FILE OUTPUT-FILE\n-o OUTPUT-FILE INPUT-FILE\n-u INPUT-FILE");
137 /* Prototype for option handler. */
138 static error_t parse_opt (int key, char *arg, struct argp_state *state);
140 /* Function to print some extra text in the help message. */
141 static char *more_help (int key, const char *text, void *input);
143 /* Data structure to communicate with argp functions. */
144 static struct argp argp =
146 options, parse_opt, args_doc, doc, NULL, more_help
150 /* List of databases which are not part of the iteration table. */
151 static struct db_option
154 struct db_option *next;
158 /* Prototypes for local functions. */
159 static int process_input (FILE *input, const char *inname,
160 int to_lowercase, int be_quiet);
161 static int print_database (int fd);
162 static void compute_tables (void);
163 static int write_output (int fd);
165 /* SELinux support. */
167 /* Set the SELinux file creation context for the given file. */
168 static void set_file_creation_context (const char *outname, mode_t mode);
169 static void reset_file_creation_context (void);
171 # define set_file_creation_context(_outname,_mode)
172 # define reset_file_creation_context()
176 /* External functions. */
177 #include <programs/xmalloc.h>
181 main (int argc, char *argv[])
183 const char *input_name;
188 /* Set locale via LC_ALL. */
189 setlocale (LC_ALL, "");
191 /* Set the text message domain. */
192 textdomain (_libc_intl_domainname);
194 /* Initialize local variables. */
197 /* Parse and process arguments. */
198 argp_parse (&argp, argc, argv, 0, &remaining, NULL);
200 /* Determine file names. */
201 if (do_undo || output_name != NULL)
203 if (remaining + 1 != argc)
206 error (0, 0, gettext ("wrong number of arguments"));
207 argp_help (&argp, stdout, ARGP_HELP_SEE,
208 program_invocation_short_name);
211 input_name = argv[remaining];
215 if (remaining + 2 != argc)
216 goto wrong_arguments;
218 input_name = argv[remaining++];
219 output_name = argv[remaining];
222 /* Special handling if we are asked to print the database. */
225 int fd = open (input_name, O_RDONLY);
227 error (EXIT_FAILURE, errno, gettext ("cannot open database file `%s'"),
230 int status = print_database (fd);
237 /* Open input file. */
238 if (strcmp (input_name, "-") == 0 || strcmp (input_name, "/dev/stdin") == 0)
244 input_file = fopen64 (input_name, "r");
245 if (input_file == NULL)
246 error (EXIT_FAILURE, errno, gettext ("cannot open input file `%s'"),
249 /* Get the access rights from the source file. The output file should
251 if (fstat64 (fileno (input_file), &st) >= 0)
252 mode = st.st_mode & ACCESSPERMS;
255 /* Start the real work. */
256 int status = process_input (input_file, input_name, to_lowercase, be_quiet);
259 if (input_file != stdin)
262 /* No need to continue when we did not read the file successfully. */
263 if (status != EXIT_SUCCESS)
266 /* Bail out if nothing is to be done. */
272 error (EXIT_SUCCESS, 0, gettext ("no entries to be processed"));
275 /* Compute hash and string tables. */
278 /* Open output file. This must not be standard output so we don't
279 handle "-" and "/dev/stdout" special. */
280 char *tmp_output_name;
281 if (asprintf (&tmp_output_name, "%s.XXXXXX", output_name) == -1)
282 error (EXIT_FAILURE, errno, gettext ("cannot create temporary file name"));
284 set_file_creation_context (output_name, mode);
285 int fd = mkstemp (tmp_output_name);
286 reset_file_creation_context ();
288 error (EXIT_FAILURE, errno, gettext ("cannot create temporary file"));
290 status = write_output (fd);
292 if (status == EXIT_SUCCESS)
296 if (fstat64 (fd, &st) == 0)
298 if ((st.st_mode & ACCESSPERMS) != mode)
299 /* We ignore problems with changing the mode. */
304 error (0, errno, gettext ("cannot stat newly created file"));
305 status = EXIT_FAILURE;
311 if (status == EXIT_SUCCESS)
313 if (rename (tmp_output_name, output_name) != 0)
315 error (0, errno, gettext ("cannot rename temporary file"));
316 status = EXIT_FAILURE;
322 unlink (tmp_output_name);
328 /* Handle program arguments. */
330 parse_opt (int key, char *arg, struct argp_state *state)
332 struct db_option *newp;
349 newp = xmalloc (sizeof (*newp));
351 newp->next = db_options;
355 return ARGP_ERR_UNKNOWN;
362 more_help (int key, const char *text, void *input)
367 case ARGP_KEY_HELP_EXTRA:
368 /* We print some extra information. */
369 if (asprintf (&tp, gettext ("\
370 For bug reporting instructions, please see:\n\
371 %s.\n"), REPORT_BUGS_TO) < 0)
377 return (char *) text;
380 /* Print the version information. */
382 print_version (FILE *stream, struct argp_state *state)
384 fprintf (stream, "makedb %s%s\n", PKGVERSION, VERSION);
385 fprintf (stream, gettext ("\
386 Copyright (C) %s Free Software Foundation, Inc.\n\
387 This is free software; see the source for copying conditions. There is NO\n\
388 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\
390 fprintf (stream, gettext ("Written by %s.\n"), "Ulrich Drepper");
395 dbentry_compare (const void *p1, const void *p2)
397 const struct dbentry *d1 = (const struct dbentry *) p1;
398 const struct dbentry *d2 = (const struct dbentry *) p2;
400 if (d1->hashval != d2->hashval)
401 return d1->hashval < d2->hashval ? -1 : 1;
403 return strcmp (d1->str, d2->str);
408 valstr_compare (const void *p1, const void *p2)
410 const struct valstrentry *d1 = (const struct valstrentry *) p1;
411 const struct valstrentry *d2 = (const struct valstrentry *) p2;
413 return strcmp (d1->str, d2->str);
418 process_input (FILE *input, const char *inname, int to_lowercase, int be_quiet)
427 status = EXIT_SUCCESS;
430 struct database *last_database = NULL;
432 while (!feof_unlocked (input))
434 ssize_t n = getline (&line, &linelen, input);
436 /* This means end of file or some bug. */
439 /* Short read. Probably interrupted system call. */
444 if (line[n - 1] == '\n')
445 /* Remove trailing newline. */
449 while (isspace (*cp))
452 if (*cp == '#' || *cp == '\0')
453 /* First non-space character in line '#': it's a comment.
454 Also go to the next line if it is empty except for whitespaces. */
457 /* Skip over the character indicating the database so that it is not
458 affected by TO_LOWERCASE. */
460 while (*cp != '\0' && !isspace (*cp))
468 /* It's a line without a value field. */
472 size_t keylen = cp - key;
474 while (isspace (*cp))
478 size_t datalen = (&line[n] - cp) + 1;
480 /* Find the database. */
481 if (last_database == NULL || last_database->dbid != key[0])
483 last_database = databases;
484 while (last_database != NULL && last_database->dbid != key[0])
485 last_database = last_database->next;
487 if (last_database == NULL)
489 last_database = xmalloc (sizeof (*last_database));
490 last_database->dbid = key[0];
491 last_database->extra_string = false;
492 last_database->next = databases;
493 last_database->entries = NULL;
494 last_database->nentries = 0;
495 last_database->keystrlen = 0;
496 databases = last_database;
498 struct db_option *runp = db_options;
500 if (runp->dbid == key[0])
502 last_database->extra_string = true;
510 /* Skip the database selector. */
514 /* Store the data. */
515 struct valstrentry *nentry = xmalloc (sizeof (struct valstrentry)
517 if (last_database->extra_string)
518 nentry->idx = extrastrlen;
520 nentry->idx = valstrlen;
521 nentry->extra_string = last_database->extra_string;
522 memcpy (nentry->str, data, datalen);
524 struct valstrentry **fdata = tsearch (nentry, &valstrtree,
527 error (EXIT_FAILURE, errno, gettext ("cannot create search tree"));
529 if (*fdata != nentry)
531 /* We can reuse a string. */
536 if (last_database->extra_string)
537 extrastrlen += datalen;
539 valstrlen += datalen;
542 struct dbentry *newp = xmalloc (sizeof (struct dbentry) + keylen);
543 newp->validx = nentry->idx;
544 newp->hashval = __hash_string (key);
545 memcpy (newp->str, key, keylen);
547 struct dbentry **found = tsearch (newp, &last_database->entries,
550 error (EXIT_FAILURE, errno, gettext ("cannot create search tree"));
556 error_at_line (0, 0, inname, linenr, gettext ("duplicate key"));
560 ++last_database->nentries;
561 last_database->keystrlen += keylen;
566 if (ferror_unlocked (input))
568 error (0, 0, gettext ("problems while reading `%s'"), inname);
569 status = EXIT_FAILURE;
577 copy_valstr (const void *nodep, const VISIT which, const int depth)
579 if (which != leaf && which != postorder)
582 const struct valstrentry *p = *(const struct valstrentry **) nodep;
584 strcpy (valstrtab + (p->extra_string ? valstrlen : 0) + p->idx, p->str);
588 /* Determine if the candidate is prime by using a modified trial division
589 algorithm. The candidate must be both odd and greater than 4. */
591 is_prime (size_t candidate)
594 size_t sq = divn * divn;
596 assert (candidate > 4 && candidate % 2 != 0);
598 while (sq < candidate && candidate % divn != 0)
605 return candidate % divn != 0;
610 next_prime (size_t seed)
612 /* Make sure that we're always greater than 4. */
613 seed = (seed + 4) | 1;
615 while (!is_prime (seed))
623 compute_tables (void)
625 valstrtab = xmalloc (roundup (valstrlen + extrastrlen, sizeof (stridx_t)));
626 while ((valstrlen + extrastrlen) % sizeof (stridx_t) != 0)
627 valstrtab[valstrlen++] = '\0';
628 twalk (valstrtree, copy_valstr);
630 static struct database *db;
631 for (db = databases; db != NULL; db = db->next)
632 if (db->nentries != 0)
636 /* We simply use an odd number large than twice the number of
637 elements to store in the hash table for the size. This gives
638 enough efficiency. */
639 #define TEST_RANGE 30
640 size_t nhashentries_min = next_prime (db->nentries < TEST_RANGE
642 : db->nentries * 2 - TEST_RANGE);
643 size_t nhashentries_max = MAX (nhashentries_min, db->nentries * 4);
644 size_t nhashentries_best = nhashentries_min;
645 size_t chainlength_best = db->nentries;
647 db->hashtable = xmalloc (2 * nhashentries_max * sizeof (stridx_t)
649 db->keyidxtab = db->hashtable + nhashentries_max;
650 db->keystrtab = (char *) (db->keyidxtab + nhashentries_max);
652 static size_t max_chainlength;
654 static size_t nhashentries;
655 static bool copy_string;
657 void add_key(const void *nodep, const VISIT which, const int depth)
659 if (which != leaf && which != postorder)
662 const struct dbentry *dbe = *(const struct dbentry **) nodep;
667 stridx = wp - db->keystrtab;
668 wp = stpcpy (wp, dbe->str) + 1;
673 size_t hidx = dbe->hashval % nhashentries;
674 size_t hval2 = 1 + dbe->hashval % (nhashentries - 2);
675 size_t chainlength = 0;
677 while (db->hashtable[hidx] != ~((stridx_t) 0))
680 if ((hidx += hval2) >= nhashentries)
681 hidx -= nhashentries;
684 db->hashtable[hidx] = ((db->extra_string ? valstrlen : 0)
686 db->keyidxtab[hidx] = stridx;
688 max_chainlength = MAX (max_chainlength, chainlength);
692 nhashentries = nhashentries_min;
693 for (size_t cnt = 0; cnt < TEST_RANGE; ++cnt)
695 memset (db->hashtable, '\xff', nhashentries * sizeof (stridx_t));
700 twalk (db->entries, add_key);
702 if (max_chainlength == 0)
704 /* No need to look further, this is as good as it gets. */
705 nhashentries_best = nhashentries;
709 if (max_chainlength < chainlength_best)
711 chainlength_best = max_chainlength;
712 nhashentries_best = nhashentries;
715 nhashentries = next_prime (nhashentries + 1);
716 if (nhashentries > nhashentries_max)
720 /* Recompute the best table again, this time fill in the strings. */
721 nhashentries = nhashentries_best;
722 memset (db->hashtable, '\xff',
723 2 * nhashentries_max * sizeof (stridx_t));
727 twalk (db->entries, add_key);
729 db->nhashentries = nhashentries_best;
730 nhashentries_total += nhashentries_best;
736 write_output (int fd)
738 struct nss_db_header *header;
739 uint64_t file_offset = (sizeof (struct nss_db_header)
740 + (ndatabases * sizeof (header->dbs[0])));
741 header = alloca (file_offset);
743 header->magic = NSS_DB_MAGIC;
744 header->ndbs = ndatabases;
745 header->valstroffset = file_offset;
746 header->valstrlen = valstrlen;
748 size_t filled_dbs = 0;
749 struct iovec iov[2 + ndatabases * 3];
750 iov[0].iov_base = header;
751 iov[0].iov_len = file_offset;
753 iov[1].iov_base = valstrtab;
754 iov[1].iov_len = valstrlen + extrastrlen;
755 file_offset += iov[1].iov_len;
757 size_t keydataoffset = file_offset + nhashentries_total * sizeof (stridx_t);
758 for (struct database *db = databases; db != NULL; db = db->next)
759 if (db->entries != NULL)
761 assert (file_offset % sizeof (stridx_t) == 0);
762 assert (filled_dbs < ndatabases);
764 header->dbs[filled_dbs].id = db->dbid;
765 memset (header->dbs[filled_dbs].pad, '\0',
766 sizeof (header->dbs[0].pad));
767 header->dbs[filled_dbs].hashsize = db->nhashentries;
769 iov[2 + filled_dbs].iov_base = db->hashtable;
770 iov[2 + filled_dbs].iov_len = db->nhashentries * sizeof (stridx_t);
771 header->dbs[filled_dbs].hashoffset = file_offset;
772 file_offset += iov[2 + filled_dbs].iov_len;
774 iov[2 + ndatabases + filled_dbs * 2].iov_base = db->keyidxtab;
775 iov[2 + ndatabases + filled_dbs * 2].iov_len
776 = db->nhashentries * sizeof (stridx_t);
777 header->dbs[filled_dbs].keyidxoffset = keydataoffset;
778 keydataoffset += iov[2 + ndatabases + filled_dbs * 2].iov_len;
780 iov[3 + ndatabases + filled_dbs * 2].iov_base = db->keystrtab;
781 iov[3 + ndatabases + filled_dbs * 2].iov_len = db->keystrlen;
782 header->dbs[filled_dbs].keystroffset = keydataoffset;
783 keydataoffset += iov[3 + ndatabases + filled_dbs * 2].iov_len;
788 assert (filled_dbs == ndatabases);
789 assert (file_offset == (iov[0].iov_len + iov[1].iov_len
790 + nhashentries_total * sizeof (stridx_t)));
791 header->allocate = file_offset;
793 if (writev (fd, iov, 2 + ndatabases * 3) != keydataoffset)
795 error (0, errno, gettext ("failed to write new database file"));
804 print_database (int fd)
807 if (fstat64 (fd, &st) != 0)
808 error (EXIT_FAILURE, errno, gettext ("cannot stat database file"));
810 const struct nss_db_header *header = mmap (NULL, st.st_size, PROT_READ,
811 MAP_PRIVATE|MAP_POPULATE, fd, 0);
812 if (header == MAP_FAILED)
813 error (EXIT_FAILURE, errno, gettext ("cannot map database file"));
815 if (header->magic != NSS_DB_MAGIC)
816 error (EXIT_FAILURE, 0, gettext ("file not a database file"));
818 const char *valstrtab = (const char *) header + header->valstroffset;
820 for (unsigned int dbidx = 0; dbidx < header->ndbs; ++dbidx)
822 const stridx_t *stridxtab
823 = ((const stridx_t *) ((const char *) header
824 + header->dbs[dbidx].keyidxoffset));
825 const char *keystrtab
826 = (const char *) header + header->dbs[dbidx].keystroffset;
827 const stridx_t *hashtab
828 = (const stridx_t *) ((const char *) header
829 + header->dbs[dbidx].hashoffset);
831 for (uint32_t hidx = 0; hidx < header->dbs[dbidx].hashsize; ++hidx)
832 if (hashtab[hidx] != ~((stridx_t) 0))
834 header->dbs[dbidx].id,
835 keystrtab + stridxtab[hidx],
836 valstrtab + hashtab[hidx]);
845 set_file_creation_context (const char *outname, mode_t mode)
848 static int enforcing;
849 security_context_t ctx;
851 /* Check if SELinux is enabled, and remember. */
853 enabled = is_selinux_enabled () ? 1 : -1;
857 /* Check if SELinux is enforcing, and remember. */
859 enforcing = security_getenforce () ? 1 : -1;
861 /* Determine the context which the file should have. */
863 if (matchpathcon (outname, S_IFREG | mode, &ctx) == 0 && ctx != NULL)
865 if (setfscreatecon (ctx) != 0)
866 error (enforcing > 0 ? EXIT_FAILURE : 0, 0,
867 gettext ("cannot set file creation context for `%s'"),
875 reset_file_creation_context (void)
877 setfscreatecon (NULL);