1 /* Create simple DB database from textual input.
2 Copyright (C) 1996-2013 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/>. */
36 #include <sys/param.h>
39 #include "nss_db/nss_db.h"
41 /* Get libc version number. */
42 #include "../version.h"
44 /* The hashing function we use. */
45 #include "../intl/hash-string.h"
47 /* SELinux support. */
49 # include <selinux/selinux.h>
53 # define MAP_POPULATE 0
56 #define PACKAGE _libc_intl_domainname
58 /* List of data bases. */
63 struct database
*next
;
72 static size_t ndatabases
;
73 static size_t nhashentries_total
;
74 static size_t valstrlen
;
75 static void *valstrtree
;
76 static char *valstrtab
;
77 static size_t extrastrlen
;
87 /* Stored string entry. */
96 /* True if any entry has been added. */
97 static bool any_dbentry
;
99 /* If non-zero convert key to lower case. */
100 static int to_lowercase
;
102 /* If non-zero print content of input file, one entry per line. */
105 /* If non-zero do not print informational messages. */
108 /* Name of output file. */
109 static const char *output_name
;
111 /* Name and version of program. */
112 static void print_version (FILE *stream
, struct argp_state
*state
);
113 void (*argp_program_version_hook
) (FILE *, struct argp_state
*) = print_version
;
115 /* Definitions of arguments for argp functions. */
116 static const struct argp_option options
[] =
118 { "fold-case", 'f', NULL
, 0, N_("Convert key to lower case") },
119 { "output", 'o', N_("NAME"), 0, N_("Write output to file NAME") },
120 { "quiet", 'q', NULL
, 0,
121 N_("Do not print messages while building database") },
122 { "undo", 'u', NULL
, 0,
123 N_("Print content of database file, one entry a line") },
124 { "generated", 'g', N_("CHAR"), 0,
125 N_("Generated line not part of iteration") },
126 { NULL
, 0, NULL
, 0, NULL
}
129 /* Short description of program. */
130 static const char doc
[] = N_("Create simple database from textual input.");
132 /* Strings for arguments in help texts. */
133 static const char args_doc
[] = N_("\
134 INPUT-FILE OUTPUT-FILE\n-o OUTPUT-FILE INPUT-FILE\n-u INPUT-FILE");
136 /* Prototype for option handler. */
137 static error_t
parse_opt (int key
, char *arg
, struct argp_state
*state
);
139 /* Function to print some extra text in the help message. */
140 static char *more_help (int key
, const char *text
, void *input
);
142 /* Data structure to communicate with argp functions. */
143 static struct argp argp
=
145 options
, parse_opt
, args_doc
, doc
, NULL
, more_help
149 /* List of databases which are not part of the iteration table. */
150 static struct db_option
153 struct db_option
*next
;
157 /* Prototypes for local functions. */
158 static int process_input (FILE *input
, const char *inname
,
159 int to_lowercase
, int be_quiet
);
160 static int print_database (int fd
);
161 static void compute_tables (void);
162 static int write_output (int fd
);
164 /* SELinux support. */
166 /* Set the SELinux file creation context for the given file. */
167 static void set_file_creation_context (const char *outname
, mode_t mode
);
168 static void reset_file_creation_context (void);
170 # define set_file_creation_context(_outname,_mode)
171 # define reset_file_creation_context()
175 /* External functions. */
176 extern void *xmalloc (size_t n
)
177 __attribute_malloc__
__attribute_alloc_size (1);
178 extern void *xcalloc (size_t n
, size_t s
)
179 __attribute_malloc__
__attribute_alloc_size (1, 2);
183 main (int argc
, char *argv
[])
185 const char *input_name
;
190 /* Set locale via LC_ALL. */
191 setlocale (LC_ALL
, "");
193 /* Set the text message domain. */
194 textdomain (_libc_intl_domainname
);
196 /* Initialize local variables. */
199 /* Parse and process arguments. */
200 argp_parse (&argp
, argc
, argv
, 0, &remaining
, NULL
);
202 /* Determine file names. */
203 if (do_undo
|| output_name
!= NULL
)
205 if (remaining
+ 1 != argc
)
208 error (0, 0, gettext ("wrong number of arguments"));
209 argp_help (&argp
, stdout
, ARGP_HELP_SEE
,
210 program_invocation_short_name
);
213 input_name
= argv
[remaining
];
217 if (remaining
+ 2 != argc
)
218 goto wrong_arguments
;
220 input_name
= argv
[remaining
++];
221 output_name
= argv
[remaining
];
224 /* Special handling if we are asked to print the database. */
227 int fd
= open (input_name
, O_RDONLY
);
229 error (EXIT_FAILURE
, errno
, gettext ("cannot open database file `%s'"),
232 int status
= print_database (fd
);
239 /* Open input file. */
240 if (strcmp (input_name
, "-") == 0 || strcmp (input_name
, "/dev/stdin") == 0)
246 input_file
= fopen64 (input_name
, "r");
247 if (input_file
== NULL
)
248 error (EXIT_FAILURE
, errno
, gettext ("cannot open input file `%s'"),
251 /* Get the access rights from the source file. The output file should
253 if (fstat64 (fileno (input_file
), &st
) >= 0)
254 mode
= st
.st_mode
& ACCESSPERMS
;
257 /* Start the real work. */
258 int status
= process_input (input_file
, input_name
, to_lowercase
, be_quiet
);
261 if (input_file
!= stdin
)
264 /* No need to continue when we did not read the file successfully. */
265 if (status
!= EXIT_SUCCESS
)
268 /* Bail out if nothing is to be done. */
274 error (EXIT_SUCCESS
, 0, gettext ("no entries to be processed"));
277 /* Compute hash and string tables. */
280 /* Open output file. This must not be standard output so we don't
281 handle "-" and "/dev/stdout" special. */
282 char *tmp_output_name
;
283 if (asprintf (&tmp_output_name
, "%s.XXXXXX", output_name
) == -1)
284 error (EXIT_FAILURE
, errno
, gettext ("cannot create temporary file name"));
286 set_file_creation_context (output_name
, mode
);
287 int fd
= mkstemp (tmp_output_name
);
288 reset_file_creation_context ();
290 error (EXIT_FAILURE
, errno
, gettext ("cannot create temporary file"));
292 status
= write_output (fd
);
294 if (status
== EXIT_SUCCESS
)
298 if (fstat64 (fd
, &st
) == 0)
300 if ((st
.st_mode
& ACCESSPERMS
) != mode
)
301 /* We ignore problems with changing the mode. */
306 error (0, errno
, gettext ("cannot stat newly created file"));
307 status
= EXIT_FAILURE
;
313 if (status
== EXIT_SUCCESS
)
315 if (rename (tmp_output_name
, output_name
) != 0)
317 error (0, errno
, gettext ("cannot rename temporary file"));
318 status
= EXIT_FAILURE
;
324 unlink (tmp_output_name
);
330 /* Handle program arguments. */
332 parse_opt (int key
, char *arg
, struct argp_state
*state
)
334 struct db_option
*newp
;
351 newp
= xmalloc (sizeof (*newp
));
353 newp
->next
= db_options
;
357 return ARGP_ERR_UNKNOWN
;
364 more_help (int key
, const char *text
, void *input
)
369 case ARGP_KEY_HELP_EXTRA
:
370 /* We print some extra information. */
371 if (asprintf (&tp
, gettext ("\
372 For bug reporting instructions, please see:\n\
373 %s.\n"), REPORT_BUGS_TO
) < 0)
379 return (char *) text
;
382 /* Print the version information. */
384 print_version (FILE *stream
, struct argp_state
*state
)
386 fprintf (stream
, "makedb %s%s\n", PKGVERSION
, VERSION
);
387 fprintf (stream
, gettext ("\
388 Copyright (C) %s Free Software Foundation, Inc.\n\
389 This is free software; see the source for copying conditions. There is NO\n\
390 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\
392 fprintf (stream
, gettext ("Written by %s.\n"), "Ulrich Drepper");
397 dbentry_compare (const void *p1
, const void *p2
)
399 const struct dbentry
*d1
= (const struct dbentry
*) p1
;
400 const struct dbentry
*d2
= (const struct dbentry
*) p2
;
402 if (d1
->hashval
!= d2
->hashval
)
403 return d1
->hashval
< d2
->hashval
? -1 : 1;
405 return strcmp (d1
->str
, d2
->str
);
410 valstr_compare (const void *p1
, const void *p2
)
412 const struct valstrentry
*d1
= (const struct valstrentry
*) p1
;
413 const struct valstrentry
*d2
= (const struct valstrentry
*) p2
;
415 return strcmp (d1
->str
, d2
->str
);
420 process_input (input
, inname
, to_lowercase
, be_quiet
)
433 status
= EXIT_SUCCESS
;
436 struct database
*last_database
= NULL
;
438 while (!feof_unlocked (input
))
440 ssize_t n
= getline (&line
, &linelen
, input
);
442 /* This means end of file or some bug. */
445 /* Short read. Probably interrupted system call. */
450 if (line
[n
- 1] == '\n')
451 /* Remove trailing newline. */
455 while (isspace (*cp
))
458 if (*cp
== '#' || *cp
== '\0')
459 /* First non-space character in line '#': it's a comment.
460 Also go to the next line if it is empty except for whitespaces. */
463 /* Skip over the character indicating the database so that it is not
464 affected by TO_LOWERCASE. */
466 while (*cp
!= '\0' && !isspace (*cp
))
474 /* It's a line without a value field. */
478 size_t keylen
= cp
- key
;
480 while (isspace (*cp
))
484 size_t datalen
= (&line
[n
] - cp
) + 1;
486 /* Find the database. */
487 if (last_database
== NULL
|| last_database
->dbid
!= key
[0])
489 last_database
= databases
;
490 while (last_database
!= NULL
&& last_database
->dbid
!= key
[0])
491 last_database
= last_database
->next
;
493 if (last_database
== NULL
)
495 last_database
= xmalloc (sizeof (*last_database
));
496 last_database
->dbid
= key
[0];
497 last_database
->extra_string
= false;
498 last_database
->next
= databases
;
499 last_database
->entries
= NULL
;
500 last_database
->nentries
= 0;
501 last_database
->keystrlen
= 0;
502 databases
= last_database
;
504 struct db_option
*runp
= db_options
;
506 if (runp
->dbid
== key
[0])
508 last_database
->extra_string
= true;
516 /* Skip the database selector. */
520 /* Store the data. */
521 struct valstrentry
*nentry
= xmalloc (sizeof (struct valstrentry
)
523 if (last_database
->extra_string
)
524 nentry
->idx
= extrastrlen
;
526 nentry
->idx
= valstrlen
;
527 nentry
->extra_string
= last_database
->extra_string
;
528 memcpy (nentry
->str
, data
, datalen
);
530 struct valstrentry
**fdata
= tsearch (nentry
, &valstrtree
,
533 error (EXIT_FAILURE
, errno
, gettext ("cannot create search tree"));
535 if (*fdata
!= nentry
)
537 /* We can reuse a string. */
542 if (last_database
->extra_string
)
543 extrastrlen
+= datalen
;
545 valstrlen
+= datalen
;
548 struct dbentry
*newp
= xmalloc (sizeof (struct dbentry
) + keylen
);
549 newp
->validx
= nentry
->idx
;
550 newp
->hashval
= __hash_string (key
);
551 memcpy (newp
->str
, key
, keylen
);
553 struct dbentry
**found
= tsearch (newp
, &last_database
->entries
,
556 error (EXIT_FAILURE
, errno
, gettext ("cannot create search tree"));
562 error_at_line (0, 0, inname
, linenr
, gettext ("duplicate key"));
566 ++last_database
->nentries
;
567 last_database
->keystrlen
+= keylen
;
572 if (ferror_unlocked (input
))
574 error (0, 0, gettext ("problems while reading `%s'"), inname
);
575 status
= EXIT_FAILURE
;
583 copy_valstr (const void *nodep
, const VISIT which
, const int depth
)
585 if (which
!= leaf
&& which
!= postorder
)
588 const struct valstrentry
*p
= *(const struct valstrentry
**) nodep
;
590 strcpy (valstrtab
+ (p
->extra_string
? valstrlen
: 0) + p
->idx
, p
->str
);
594 /* Determine if the candidate is prime by using a modified trial division
595 algorithm. The candidate must be both odd and greater than 4. */
597 is_prime (size_t candidate
)
600 size_t sq
= divn
* divn
;
602 assert (candidate
> 4 && candidate
% 2 != 0);
604 while (sq
< candidate
&& candidate
% divn
!= 0)
611 return candidate
% divn
!= 0;
616 next_prime (size_t seed
)
618 /* Make sure that we're always greater than 4. */
619 seed
= (seed
+ 4) | 1;
621 while (!is_prime (seed
))
629 compute_tables (void)
631 valstrtab
= xmalloc (roundup (valstrlen
+ extrastrlen
, sizeof (stridx_t
)));
632 while ((valstrlen
+ extrastrlen
) % sizeof (stridx_t
) != 0)
633 valstrtab
[valstrlen
++] = '\0';
634 twalk (valstrtree
, copy_valstr
);
636 static struct database
*db
;
637 for (db
= databases
; db
!= NULL
; db
= db
->next
)
638 if (db
->nentries
!= 0)
642 /* We simply use an odd number large than twice the number of
643 elements to store in the hash table for the size. This gives
644 enough efficiency. */
645 #define TEST_RANGE 30
646 size_t nhashentries_min
= next_prime (db
->nentries
< TEST_RANGE
648 : db
->nentries
* 2 - TEST_RANGE
);
649 size_t nhashentries_max
= MAX (nhashentries_min
, db
->nentries
* 4);
650 size_t nhashentries_best
= nhashentries_min
;
651 size_t chainlength_best
= db
->nentries
;
653 db
->hashtable
= xmalloc (2 * nhashentries_max
* sizeof (stridx_t
)
655 db
->keyidxtab
= db
->hashtable
+ nhashentries_max
;
656 db
->keystrtab
= (char *) (db
->keyidxtab
+ nhashentries_max
);
658 static size_t max_chainlength
;
660 static size_t nhashentries
;
661 static bool copy_string
;
663 void add_key(const void *nodep
, const VISIT which
, const int depth
)
665 if (which
!= leaf
&& which
!= postorder
)
668 const struct dbentry
*dbe
= *(const struct dbentry
**) nodep
;
673 stridx
= wp
- db
->keystrtab
;
674 wp
= stpcpy (wp
, dbe
->str
) + 1;
679 size_t hidx
= dbe
->hashval
% nhashentries
;
680 size_t hval2
= 1 + dbe
->hashval
% (nhashentries
- 2);
681 size_t chainlength
= 0;
683 while (db
->hashtable
[hidx
] != ~((stridx_t
) 0))
686 if ((hidx
+= hval2
) >= nhashentries
)
687 hidx
-= nhashentries
;
690 db
->hashtable
[hidx
] = ((db
->extra_string
? valstrlen
: 0)
692 db
->keyidxtab
[hidx
] = stridx
;
694 max_chainlength
= MAX (max_chainlength
, chainlength
);
698 nhashentries
= nhashentries_min
;
699 for (size_t cnt
= 0; cnt
< TEST_RANGE
; ++cnt
)
701 memset (db
->hashtable
, '\xff', nhashentries
* sizeof (stridx_t
));
706 twalk (db
->entries
, add_key
);
708 if (max_chainlength
== 0)
710 /* No need to look further, this is as good as it gets. */
711 nhashentries_best
= nhashentries
;
715 if (max_chainlength
< chainlength_best
)
717 chainlength_best
= max_chainlength
;
718 nhashentries_best
= nhashentries
;
721 nhashentries
= next_prime (nhashentries
+ 1);
722 if (nhashentries
> nhashentries_max
)
726 /* Recompute the best table again, this time fill in the strings. */
727 nhashentries
= nhashentries_best
;
728 memset (db
->hashtable
, '\xff',
729 2 * nhashentries_max
* sizeof (stridx_t
));
733 twalk (db
->entries
, add_key
);
735 db
->nhashentries
= nhashentries_best
;
736 nhashentries_total
+= nhashentries_best
;
742 write_output (int fd
)
744 struct nss_db_header
*header
;
745 uint64_t file_offset
= (sizeof (struct nss_db_header
)
746 + (ndatabases
* sizeof (header
->dbs
[0])));
747 header
= alloca (file_offset
);
749 header
->magic
= NSS_DB_MAGIC
;
750 header
->ndbs
= ndatabases
;
751 header
->valstroffset
= file_offset
;
752 header
->valstrlen
= valstrlen
;
754 size_t filled_dbs
= 0;
755 struct iovec iov
[2 + ndatabases
* 3];
756 iov
[0].iov_base
= header
;
757 iov
[0].iov_len
= file_offset
;
759 iov
[1].iov_base
= valstrtab
;
760 iov
[1].iov_len
= valstrlen
+ extrastrlen
;
761 file_offset
+= iov
[1].iov_len
;
763 size_t keydataoffset
= file_offset
+ nhashentries_total
* sizeof (stridx_t
);
764 for (struct database
*db
= databases
; db
!= NULL
; db
= db
->next
)
765 if (db
->entries
!= NULL
)
767 assert (file_offset
% sizeof (stridx_t
) == 0);
768 assert (filled_dbs
< ndatabases
);
770 header
->dbs
[filled_dbs
].id
= db
->dbid
;
771 memset (header
->dbs
[filled_dbs
].pad
, '\0',
772 sizeof (header
->dbs
[0].pad
));
773 header
->dbs
[filled_dbs
].hashsize
= db
->nhashentries
;
775 iov
[2 + filled_dbs
].iov_base
= db
->hashtable
;
776 iov
[2 + filled_dbs
].iov_len
= db
->nhashentries
* sizeof (stridx_t
);
777 header
->dbs
[filled_dbs
].hashoffset
= file_offset
;
778 file_offset
+= iov
[2 + filled_dbs
].iov_len
;
780 iov
[2 + ndatabases
+ filled_dbs
* 2].iov_base
= db
->keyidxtab
;
781 iov
[2 + ndatabases
+ filled_dbs
* 2].iov_len
782 = db
->nhashentries
* sizeof (stridx_t
);
783 header
->dbs
[filled_dbs
].keyidxoffset
= keydataoffset
;
784 keydataoffset
+= iov
[2 + ndatabases
+ filled_dbs
* 2].iov_len
;
786 iov
[3 + ndatabases
+ filled_dbs
* 2].iov_base
= db
->keystrtab
;
787 iov
[3 + ndatabases
+ filled_dbs
* 2].iov_len
= db
->keystrlen
;
788 header
->dbs
[filled_dbs
].keystroffset
= keydataoffset
;
789 keydataoffset
+= iov
[3 + ndatabases
+ filled_dbs
* 2].iov_len
;
794 assert (filled_dbs
== ndatabases
);
795 assert (file_offset
== (iov
[0].iov_len
+ iov
[1].iov_len
796 + nhashentries_total
* sizeof (stridx_t
)));
797 header
->allocate
= file_offset
;
799 if (writev (fd
, iov
, 2 + ndatabases
* 3) != keydataoffset
)
801 error (0, errno
, gettext ("failed to write new database file"));
810 print_database (int fd
)
813 if (fstat64 (fd
, &st
) != 0)
814 error (EXIT_FAILURE
, errno
, gettext ("cannot stat database file"));
816 const struct nss_db_header
*header
= mmap (NULL
, st
.st_size
, PROT_READ
,
817 MAP_PRIVATE
|MAP_POPULATE
, fd
, 0);
818 if (header
== MAP_FAILED
)
819 error (EXIT_FAILURE
, errno
, gettext ("cannot map database file"));
821 if (header
->magic
!= NSS_DB_MAGIC
)
822 error (EXIT_FAILURE
, 0, gettext ("file not a database file"));
824 const char *valstrtab
= (const char *) header
+ header
->valstroffset
;
826 for (unsigned int dbidx
= 0; dbidx
< header
->ndbs
; ++dbidx
)
828 const stridx_t
*stridxtab
829 = ((const stridx_t
*) ((const char *) header
830 + header
->dbs
[dbidx
].keyidxoffset
));
831 const char *keystrtab
832 = (const char *) header
+ header
->dbs
[dbidx
].keystroffset
;
833 const stridx_t
*hashtab
834 = (const stridx_t
*) ((const char *) header
835 + header
->dbs
[dbidx
].hashoffset
);
837 for (uint32_t hidx
= 0; hidx
< header
->dbs
[dbidx
].hashsize
; ++hidx
)
838 if (hashtab
[hidx
] != ~((stridx_t
) 0))
840 header
->dbs
[dbidx
].id
,
841 keystrtab
+ stridxtab
[hidx
],
842 valstrtab
+ hashtab
[hidx
]);
851 set_file_creation_context (const char *outname
, mode_t mode
)
854 static int enforcing
;
855 security_context_t ctx
;
857 /* Check if SELinux is enabled, and remember. */
859 enabled
= is_selinux_enabled () ? 1 : -1;
863 /* Check if SELinux is enforcing, and remember. */
865 enforcing
= security_getenforce () ? 1 : -1;
867 /* Determine the context which the file should have. */
869 if (matchpathcon (outname
, S_IFREG
| mode
, &ctx
) == 0 && ctx
!= NULL
)
871 if (setfscreatecon (ctx
) != 0)
872 error (enforcing
> 0 ? EXIT_FAILURE
: 0, 0,
873 gettext ("cannot set file creation context for `%s'"),
881 reset_file_creation_context (void)
883 setfscreatecon (NULL
);