1 /* Create simple DB database from textual input.
2 Copyright (C) 1996-2000, 2011 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, write to the Free
18 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
37 #include "nss_db/nss_db.h"
39 /* Get libc version number. */
40 #include "../version.h"
42 /* The hashing function we use. */
43 #include "../intl/hash-string.h"
45 /* SELinux support. */
47 # include <selinux/selinux.h>
50 #define PACKAGE _libc_intl_domainname
52 /* List of data bases. */
57 struct database *next;
66 static size_t ndatabases;
67 static size_t nhashentries_total;
68 static size_t valstrlen;
69 static void *valstrtree;
70 static char *valstrtab;
71 static size_t extrastrlen;
81 /* Stored string entry. */
90 /* True if any entry has been added. */
91 static bool any_dbentry;
93 /* If non-zero convert key to lower case. */
94 static int to_lowercase;
96 /* If non-zero print content of input file, one entry per line. */
99 /* If non-zero do not print informational messages. */
102 /* Name of output file. */
103 static const char *output_name;
105 /* Name and version of program. */
106 static void print_version (FILE *stream, struct argp_state *state);
107 void (*argp_program_version_hook) (FILE *, struct argp_state *) = print_version;
109 /* Definitions of arguments for argp functions. */
110 static const struct argp_option options[] =
112 { "fold-case", 'f', NULL, 0, N_("Convert key to lower case") },
113 { "output", 'o', N_("NAME"), 0, N_("Write output to file NAME") },
114 { "quiet", 'q', NULL, 0,
115 N_("Do not print messages while building database") },
116 { "undo", 'u', NULL, 0,
117 N_("Print content of database file, one entry a line") },
118 { "generated", 'g', N_("CHAR"), 0,
119 N_("Generated line not part of iteration") },
120 { NULL, 0, NULL, 0, NULL }
123 /* Short description of program. */
124 static const char doc[] = N_("Create simple database from textual input.");
126 /* Strings for arguments in help texts. */
127 static const char args_doc[] = N_("\
128 INPUT-FILE OUTPUT-FILE\n-o OUTPUT-FILE INPUT-FILE\n-u INPUT-FILE");
130 /* Prototype for option handler. */
131 static error_t parse_opt (int key, char *arg, struct argp_state *state);
133 /* Function to print some extra text in the help message. */
134 static char *more_help (int key, const char *text, void *input);
136 /* Data structure to communicate with argp functions. */
137 static struct argp argp =
139 options, parse_opt, args_doc, doc, NULL, more_help
143 /* List of databases which are not part of the iteration table. */
144 static struct db_option
147 struct db_option *next;
151 /* Prototypes for local functions. */
152 static int process_input (FILE *input, const char *inname,
153 int to_lowercase, int be_quiet);
154 static int print_database (int fd);
155 static void compute_tables (void);
156 static int write_output (int fd);
158 /* SELinux support. */
160 /* Set the SELinux file creation context for the given file. */
161 static void set_file_creation_context (const char *outname, mode_t mode);
162 static void reset_file_creation_context (void);
164 # define set_file_creation_context(_outname,_mode)
165 # define reset_file_creation_context()
169 /* External functions. */
170 extern void *xmalloc (size_t n) __attribute_malloc__;
171 extern void *xcalloc (size_t n, size_t m) __attribute_malloc__;
175 main (int argc, char *argv[])
177 const char *input_name;
182 /* Set locale via LC_ALL. */
183 setlocale (LC_ALL, "");
185 /* Set the text message domain. */
186 textdomain (_libc_intl_domainname);
188 /* Initialize local variables. */
191 /* Parse and process arguments. */
192 argp_parse (&argp, argc, argv, 0, &remaining, NULL);
194 /* Determine file names. */
195 if (do_undo || output_name != NULL)
197 if (remaining + 1 != argc)
200 error (0, 0, gettext ("wrong number of arguments"));
201 argp_help (&argp, stdout, ARGP_HELP_SEE,
202 program_invocation_short_name);
205 input_name = argv[remaining];
209 if (remaining + 2 != argc)
210 goto wrong_arguments;
212 input_name = argv[remaining++];
213 output_name = argv[remaining];
216 /* Special handling if we are asked to print the database. */
219 int fd = open (input_name, O_RDONLY);
221 error (EXIT_FAILURE, errno, gettext ("cannot open database file `%s'"),
224 int status = print_database (fd);
231 /* Open input file. */
232 if (strcmp (input_name, "-") == 0 || strcmp (input_name, "/dev/stdin") == 0)
238 input_file = fopen64 (input_name, "r");
239 if (input_file == NULL)
240 error (EXIT_FAILURE, errno, gettext ("cannot open input file `%s'"),
243 /* Get the access rights from the source file. The output file should
245 if (fstat64 (fileno (input_file), &st) >= 0)
246 mode = st.st_mode & ACCESSPERMS;
249 /* Start the real work. */
250 int status = process_input (input_file, input_name, to_lowercase, be_quiet);
253 if (input_file != stdin)
256 /* No need to continue when we did not read the file successfully. */
257 if (status != EXIT_SUCCESS)
260 /* Bail out if nothing is to be done. */
266 error (EXIT_SUCCESS, 0, gettext ("no entries to be processed"));
269 /* Compute hash and string tables. */
272 /* Open output file. This must not be standard output so we don't
273 handle "-" and "/dev/stdout" special. */
274 char *tmp_output_name;
275 if (asprintf (&tmp_output_name, "%s.XXXXXX", output_name) == -1)
276 error (EXIT_FAILURE, errno, gettext ("cannot create temporary file name"));
278 set_file_creation_context (output_name, mode);
279 int fd = mkstemp (tmp_output_name);
280 reset_file_creation_context ();
282 error (EXIT_FAILURE, errno, gettext ("cannot create temporary file"));
284 status = write_output (fd);
286 if (status == EXIT_SUCCESS)
290 if (fstat64 (fd, &st) == 0)
292 if ((st.st_mode & ACCESSPERMS) != mode)
293 /* We ignore problems with changing the mode. */
298 error (0, errno, gettext ("cannot stat newly created file"));
299 status = EXIT_FAILURE;
305 if (status == EXIT_SUCCESS)
307 if (rename (tmp_output_name, output_name) != 0)
309 error (0, errno, gettext ("cannot rename temporary file"));
310 status = EXIT_FAILURE;
316 unlink (tmp_output_name);
322 /* Handle program arguments. */
324 parse_opt (int key, char *arg, struct argp_state *state)
326 struct db_option *newp;
343 newp = xmalloc (sizeof (*newp));
345 newp->next = db_options;
349 return ARGP_ERR_UNKNOWN;
356 more_help (int key, const char *text, void *input)
360 case ARGP_KEY_HELP_EXTRA:
361 /* We print some extra information. */
362 return strdup (gettext ("\
363 For bug reporting instructions, please see:\n\
364 <http://www.gnu.org/software/libc/bugs.html>.\n"));
368 return (char *) text;
371 /* Print the version information. */
373 print_version (FILE *stream, struct argp_state *state)
375 fprintf (stream, "makedb (GNU %s) %s\n", PACKAGE, VERSION);
376 fprintf (stream, gettext ("\
377 Copyright (C) %s Free Software Foundation, Inc.\n\
378 This is free software; see the source for copying conditions. There is NO\n\
379 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\
381 fprintf (stream, gettext ("Written by %s.\n"), "Ulrich Drepper");
386 dbentry_compare (const void *p1, const void *p2)
388 const struct dbentry *d1 = (const struct dbentry *) p1;
389 const struct dbentry *d2 = (const struct dbentry *) p2;
391 if (d1->hashval != d2->hashval)
392 return d1->hashval < d2->hashval ? -1 : 1;
394 return strcmp (d1->str, d2->str);
399 valstr_compare (const void *p1, const void *p2)
401 const struct valstrentry *d1 = (const struct valstrentry *) p1;
402 const struct valstrentry *d2 = (const struct valstrentry *) p2;
404 return strcmp (d1->str, d2->str);
409 process_input (input, inname, to_lowercase, be_quiet)
422 status = EXIT_SUCCESS;
425 struct database *last_database = NULL;
427 while (!feof_unlocked (input))
429 ssize_t n = getline (&line, &linelen, input);
431 /* This means end of file or some bug. */
434 /* Short read. Probably interrupted system call. */
439 if (line[n - 1] == '\n')
440 /* Remove trailing newline. */
444 while (isspace (*cp))
447 if (*cp == '#' || *cp == '\0')
448 /* First non-space character in line '#': it's a comment.
449 Also go to the next line if it is empty except for whitespaces. */
452 /* Skip over the character indicating the database so that it is not
453 affected by TO_LOWERCASE. */
455 while (*cp != '\0' && !isspace (*cp))
463 /* It's a line without a value field. */
467 size_t keylen = cp - key;
469 while (isspace (*cp))
473 size_t datalen = (&line[n] - cp) + 1;
475 /* Find the database. */
476 if (last_database == NULL || last_database->dbid != key[0])
478 last_database = databases;
479 while (last_database != NULL && last_database->dbid != key[0])
480 last_database = last_database->next;
482 if (last_database == NULL)
484 last_database = xmalloc (sizeof (*last_database));
485 last_database->dbid = key[0];
486 last_database->extra_string = false;
487 last_database->next = databases;
488 last_database->entries = NULL;
489 last_database->nentries = 0;
490 last_database->keystrlen = 0;
491 databases = last_database;
493 struct db_option *runp = db_options;
495 if (runp->dbid == key[0])
497 last_database->extra_string = true;
505 /* Skip the database selector. */
509 /* Store the data. */
510 struct valstrentry *nentry = xmalloc (sizeof (struct valstrentry)
512 if (last_database->extra_string)
513 nentry->idx = extrastrlen;
515 nentry->idx = valstrlen;
516 nentry->extra_string = last_database->extra_string;
517 memcpy (nentry->str, data, datalen);
519 struct valstrentry **fdata = tsearch (nentry, &valstrtree,
522 error (EXIT_FAILURE, errno, gettext ("cannot create search tree"));
524 if (*fdata != nentry)
526 /* We can reuse a string. */
531 if (last_database->extra_string)
532 extrastrlen += datalen;
534 valstrlen += datalen;
537 struct dbentry *newp = xmalloc (sizeof (struct dbentry) + keylen);
538 newp->validx = nentry->idx;
539 newp->hashval = __hash_string (key);
540 memcpy (newp->str, key, keylen);
542 struct dbentry **found = tsearch (newp, &last_database->entries,
545 error (EXIT_FAILURE, errno, gettext ("cannot create search tree"));
551 error_at_line (0, 0, inname, linenr, gettext ("duplicate key"));
555 ++last_database->nentries;
556 last_database->keystrlen += keylen;
561 if (ferror_unlocked (input))
563 error (0, 0, gettext ("problems while reading `%s'"), inname);
564 status = EXIT_FAILURE;
572 copy_valstr (const void *nodep, const VISIT which, const int depth)
574 if (which != leaf && which != postorder)
577 const struct valstrentry *p = *(const struct valstrentry **) nodep;
579 strcpy (valstrtab + (p->extra_string ? valstrlen : 0) + p->idx, p->str);
584 is_prime (size_t candidate)
586 /* No even number and none less than 10 will be passed here. */
588 size_t sq = divn * divn;
590 while (sq < candidate && candidate % divn != 0)
597 return candidate % divn != 0;
602 next_prime (size_t seed)
604 /* Make it definitely odd. */
607 while (!is_prime (seed))
615 compute_tables (void)
617 valstrtab = xmalloc (roundup (valstrlen + extrastrlen, sizeof (stridx_t)));
618 while ((valstrlen + extrastrlen) % sizeof (stridx_t) != 0)
619 valstrtab[valstrlen++] = '\0';
620 twalk (valstrtree, copy_valstr);
622 for (struct database *db = databases; db != NULL; db = db->next)
623 if (db->nentries != 0)
627 /* We simply use an odd number large than twice the number of
628 elements to store in the hash table for the size. This gives
629 enough efficiency. */
630 #define TEST_RANGE 30
631 size_t nhashentries_min = next_prime (db->nentries < TEST_RANGE
633 : db->nentries * 2 - TEST_RANGE);
634 size_t nhashentries_max = MAX (nhashentries_min, db->nentries * 4);
635 size_t nhashentries_best = nhashentries_min;
636 size_t chainlength_best = db->nentries;
638 db->hashtable = xmalloc (2 * nhashentries_max * sizeof (stridx_t)
640 db->keyidxtab = db->hashtable + nhashentries_max;
641 db->keystrtab = (char *) (db->keyidxtab + nhashentries_max);
643 size_t max_chainlength;
646 bool copy_string = false;
648 void add_key(const void *nodep, const VISIT which, const int depth)
650 if (which != leaf && which != postorder)
653 const struct dbentry *dbe = *(const struct dbentry **) nodep;
658 stridx = wp - db->keystrtab;
659 wp = stpcpy (wp, dbe->str) + 1;
664 size_t hidx = dbe->hashval % nhashentries;
665 size_t hval2 = 1 + dbe->hashval % (nhashentries - 2);
666 size_t chainlength = 0;
668 while (db->hashtable[hidx] != ~((stridx_t) 0))
671 if ((hidx += hval2) >= nhashentries)
672 hidx -= nhashentries;
675 db->hashtable[hidx] = ((db->extra_string ? valstrlen : 0)
677 db->keyidxtab[hidx] = stridx;
679 max_chainlength = MAX (max_chainlength, chainlength);
682 nhashentries = nhashentries_min;
683 for (size_t cnt = 0; cnt < TEST_RANGE; ++cnt)
685 memset (db->hashtable, '\xff', nhashentries * sizeof (stridx_t));
690 twalk (db->entries, add_key);
692 if (max_chainlength == 0)
694 /* No need to look further, this is as good as it gets. */
695 nhashentries_best = nhashentries;
699 if (max_chainlength < chainlength_best)
701 chainlength_best = max_chainlength;
702 nhashentries_best = nhashentries;
705 nhashentries = next_prime (nhashentries + 1);
706 if (nhashentries > nhashentries_max)
710 /* Recompute the best table again, this time fill in the strings. */
711 nhashentries = nhashentries_best;
712 memset (db->hashtable, '\xff',
713 2 * nhashentries_max * sizeof (stridx_t));
717 twalk (db->entries, add_key);
719 db->nhashentries = nhashentries_best;
720 nhashentries_total += nhashentries_best;
726 write_output (int fd)
728 struct nss_db_header *header;
729 uint64_t file_offset = (sizeof (struct nss_db_header)
730 + (ndatabases * sizeof (header->dbs[0])));
731 header = alloca (file_offset);
733 header->magic = NSS_DB_MAGIC;
734 header->ndbs = ndatabases;
735 header->valstroffset = file_offset;
736 header->valstrlen = valstrlen;
738 size_t filled_dbs = 0;
739 struct iovec iov[2 + ndatabases * 3];
740 iov[0].iov_base = header;
741 iov[0].iov_len = file_offset;
743 iov[1].iov_base = valstrtab;
744 iov[1].iov_len = valstrlen + extrastrlen;
745 file_offset += iov[1].iov_len;
747 size_t keydataoffset = file_offset + nhashentries_total * sizeof (stridx_t);
748 for (struct database *db = databases; db != NULL; db = db->next)
749 if (db->entries != NULL)
751 assert (file_offset % sizeof (stridx_t) == 0);
752 assert (filled_dbs < ndatabases);
754 header->dbs[filled_dbs].id = db->dbid;
755 memset (header->dbs[filled_dbs].pad, '\0',
756 sizeof (header->dbs[0].pad));
757 header->dbs[filled_dbs].hashsize = db->nhashentries;
759 iov[2 + filled_dbs].iov_base = db->hashtable;
760 iov[2 + filled_dbs].iov_len = db->nhashentries * sizeof (stridx_t);
761 header->dbs[filled_dbs].hashoffset = file_offset;
762 file_offset += iov[2 + filled_dbs].iov_len;
764 iov[2 + ndatabases + filled_dbs * 2].iov_base = db->keyidxtab;
765 iov[2 + ndatabases + filled_dbs * 2].iov_len
766 = db->nhashentries * sizeof (stridx_t);
767 header->dbs[filled_dbs].keyidxoffset = keydataoffset;
768 keydataoffset += iov[2 + ndatabases + filled_dbs * 2].iov_len;
770 iov[3 + ndatabases + filled_dbs * 2].iov_base = db->keystrtab;
771 iov[3 + ndatabases + filled_dbs * 2].iov_len = db->keystrlen;
772 header->dbs[filled_dbs].keystroffset = keydataoffset;
773 keydataoffset += iov[3 + ndatabases + filled_dbs * 2].iov_len;
778 assert (filled_dbs == ndatabases);
779 assert (file_offset == (iov[0].iov_len + iov[1].iov_len
780 + nhashentries_total * sizeof (stridx_t)));
781 header->allocate = file_offset;
783 if (writev (fd, iov, 2 + ndatabases * 3) != keydataoffset)
785 error (0, errno, gettext ("failed to write new database file"));
794 print_database (int fd)
797 if (fstat64 (fd, &st) != 0)
798 error (EXIT_FAILURE, errno, gettext ("cannot stat database file"));
800 const struct nss_db_header *header = mmap (NULL, st.st_size, PROT_READ,
801 MAP_PRIVATE|MAP_POPULATE, fd, 0);
802 if (header == MAP_FAILED)
803 error (EXIT_FAILURE, errno, gettext ("cannot map database file"));
805 if (header->magic != NSS_DB_MAGIC)
806 error (EXIT_FAILURE, 0, gettext ("file not a database file"));
808 const char *valstrtab = (const char *) header + header->valstroffset;
810 for (unsigned int dbidx = 0; dbidx < header->ndbs; ++dbidx)
812 const stridx_t *stridxtab
813 = ((const stridx_t *) ((const char *) header
814 + header->dbs[dbidx].keyidxoffset));
815 const char *keystrtab
816 = (const char *) header + header->dbs[dbidx].keystroffset;
817 const stridx_t *hashtab
818 = (const stridx_t *) ((const char *) header
819 + header->dbs[dbidx].hashoffset);
821 for (uint32_t hidx = 0; hidx < header->dbs[dbidx].hashsize; ++hidx)
822 if (hashtab[hidx] != ~((stridx_t) 0))
824 header->dbs[dbidx].id,
825 keystrtab + stridxtab[hidx],
826 valstrtab + hashtab[hidx]);
835 set_file_creation_context (const char *outname, mode_t mode)
838 static int enforcing;
839 security_context_t ctx;
841 /* Check if SELinux is enabled, and remember. */
843 enabled = is_selinux_enabled ();
847 /* Check if SELinux is enforcing, and remember. */
849 enforcing = security_getenforce () ? 1 : -1;
851 /* Determine the context which the file should have. */
853 if (matchpathcon (outname, S_IFREG | mode, &ctx) == 0 && ctx != NULL)
855 if (setfscreatecon (ctx) != 0)
856 error (enforcing > 0 ? EXIT_FAILURE : 0, 0,
857 gettext ("cannot set file creation context for `%s'"),
865 reset_file_creation_context (void)
867 setfscreatecon (NULL);