1 /* Create simple DB database from textual input.
2 Copyright (C) 1996-2012 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 <http://www.gnu.org/licenses/>. */
35 #include <sys/param.h>
38 #include "nss_db/nss_db.h"
40 /* Get libc version number. */
41 #include "../version.h"
43 /* The hashing function we use. */
44 #include "../intl/hash-string.h"
46 /* SELinux support. */
48 # include <selinux/selinux.h>
52 # define MAP_POPULATE 0
55 #define PACKAGE _libc_intl_domainname
57 /* List of data bases. */
62 struct database *next;
71 static size_t ndatabases;
72 static size_t nhashentries_total;
73 static size_t valstrlen;
74 static void *valstrtree;
75 static char *valstrtab;
76 static size_t extrastrlen;
86 /* Stored string entry. */
95 /* True if any entry has been added. */
96 static bool any_dbentry;
98 /* If non-zero convert key to lower case. */
99 static int to_lowercase;
101 /* If non-zero print content of input file, one entry per line. */
104 /* If non-zero do not print informational messages. */
107 /* Name of output file. */
108 static const char *output_name;
110 /* Name and version of program. */
111 static void print_version (FILE *stream, struct argp_state *state);
112 void (*argp_program_version_hook) (FILE *, struct argp_state *) = print_version;
114 /* Definitions of arguments for argp functions. */
115 static const struct argp_option options[] =
117 { "fold-case", 'f', NULL, 0, N_("Convert key to lower case") },
118 { "output", 'o', N_("NAME"), 0, N_("Write output to file NAME") },
119 { "quiet", 'q', NULL, 0,
120 N_("Do not print messages while building database") },
121 { "undo", 'u', NULL, 0,
122 N_("Print content of database file, one entry a line") },
123 { "generated", 'g', N_("CHAR"), 0,
124 N_("Generated line not part of iteration") },
125 { NULL, 0, NULL, 0, NULL }
128 /* Short description of program. */
129 static const char doc[] = N_("Create simple database from textual input.");
131 /* Strings for arguments in help texts. */
132 static const char args_doc[] = N_("\
133 INPUT-FILE OUTPUT-FILE\n-o OUTPUT-FILE INPUT-FILE\n-u INPUT-FILE");
135 /* Prototype for option handler. */
136 static error_t parse_opt (int key, char *arg, struct argp_state *state);
138 /* Function to print some extra text in the help message. */
139 static char *more_help (int key, const char *text, void *input);
141 /* Data structure to communicate with argp functions. */
142 static struct argp argp =
144 options, parse_opt, args_doc, doc, NULL, more_help
148 /* List of databases which are not part of the iteration table. */
149 static struct db_option
152 struct db_option *next;
156 /* Prototypes for local functions. */
157 static int process_input (FILE *input, const char *inname,
158 int to_lowercase, int be_quiet);
159 static int print_database (int fd);
160 static void compute_tables (void);
161 static int write_output (int fd);
163 /* SELinux support. */
165 /* Set the SELinux file creation context for the given file. */
166 static void set_file_creation_context (const char *outname, mode_t mode);
167 static void reset_file_creation_context (void);
169 # define set_file_creation_context(_outname,_mode)
170 # define reset_file_creation_context()
174 /* External functions. */
175 extern void *xmalloc (size_t n)
176 __attribute_malloc__ __attribute_alloc_size (1);
177 extern void *xcalloc (size_t n, size_t s)
178 __attribute_malloc__ __attribute_alloc_size (1, 2);
182 main (int argc, char *argv[])
184 const char *input_name;
189 /* Set locale via LC_ALL. */
190 setlocale (LC_ALL, "");
192 /* Set the text message domain. */
193 textdomain (_libc_intl_domainname);
195 /* Initialize local variables. */
198 /* Parse and process arguments. */
199 argp_parse (&argp, argc, argv, 0, &remaining, NULL);
201 /* Determine file names. */
202 if (do_undo || output_name != NULL)
204 if (remaining + 1 != argc)
207 error (0, 0, gettext ("wrong number of arguments"));
208 argp_help (&argp, stdout, ARGP_HELP_SEE,
209 program_invocation_short_name);
212 input_name = argv[remaining];
216 if (remaining + 2 != argc)
217 goto wrong_arguments;
219 input_name = argv[remaining++];
220 output_name = argv[remaining];
223 /* Special handling if we are asked to print the database. */
226 int fd = open (input_name, O_RDONLY);
228 error (EXIT_FAILURE, errno, gettext ("cannot open database file `%s'"),
231 int status = print_database (fd);
238 /* Open input file. */
239 if (strcmp (input_name, "-") == 0 || strcmp (input_name, "/dev/stdin") == 0)
245 input_file = fopen64 (input_name, "r");
246 if (input_file == NULL)
247 error (EXIT_FAILURE, errno, gettext ("cannot open input file `%s'"),
250 /* Get the access rights from the source file. The output file should
252 if (fstat64 (fileno (input_file), &st) >= 0)
253 mode = st.st_mode & ACCESSPERMS;
256 /* Start the real work. */
257 int status = process_input (input_file, input_name, to_lowercase, be_quiet);
260 if (input_file != stdin)
263 /* No need to continue when we did not read the file successfully. */
264 if (status != EXIT_SUCCESS)
267 /* Bail out if nothing is to be done. */
273 error (EXIT_SUCCESS, 0, gettext ("no entries to be processed"));
276 /* Compute hash and string tables. */
279 /* Open output file. This must not be standard output so we don't
280 handle "-" and "/dev/stdout" special. */
281 char *tmp_output_name;
282 if (asprintf (&tmp_output_name, "%s.XXXXXX", output_name) == -1)
283 error (EXIT_FAILURE, errno, gettext ("cannot create temporary file name"));
285 set_file_creation_context (output_name, mode);
286 int fd = mkstemp (tmp_output_name);
287 reset_file_creation_context ();
289 error (EXIT_FAILURE, errno, gettext ("cannot create temporary file"));
291 status = write_output (fd);
293 if (status == EXIT_SUCCESS)
297 if (fstat64 (fd, &st) == 0)
299 if ((st.st_mode & ACCESSPERMS) != mode)
300 /* We ignore problems with changing the mode. */
305 error (0, errno, gettext ("cannot stat newly created file"));
306 status = EXIT_FAILURE;
312 if (status == EXIT_SUCCESS)
314 if (rename (tmp_output_name, output_name) != 0)
316 error (0, errno, gettext ("cannot rename temporary file"));
317 status = EXIT_FAILURE;
323 unlink (tmp_output_name);
329 /* Handle program arguments. */
331 parse_opt (int key, char *arg, struct argp_state *state)
333 struct db_option *newp;
350 newp = xmalloc (sizeof (*newp));
352 newp->next = db_options;
356 return ARGP_ERR_UNKNOWN;
363 more_help (int key, const char *text, void *input)
367 case ARGP_KEY_HELP_EXTRA:
368 /* We print some extra information. */
369 return strdup (gettext ("\
370 For bug reporting instructions, please see:\n\
371 <http://www.gnu.org/software/libc/bugs.html>.\n"));
375 return (char *) text;
378 /* Print the version information. */
380 print_version (FILE *stream, struct argp_state *state)
382 fprintf (stream, "makedb (GNU %s) %s\n", PACKAGE, VERSION);
383 fprintf (stream, gettext ("\
384 Copyright (C) %s Free Software Foundation, Inc.\n\
385 This is free software; see the source for copying conditions. There is NO\n\
386 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\
388 fprintf (stream, gettext ("Written by %s.\n"), "Ulrich Drepper");
393 dbentry_compare (const void *p1, const void *p2)
395 const struct dbentry *d1 = (const struct dbentry *) p1;
396 const struct dbentry *d2 = (const struct dbentry *) p2;
398 if (d1->hashval != d2->hashval)
399 return d1->hashval < d2->hashval ? -1 : 1;
401 return strcmp (d1->str, d2->str);
406 valstr_compare (const void *p1, const void *p2)
408 const struct valstrentry *d1 = (const struct valstrentry *) p1;
409 const struct valstrentry *d2 = (const struct valstrentry *) p2;
411 return strcmp (d1->str, d2->str);
416 process_input (input, inname, to_lowercase, be_quiet)
429 status = EXIT_SUCCESS;
432 struct database *last_database = NULL;
434 while (!feof_unlocked (input))
436 ssize_t n = getline (&line, &linelen, input);
438 /* This means end of file or some bug. */
441 /* Short read. Probably interrupted system call. */
446 if (line[n - 1] == '\n')
447 /* Remove trailing newline. */
451 while (isspace (*cp))
454 if (*cp == '#' || *cp == '\0')
455 /* First non-space character in line '#': it's a comment.
456 Also go to the next line if it is empty except for whitespaces. */
459 /* Skip over the character indicating the database so that it is not
460 affected by TO_LOWERCASE. */
462 while (*cp != '\0' && !isspace (*cp))
470 /* It's a line without a value field. */
474 size_t keylen = cp - key;
476 while (isspace (*cp))
480 size_t datalen = (&line[n] - cp) + 1;
482 /* Find the database. */
483 if (last_database == NULL || last_database->dbid != key[0])
485 last_database = databases;
486 while (last_database != NULL && last_database->dbid != key[0])
487 last_database = last_database->next;
489 if (last_database == NULL)
491 last_database = xmalloc (sizeof (*last_database));
492 last_database->dbid = key[0];
493 last_database->extra_string = false;
494 last_database->next = databases;
495 last_database->entries = NULL;
496 last_database->nentries = 0;
497 last_database->keystrlen = 0;
498 databases = last_database;
500 struct db_option *runp = db_options;
502 if (runp->dbid == key[0])
504 last_database->extra_string = true;
512 /* Skip the database selector. */
516 /* Store the data. */
517 struct valstrentry *nentry = xmalloc (sizeof (struct valstrentry)
519 if (last_database->extra_string)
520 nentry->idx = extrastrlen;
522 nentry->idx = valstrlen;
523 nentry->extra_string = last_database->extra_string;
524 memcpy (nentry->str, data, datalen);
526 struct valstrentry **fdata = tsearch (nentry, &valstrtree,
529 error (EXIT_FAILURE, errno, gettext ("cannot create search tree"));
531 if (*fdata != nentry)
533 /* We can reuse a string. */
538 if (last_database->extra_string)
539 extrastrlen += datalen;
541 valstrlen += datalen;
544 struct dbentry *newp = xmalloc (sizeof (struct dbentry) + keylen);
545 newp->validx = nentry->idx;
546 newp->hashval = __hash_string (key);
547 memcpy (newp->str, key, keylen);
549 struct dbentry **found = tsearch (newp, &last_database->entries,
552 error (EXIT_FAILURE, errno, gettext ("cannot create search tree"));
558 error_at_line (0, 0, inname, linenr, gettext ("duplicate key"));
562 ++last_database->nentries;
563 last_database->keystrlen += keylen;
568 if (ferror_unlocked (input))
570 error (0, 0, gettext ("problems while reading `%s'"), inname);
571 status = EXIT_FAILURE;
579 copy_valstr (const void *nodep, const VISIT which, const int depth)
581 if (which != leaf && which != postorder)
584 const struct valstrentry *p = *(const struct valstrentry **) nodep;
586 strcpy (valstrtab + (p->extra_string ? valstrlen : 0) + p->idx, p->str);
591 is_prime (size_t candidate)
593 /* No even number and none less than 10 will be passed here. */
595 size_t sq = divn * divn;
597 while (sq < candidate && candidate % divn != 0)
604 return candidate % divn != 0;
609 next_prime (size_t seed)
611 /* Make it definitely odd. */
614 while (!is_prime (seed))
622 compute_tables (void)
624 valstrtab = xmalloc (roundup (valstrlen + extrastrlen, sizeof (stridx_t)));
625 while ((valstrlen + extrastrlen) % sizeof (stridx_t) != 0)
626 valstrtab[valstrlen++] = '\0';
627 twalk (valstrtree, copy_valstr);
629 static struct database *db;
630 for (db = databases; db != NULL; db = db->next)
631 if (db->nentries != 0)
635 /* We simply use an odd number large than twice the number of
636 elements to store in the hash table for the size. This gives
637 enough efficiency. */
638 #define TEST_RANGE 30
639 size_t nhashentries_min = next_prime (db->nentries < TEST_RANGE
641 : db->nentries * 2 - TEST_RANGE);
642 size_t nhashentries_max = MAX (nhashentries_min, db->nentries * 4);
643 size_t nhashentries_best = nhashentries_min;
644 size_t chainlength_best = db->nentries;
646 db->hashtable = xmalloc (2 * nhashentries_max * sizeof (stridx_t)
648 db->keyidxtab = db->hashtable + nhashentries_max;
649 db->keystrtab = (char *) (db->keyidxtab + nhashentries_max);
651 static size_t max_chainlength;
653 static size_t nhashentries;
654 static bool copy_string;
656 void add_key(const void *nodep, const VISIT which, const int depth)
658 if (which != leaf && which != postorder)
661 const struct dbentry *dbe = *(const struct dbentry **) nodep;
666 stridx = wp - db->keystrtab;
667 wp = stpcpy (wp, dbe->str) + 1;
672 size_t hidx = dbe->hashval % nhashentries;
673 size_t hval2 = 1 + dbe->hashval % (nhashentries - 2);
674 size_t chainlength = 0;
676 while (db->hashtable[hidx] != ~((stridx_t) 0))
679 if ((hidx += hval2) >= nhashentries)
680 hidx -= nhashentries;
683 db->hashtable[hidx] = ((db->extra_string ? valstrlen : 0)
685 db->keyidxtab[hidx] = stridx;
687 max_chainlength = MAX (max_chainlength, chainlength);
691 nhashentries = nhashentries_min;
692 for (size_t cnt = 0; cnt < TEST_RANGE; ++cnt)
694 memset (db->hashtable, '\xff', nhashentries * sizeof (stridx_t));
699 twalk (db->entries, add_key);
701 if (max_chainlength == 0)
703 /* No need to look further, this is as good as it gets. */
704 nhashentries_best = nhashentries;
708 if (max_chainlength < chainlength_best)
710 chainlength_best = max_chainlength;
711 nhashentries_best = nhashentries;
714 nhashentries = next_prime (nhashentries + 1);
715 if (nhashentries > nhashentries_max)
719 /* Recompute the best table again, this time fill in the strings. */
720 nhashentries = nhashentries_best;
721 memset (db->hashtable, '\xff',
722 2 * nhashentries_max * sizeof (stridx_t));
726 twalk (db->entries, add_key);
728 db->nhashentries = nhashentries_best;
729 nhashentries_total += nhashentries_best;
735 write_output (int fd)
737 struct nss_db_header *header;
738 uint64_t file_offset = (sizeof (struct nss_db_header)
739 + (ndatabases * sizeof (header->dbs[0])));
740 header = alloca (file_offset);
742 header->magic = NSS_DB_MAGIC;
743 header->ndbs = ndatabases;
744 header->valstroffset = file_offset;
745 header->valstrlen = valstrlen;
747 size_t filled_dbs = 0;
748 struct iovec iov[2 + ndatabases * 3];
749 iov[0].iov_base = header;
750 iov[0].iov_len = file_offset;
752 iov[1].iov_base = valstrtab;
753 iov[1].iov_len = valstrlen + extrastrlen;
754 file_offset += iov[1].iov_len;
756 size_t keydataoffset = file_offset + nhashentries_total * sizeof (stridx_t);
757 for (struct database *db = databases; db != NULL; db = db->next)
758 if (db->entries != NULL)
760 assert (file_offset % sizeof (stridx_t) == 0);
761 assert (filled_dbs < ndatabases);
763 header->dbs[filled_dbs].id = db->dbid;
764 memset (header->dbs[filled_dbs].pad, '\0',
765 sizeof (header->dbs[0].pad));
766 header->dbs[filled_dbs].hashsize = db->nhashentries;
768 iov[2 + filled_dbs].iov_base = db->hashtable;
769 iov[2 + filled_dbs].iov_len = db->nhashentries * sizeof (stridx_t);
770 header->dbs[filled_dbs].hashoffset = file_offset;
771 file_offset += iov[2 + filled_dbs].iov_len;
773 iov[2 + ndatabases + filled_dbs * 2].iov_base = db->keyidxtab;
774 iov[2 + ndatabases + filled_dbs * 2].iov_len
775 = db->nhashentries * sizeof (stridx_t);
776 header->dbs[filled_dbs].keyidxoffset = keydataoffset;
777 keydataoffset += iov[2 + ndatabases + filled_dbs * 2].iov_len;
779 iov[3 + ndatabases + filled_dbs * 2].iov_base = db->keystrtab;
780 iov[3 + ndatabases + filled_dbs * 2].iov_len = db->keystrlen;
781 header->dbs[filled_dbs].keystroffset = keydataoffset;
782 keydataoffset += iov[3 + ndatabases + filled_dbs * 2].iov_len;
787 assert (filled_dbs == ndatabases);
788 assert (file_offset == (iov[0].iov_len + iov[1].iov_len
789 + nhashentries_total * sizeof (stridx_t)));
790 header->allocate = file_offset;
792 if (writev (fd, iov, 2 + ndatabases * 3) != keydataoffset)
794 error (0, errno, gettext ("failed to write new database file"));
803 print_database (int fd)
806 if (fstat64 (fd, &st) != 0)
807 error (EXIT_FAILURE, errno, gettext ("cannot stat database file"));
809 const struct nss_db_header *header = mmap (NULL, st.st_size, PROT_READ,
810 MAP_PRIVATE|MAP_POPULATE, fd, 0);
811 if (header == MAP_FAILED)
812 error (EXIT_FAILURE, errno, gettext ("cannot map database file"));
814 if (header->magic != NSS_DB_MAGIC)
815 error (EXIT_FAILURE, 0, gettext ("file not a database file"));
817 const char *valstrtab = (const char *) header + header->valstroffset;
819 for (unsigned int dbidx = 0; dbidx < header->ndbs; ++dbidx)
821 const stridx_t *stridxtab
822 = ((const stridx_t *) ((const char *) header
823 + header->dbs[dbidx].keyidxoffset));
824 const char *keystrtab
825 = (const char *) header + header->dbs[dbidx].keystroffset;
826 const stridx_t *hashtab
827 = (const stridx_t *) ((const char *) header
828 + header->dbs[dbidx].hashoffset);
830 for (uint32_t hidx = 0; hidx < header->dbs[dbidx].hashsize; ++hidx)
831 if (hashtab[hidx] != ~((stridx_t) 0))
833 header->dbs[dbidx].id,
834 keystrtab + stridxtab[hidx],
835 valstrtab + hashtab[hidx]);
844 set_file_creation_context (const char *outname, mode_t mode)
847 static int enforcing;
848 security_context_t ctx;
850 /* Check if SELinux is enabled, and remember. */
852 enabled = is_selinux_enabled () ? 1 : -1;
856 /* Check if SELinux is enforcing, and remember. */
858 enforcing = security_getenforce () ? 1 : -1;
860 /* Determine the context which the file should have. */
862 if (matchpathcon (outname, S_IFREG | mode, &ctx) == 0 && ctx != NULL)
864 if (setfscreatecon (ctx) != 0)
865 error (enforcing > 0 ? EXIT_FAILURE : 0, 0,
866 gettext ("cannot set file creation context for `%s'"),
874 reset_file_creation_context (void)
876 setfscreatecon (NULL);