diff options
Diffstat (limited to 'REORG.TODO/nss/makedb.c')
| -rw-r--r-- | REORG.TODO/nss/makedb.c | 879 |
1 files changed, 879 insertions, 0 deletions
diff --git a/REORG.TODO/nss/makedb.c b/REORG.TODO/nss/makedb.c new file mode 100644 index 0000000000..542244dd35 --- /dev/null +++ b/REORG.TODO/nss/makedb.c @@ -0,0 +1,879 @@ +/* Create simple DB database from textual input. + Copyright (C) 1996-2017 Free Software Foundation, Inc. + This file is part of the GNU C Library. + Contributed by Ulrich Drepper <drepper@cygnus.com>, 1996. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + <http://www.gnu.org/licenses/>. */ + +#include <argp.h> +#include <assert.h> +#include <ctype.h> +#include <errno.h> +#include <error.h> +#include <fcntl.h> +#include <inttypes.h> +#include <libintl.h> +#include <locale.h> +#include <search.h> +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> +#include <stdint.h> +#include <sys/mman.h> +#include <sys/param.h> +#include <sys/stat.h> +#include <sys/uio.h> +#include "nss_db/nss_db.h" + +/* Get libc version number. */ +#include "../version.h" + +/* The hashing function we use. */ +#include "../intl/hash-string.h" + +/* SELinux support. */ +#ifdef HAVE_SELINUX +# include <selinux/selinux.h> +#endif + +#ifndef MAP_POPULATE +# define MAP_POPULATE 0 +#endif + +#define PACKAGE _libc_intl_domainname + +/* List of data bases. */ +struct database +{ + char dbid; + bool extra_string; + struct database *next; + void *entries; + size_t nentries; + size_t nhashentries; + stridx_t *hashtable; + size_t keystrlen; + stridx_t *keyidxtab; + char *keystrtab; +} *databases; +static size_t ndatabases; +static size_t nhashentries_total; +static size_t valstrlen; +static void *valstrtree; +static char *valstrtab; +static size_t extrastrlen; + +/* Database entry. */ +struct dbentry +{ + stridx_t validx; + uint32_t hashval; + char str[0]; +}; + +/* Stored string entry. */ +struct valstrentry +{ + stridx_t idx; + bool extra_string; + char str[0]; +}; + + +/* True if any entry has been added. */ +static bool any_dbentry; + +/* If non-zero convert key to lower case. */ +static int to_lowercase; + +/* If non-zero print content of input file, one entry per line. */ +static int do_undo; + +/* If non-zero do not print informational messages. */ +static int be_quiet; + +/* Name of output file. */ +static const char *output_name; + +/* Name and version of program. */ +static void print_version (FILE *stream, struct argp_state *state); +void (*argp_program_version_hook) (FILE *, struct argp_state *) = print_version; + +/* Definitions of arguments for argp functions. */ +static const struct argp_option options[] = +{ + { "fold-case", 'f', NULL, 0, N_("Convert key to lower case") }, + { "output", 'o', N_("NAME"), 0, N_("Write output to file NAME") }, + { "quiet", 'q', NULL, 0, + N_("Do not print messages while building database") }, + { "undo", 'u', NULL, 0, + N_("Print content of database file, one entry a line") }, + { "generated", 'g', N_("CHAR"), 0, + N_("Generated line not part of iteration") }, + { NULL, 0, NULL, 0, NULL } +}; + +/* Short description of program. */ +static const char doc[] = N_("Create simple database from textual input."); + +/* Strings for arguments in help texts. */ +static const char args_doc[] = N_("\ +INPUT-FILE OUTPUT-FILE\n-o OUTPUT-FILE INPUT-FILE\n-u INPUT-FILE"); + +/* Prototype for option handler. */ +static error_t parse_opt (int key, char *arg, struct argp_state *state); + +/* Function to print some extra text in the help message. */ +static char *more_help (int key, const char *text, void *input); + +/* Data structure to communicate with argp functions. */ +static struct argp argp = +{ + options, parse_opt, args_doc, doc, NULL, more_help +}; + + +/* List of databases which are not part of the iteration table. */ +static struct db_option +{ + char dbid; + struct db_option *next; +} *db_options; + + +/* Prototypes for local functions. */ +static int process_input (FILE *input, const char *inname, + int to_lowercase, int be_quiet); +static int print_database (int fd); +static void compute_tables (void); +static int write_output (int fd); + +/* SELinux support. */ +#ifdef HAVE_SELINUX +/* Set the SELinux file creation context for the given file. */ +static void set_file_creation_context (const char *outname, mode_t mode); +static void reset_file_creation_context (void); +#else +# define set_file_creation_context(_outname,_mode) +# define reset_file_creation_context() +#endif + + +/* External functions. */ +#include <programs/xmalloc.h> + + +int +main (int argc, char *argv[]) +{ + const char *input_name; + FILE *input_file; + int remaining; + int mode = 0644; + + /* Set locale via LC_ALL. */ + setlocale (LC_ALL, ""); + + /* Set the text message domain. */ + textdomain (_libc_intl_domainname); + + /* Initialize local variables. */ + input_name = NULL; + + /* Parse and process arguments. */ + argp_parse (&argp, argc, argv, 0, &remaining, NULL); + + /* Determine file names. */ + if (do_undo || output_name != NULL) + { + if (remaining + 1 != argc) + { + wrong_arguments: + error (0, 0, gettext ("wrong number of arguments")); + argp_help (&argp, stdout, ARGP_HELP_SEE, + program_invocation_short_name); + exit (1); + } + input_name = argv[remaining]; + } + else + { + if (remaining + 2 != argc) + goto wrong_arguments; + + input_name = argv[remaining++]; + output_name = argv[remaining]; + } + + /* Special handling if we are asked to print the database. */ + if (do_undo) + { + int fd = open (input_name, O_RDONLY); + if (fd == -1) + error (EXIT_FAILURE, errno, gettext ("cannot open database file `%s'"), + input_name); + + int status = print_database (fd); + + close (fd); + + return status; + } + + /* Open input file. */ + if (strcmp (input_name, "-") == 0 || strcmp (input_name, "/dev/stdin") == 0) + input_file = stdin; + else + { + struct stat64 st; + + input_file = fopen64 (input_name, "r"); + if (input_file == NULL) + error (EXIT_FAILURE, errno, gettext ("cannot open input file `%s'"), + input_name); + + /* Get the access rights from the source file. The output file should + have the same. */ + if (fstat64 (fileno (input_file), &st) >= 0) + mode = st.st_mode & ACCESSPERMS; + } + + /* Start the real work. */ + int status = process_input (input_file, input_name, to_lowercase, be_quiet); + + /* Close files. */ + if (input_file != stdin) + fclose (input_file); + + /* No need to continue when we did not read the file successfully. */ + if (status != EXIT_SUCCESS) + return status; + + /* Bail out if nothing is to be done. */ + if (!any_dbentry) + { + if (be_quiet) + return EXIT_SUCCESS; + else + error (EXIT_SUCCESS, 0, gettext ("no entries to be processed")); + } + + /* Compute hash and string tables. */ + compute_tables (); + + /* Open output file. This must not be standard output so we don't + handle "-" and "/dev/stdout" special. */ + char *tmp_output_name; + if (asprintf (&tmp_output_name, "%s.XXXXXX", output_name) == -1) + error (EXIT_FAILURE, errno, gettext ("cannot create temporary file name")); + + set_file_creation_context (output_name, mode); + int fd = mkstemp (tmp_output_name); + reset_file_creation_context (); + if (fd == -1) + error (EXIT_FAILURE, errno, gettext ("cannot create temporary file")); + + status = write_output (fd); + + if (status == EXIT_SUCCESS) + { + struct stat64 st; + + if (fstat64 (fd, &st) == 0) + { + if ((st.st_mode & ACCESSPERMS) != mode) + /* We ignore problems with changing the mode. */ + fchmod (fd, mode); + } + else + { + error (0, errno, gettext ("cannot stat newly created file")); + status = EXIT_FAILURE; + } + } + + close (fd); + + if (status == EXIT_SUCCESS) + { + if (rename (tmp_output_name, output_name) != 0) + { + error (0, errno, gettext ("cannot rename temporary file")); + status = EXIT_FAILURE; + goto do_unlink; + } + } + else + do_unlink: + unlink (tmp_output_name); + + return status; +} + + +/* Handle program arguments. */ +static error_t +parse_opt (int key, char *arg, struct argp_state *state) +{ + struct db_option *newp; + + switch (key) + { + case 'f': + to_lowercase = 1; + break; + case 'o': + output_name = arg; + break; + case 'q': + be_quiet = 1; + break; + case 'u': + do_undo = 1; + break; + case 'g': + newp = xmalloc (sizeof (*newp)); + newp->dbid = arg[0]; + newp->next = db_options; + db_options = newp; + break; + default: + return ARGP_ERR_UNKNOWN; + } + return 0; +} + + +static char * +more_help (int key, const char *text, void *input) +{ + char *tp = NULL; + switch (key) + { + case ARGP_KEY_HELP_EXTRA: + /* We print some extra information. */ + if (asprintf (&tp, gettext ("\ +For bug reporting instructions, please see:\n\ +%s.\n"), REPORT_BUGS_TO) < 0) + return NULL; + return tp; + default: + break; + } + return (char *) text; +} + +/* Print the version information. */ +static void +print_version (FILE *stream, struct argp_state *state) +{ + fprintf (stream, "makedb %s%s\n", PKGVERSION, VERSION); + fprintf (stream, gettext ("\ +Copyright (C) %s Free Software Foundation, Inc.\n\ +This is free software; see the source for copying conditions. There is NO\n\ +warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\ +"), "2017"); + fprintf (stream, gettext ("Written by %s.\n"), "Ulrich Drepper"); +} + + +static int +dbentry_compare (const void *p1, const void *p2) +{ + const struct dbentry *d1 = (const struct dbentry *) p1; + const struct dbentry *d2 = (const struct dbentry *) p2; + + if (d1->hashval != d2->hashval) + return d1->hashval < d2->hashval ? -1 : 1; + + return strcmp (d1->str, d2->str); +} + + +static int +valstr_compare (const void *p1, const void *p2) +{ + const struct valstrentry *d1 = (const struct valstrentry *) p1; + const struct valstrentry *d2 = (const struct valstrentry *) p2; + + return strcmp (d1->str, d2->str); +} + + +static int +process_input (FILE *input, const char *inname, int to_lowercase, int be_quiet) +{ + char *line; + size_t linelen; + int status; + size_t linenr; + + line = NULL; + linelen = 0; + status = EXIT_SUCCESS; + linenr = 0; + + struct database *last_database = NULL; + + while (!feof_unlocked (input)) + { + ssize_t n = getline (&line, &linelen, input); + if (n < 0) + /* This means end of file or some bug. */ + break; + if (n == 0) + /* Short read. Probably interrupted system call. */ + continue; + + ++linenr; + + if (line[n - 1] == '\n') + /* Remove trailing newline. */ + line[--n] = '\0'; + + char *cp = line; + while (isspace (*cp)) + ++cp; + + if (*cp == '#' || *cp == '\0') + /* First non-space character in line '#': it's a comment. + Also go to the next line if it is empty except for whitespaces. */ + continue; + + /* Skip over the character indicating the database so that it is not + affected by TO_LOWERCASE. */ + char *key = cp++; + while (*cp != '\0' && !isspace (*cp)) + { + if (to_lowercase) + *cp = tolower (*cp); + ++cp; + } + + if (*cp == '\0') + /* It's a line without a value field. */ + continue; + + *cp++ = '\0'; + size_t keylen = cp - key; + + while (isspace (*cp)) + ++cp; + + char *data = cp; + size_t datalen = (&line[n] - cp) + 1; + + /* Find the database. */ + if (last_database == NULL || last_database->dbid != key[0]) + { + last_database = databases; + while (last_database != NULL && last_database->dbid != key[0]) + last_database = last_database->next; + + if (last_database == NULL) + { + last_database = xmalloc (sizeof (*last_database)); + last_database->dbid = key[0]; + last_database->extra_string = false; + last_database->next = databases; + last_database->entries = NULL; + last_database->nentries = 0; + last_database->keystrlen = 0; + databases = last_database; + + struct db_option *runp = db_options; + while (runp != NULL) + if (runp->dbid == key[0]) + { + last_database->extra_string = true; + break; + } + else + runp = runp->next; + } + } + + /* Skip the database selector. */ + ++key; + --keylen; + + /* Store the data. */ + struct valstrentry *nentry = xmalloc (sizeof (struct valstrentry) + + datalen); + if (last_database->extra_string) + nentry->idx = extrastrlen; + else + nentry->idx = valstrlen; + nentry->extra_string = last_database->extra_string; + memcpy (nentry->str, data, datalen); + + struct valstrentry **fdata = tsearch (nentry, &valstrtree, + valstr_compare); + if (fdata == NULL) + error (EXIT_FAILURE, errno, gettext ("cannot create search tree")); + + if (*fdata != nentry) + { + /* We can reuse a string. */ + free (nentry); + nentry = *fdata; + } + else + if (last_database->extra_string) + extrastrlen += datalen; + else + valstrlen += datalen; + + /* Store the key. */ + struct dbentry *newp = xmalloc (sizeof (struct dbentry) + keylen); + newp->validx = nentry->idx; + newp->hashval = __hash_string (key); + memcpy (newp->str, key, keylen); + + struct dbentry **found = tsearch (newp, &last_database->entries, + dbentry_compare); + if (found == NULL) + error (EXIT_FAILURE, errno, gettext ("cannot create search tree")); + + if (*found != newp) + { + free (newp); + if (!be_quiet) + error_at_line (0, 0, inname, linenr, gettext ("duplicate key")); + continue; + } + + ++last_database->nentries; + last_database->keystrlen += keylen; + + any_dbentry = true; + } + + if (ferror_unlocked (input)) + { + error (0, 0, gettext ("problems while reading `%s'"), inname); + status = EXIT_FAILURE; + } + + return status; +} + + +static void +copy_valstr (const void *nodep, const VISIT which, const int depth) +{ + if (which != leaf && which != postorder) + return; + + const struct valstrentry *p = *(const struct valstrentry **) nodep; + + strcpy (valstrtab + (p->extra_string ? valstrlen : 0) + p->idx, p->str); +} + + +/* Determine if the candidate is prime by using a modified trial division + algorithm. The candidate must be both odd and greater than 4. */ +static int +is_prime (size_t candidate) +{ + size_t divn = 3; + size_t sq = divn * divn; + + assert (candidate > 4 && candidate % 2 != 0); + + while (sq < candidate && candidate % divn != 0) + { + ++divn; + sq += 4 * divn; + ++divn; + } + + return candidate % divn != 0; +} + + +static size_t +next_prime (size_t seed) +{ + /* Make sure that we're always greater than 4. */ + seed = (seed + 4) | 1; + + while (!is_prime (seed)) + seed += 2; + + return seed; +} + + +static void +compute_tables (void) +{ + valstrtab = xmalloc (roundup (valstrlen + extrastrlen, sizeof (stridx_t))); + while ((valstrlen + extrastrlen) % sizeof (stridx_t) != 0) + valstrtab[valstrlen++] = '\0'; + twalk (valstrtree, copy_valstr); + + static struct database *db; + for (db = databases; db != NULL; db = db->next) + if (db->nentries != 0) + { + ++ndatabases; + + /* We simply use an odd number large than twice the number of + elements to store in the hash table for the size. This gives + enough efficiency. */ +#define TEST_RANGE 30 + size_t nhashentries_min = next_prime (db->nentries < TEST_RANGE + ? db->nentries + : db->nentries * 2 - TEST_RANGE); + size_t nhashentries_max = MAX (nhashentries_min, db->nentries * 4); + size_t nhashentries_best = nhashentries_min; + size_t chainlength_best = db->nentries; + + db->hashtable = xmalloc (2 * nhashentries_max * sizeof (stridx_t) + + db->keystrlen); + db->keyidxtab = db->hashtable + nhashentries_max; + db->keystrtab = (char *) (db->keyidxtab + nhashentries_max); + + static size_t max_chainlength; + static char *wp; + static size_t nhashentries; + static bool copy_string; + + void add_key(const void *nodep, const VISIT which, const int depth) + { + if (which != leaf && which != postorder) + return; + + const struct dbentry *dbe = *(const struct dbentry **) nodep; + + ptrdiff_t stridx; + if (copy_string) + { + stridx = wp - db->keystrtab; + wp = stpcpy (wp, dbe->str) + 1; + } + else + stridx = 0; + + size_t hidx = dbe->hashval % nhashentries; + size_t hval2 = 1 + dbe->hashval % (nhashentries - 2); + size_t chainlength = 0; + + while (db->hashtable[hidx] != ~((stridx_t) 0)) + { + ++chainlength; + if ((hidx += hval2) >= nhashentries) + hidx -= nhashentries; + } + + db->hashtable[hidx] = ((db->extra_string ? valstrlen : 0) + + dbe->validx); + db->keyidxtab[hidx] = stridx; + + max_chainlength = MAX (max_chainlength, chainlength); + } + + copy_string = false; + nhashentries = nhashentries_min; + for (size_t cnt = 0; cnt < TEST_RANGE; ++cnt) + { + memset (db->hashtable, '\xff', nhashentries * sizeof (stridx_t)); + + max_chainlength = 0; + wp = db->keystrtab; + + twalk (db->entries, add_key); + + if (max_chainlength == 0) + { + /* No need to look further, this is as good as it gets. */ + nhashentries_best = nhashentries; + break; + } + + if (max_chainlength < chainlength_best) + { + chainlength_best = max_chainlength; + nhashentries_best = nhashentries; + } + + nhashentries = next_prime (nhashentries + 1); + if (nhashentries > nhashentries_max) + break; + } + + /* Recompute the best table again, this time fill in the strings. */ + nhashentries = nhashentries_best; + memset (db->hashtable, '\xff', + 2 * nhashentries_max * sizeof (stridx_t)); + copy_string = true; + wp = db->keystrtab; + + twalk (db->entries, add_key); + + db->nhashentries = nhashentries_best; + nhashentries_total += nhashentries_best; + } +} + + +static int +write_output (int fd) +{ + struct nss_db_header *header; + uint64_t file_offset = (sizeof (struct nss_db_header) + + (ndatabases * sizeof (header->dbs[0]))); + header = alloca (file_offset); + + header->magic = NSS_DB_MAGIC; + header->ndbs = ndatabases; + header->valstroffset = file_offset; + header->valstrlen = valstrlen; + + size_t filled_dbs = 0; + struct iovec iov[2 + ndatabases * 3]; + iov[0].iov_base = header; + iov[0].iov_len = file_offset; + + iov[1].iov_base = valstrtab; + iov[1].iov_len = valstrlen + extrastrlen; + file_offset += iov[1].iov_len; + + size_t keydataoffset = file_offset + nhashentries_total * sizeof (stridx_t); + for (struct database *db = databases; db != NULL; db = db->next) + if (db->entries != NULL) + { + assert (file_offset % sizeof (stridx_t) == 0); + assert (filled_dbs < ndatabases); + + header->dbs[filled_dbs].id = db->dbid; + memset (header->dbs[filled_dbs].pad, '\0', + sizeof (header->dbs[0].pad)); + header->dbs[filled_dbs].hashsize = db->nhashentries; + + iov[2 + filled_dbs].iov_base = db->hashtable; + iov[2 + filled_dbs].iov_len = db->nhashentries * sizeof (stridx_t); + header->dbs[filled_dbs].hashoffset = file_offset; + file_offset += iov[2 + filled_dbs].iov_len; + + iov[2 + ndatabases + filled_dbs * 2].iov_base = db->keyidxtab; + iov[2 + ndatabases + filled_dbs * 2].iov_len + = db->nhashentries * sizeof (stridx_t); + header->dbs[filled_dbs].keyidxoffset = keydataoffset; + keydataoffset += iov[2 + ndatabases + filled_dbs * 2].iov_len; + + iov[3 + ndatabases + filled_dbs * 2].iov_base = db->keystrtab; + iov[3 + ndatabases + filled_dbs * 2].iov_len = db->keystrlen; + header->dbs[filled_dbs].keystroffset = keydataoffset; + keydataoffset += iov[3 + ndatabases + filled_dbs * 2].iov_len; + + ++filled_dbs; + } + + assert (filled_dbs == ndatabases); + assert (file_offset == (iov[0].iov_len + iov[1].iov_len + + nhashentries_total * sizeof (stridx_t))); + header->allocate = file_offset; + + if (writev (fd, iov, 2 + ndatabases * 3) != keydataoffset) + { + error (0, errno, gettext ("failed to write new database file")); + return EXIT_FAILURE; + } + + return EXIT_SUCCESS; +} + + +static int +print_database (int fd) +{ + struct stat64 st; + if (fstat64 (fd, &st) != 0) + error (EXIT_FAILURE, errno, gettext ("cannot stat database file")); + + const struct nss_db_header *header = mmap (NULL, st.st_size, PROT_READ, + MAP_PRIVATE|MAP_POPULATE, fd, 0); + if (header == MAP_FAILED) + error (EXIT_FAILURE, errno, gettext ("cannot map database file")); + + if (header->magic != NSS_DB_MAGIC) + error (EXIT_FAILURE, 0, gettext ("file not a database file")); + + const char *valstrtab = (const char *) header + header->valstroffset; + + for (unsigned int dbidx = 0; dbidx < header->ndbs; ++dbidx) + { + const stridx_t *stridxtab + = ((const stridx_t *) ((const char *) header + + header->dbs[dbidx].keyidxoffset)); + const char *keystrtab + = (const char *) header + header->dbs[dbidx].keystroffset; + const stridx_t *hashtab + = (const stridx_t *) ((const char *) header + + header->dbs[dbidx].hashoffset); + + for (uint32_t hidx = 0; hidx < header->dbs[dbidx].hashsize; ++hidx) + if (hashtab[hidx] != ~((stridx_t) 0)) + printf ("%c%s %s\n", + header->dbs[dbidx].id, + keystrtab + stridxtab[hidx], + valstrtab + hashtab[hidx]); + } + + return EXIT_SUCCESS; +} + + +#ifdef HAVE_SELINUX +static void +set_file_creation_context (const char *outname, mode_t mode) +{ + static int enabled; + static int enforcing; + security_context_t ctx; + + /* Check if SELinux is enabled, and remember. */ + if (enabled == 0) + enabled = is_selinux_enabled () ? 1 : -1; + if (enabled < 0) + return; + + /* Check if SELinux is enforcing, and remember. */ + if (enforcing == 0) + enforcing = security_getenforce () ? 1 : -1; + + /* Determine the context which the file should have. */ + ctx = NULL; + if (matchpathcon (outname, S_IFREG | mode, &ctx) == 0 && ctx != NULL) + { + if (setfscreatecon (ctx) != 0) + error (enforcing > 0 ? EXIT_FAILURE : 0, 0, + gettext ("cannot set file creation context for `%s'"), + outname); + + freecon (ctx); + } +} + +static void +reset_file_creation_context (void) +{ + setfscreatecon (NULL); +} +#endif |