From 464df1d5e5ab1322e2dd0a7796939fff1aeefa9a Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 17:49:25 +0200 Subject: Adding upstream version 1.47.0. Signed-off-by: Daniel Baumann --- lib/support/Android.bp | 78 ++ lib/support/Makefile.in | 184 ++++ lib/support/argv_parse.c | 168 ++++ lib/support/argv_parse.h | 43 + lib/support/common.h | 36 + lib/support/cstring.c | 162 ++++ lib/support/cstring.h | 6 + lib/support/devname.c | 65 ++ lib/support/devname.h | 19 + lib/support/dict.c | 1542 +++++++++++++++++++++++++++++++++ lib/support/dict.h | 147 ++++ lib/support/dqblk_v2.h | 31 + lib/support/mkquota.c | 707 +++++++++++++++ lib/support/nls-enable.h | 21 + lib/support/parse_qtype.c | 90 ++ lib/support/plausible.c | 287 +++++++ lib/support/plausible.h | 29 + lib/support/print_fs_flags.c | 75 ++ lib/support/print_fs_flags.h | 5 + lib/support/prof_err.et | 66 ++ lib/support/profile.c | 1910 +++++++++++++++++++++++++++++++++++++++++ lib/support/profile.h | 107 +++ lib/support/profile_helpers.c | 317 +++++++ lib/support/profile_helpers.h | 28 + lib/support/quotaio.c | 412 +++++++++ lib/support/quotaio.h | 268 ++++++ lib/support/quotaio_tree.c | 687 +++++++++++++++ lib/support/quotaio_tree.h | 64 ++ lib/support/quotaio_v2.c | 389 +++++++++ lib/support/quotaio_v2.h | 69 ++ lib/support/sort_r.h | 325 +++++++ 31 files changed, 8337 insertions(+) create mode 100644 lib/support/Android.bp create mode 100644 lib/support/Makefile.in create mode 100644 lib/support/argv_parse.c create mode 100644 lib/support/argv_parse.h create mode 100644 lib/support/common.h create mode 100644 lib/support/cstring.c create mode 100644 lib/support/cstring.h create mode 100644 lib/support/devname.c create mode 100644 lib/support/devname.h create mode 100644 lib/support/dict.c create mode 100644 lib/support/dict.h create mode 100644 lib/support/dqblk_v2.h create mode 100644 lib/support/mkquota.c create mode 100644 lib/support/nls-enable.h create mode 100644 lib/support/parse_qtype.c create mode 100644 lib/support/plausible.c create mode 100644 lib/support/plausible.h create mode 100644 lib/support/print_fs_flags.c create mode 100644 lib/support/print_fs_flags.h create mode 100644 lib/support/prof_err.et create mode 100644 lib/support/profile.c create mode 100644 lib/support/profile.h create mode 100644 lib/support/profile_helpers.c create mode 100644 lib/support/profile_helpers.h create mode 100644 lib/support/quotaio.c create mode 100644 lib/support/quotaio.h create mode 100644 lib/support/quotaio_tree.c create mode 100644 lib/support/quotaio_tree.h create mode 100644 lib/support/quotaio_v2.c create mode 100644 lib/support/quotaio_v2.h create mode 100644 lib/support/sort_r.h (limited to 'lib/support') diff --git a/lib/support/Android.bp b/lib/support/Android.bp new file mode 100644 index 0000000..af9b28d --- /dev/null +++ b/lib/support/Android.bp @@ -0,0 +1,78 @@ +// Copyright 2017 The Android Open Source Project + +package { + // See: http://go/android-license-faq + // A large-scale-change added 'default_applicable_licenses' to import + // all of the 'license_kinds' from "external_e2fsprogs_license" + // to get the below license kinds: + // SPDX-license-identifier-GPL + // SPDX-license-identifier-MIT + default_applicable_licenses: ["external_e2fsprogs_license"], +} + +cc_library { + name: "libext2_quota", + host_supported: true, + ramdisk_available: true, + vendor_ramdisk_available: true, + recovery_available: true, + unique_host_soname: true, + defaults: ["e2fsprogs-defaults"], + srcs: [ + "devname.c", + "dict.c", + "mkquota.c", + "parse_qtype.c", + "plausible.c", + "profile.c", + "profile_helpers.c", + "prof_err.c", + "quotaio.c", + "quotaio_tree.c", + "quotaio_v2.c", + ], + shared_libs: [ + "libext2fs", + "libext2_blkid", + "libext2_com_err", + ], + + target: { + windows: { + enabled: true, + }, + }, + + header_libs: ["libext2-headers"], + export_include_dirs: ["."], + export_header_lib_headers: ["libext2-headers"], +} + +cc_library_shared { + name: "libext2_profile", + host_supported: true, + unique_host_soname: true, + defaults: ["e2fsprogs-defaults"], + + srcs: [ + "prof_err.c", + "profile.c", + ], + shared_libs: ["libext2_com_err"], + + header_libs: ["libext2-headers"], + export_include_dirs: ["."], + export_header_lib_headers: ["libext2-headers"], +} + +cc_library { + name: "libext2_support", + host_supported: true, + defaults: ["e2fsprogs-defaults"], + + srcs: [ + "cstring.c", + ], + header_libs: ["libext2-headers"], + export_include_dirs: ["."], +} diff --git a/lib/support/Makefile.in b/lib/support/Makefile.in new file mode 100644 index 0000000..b622909 --- /dev/null +++ b/lib/support/Makefile.in @@ -0,0 +1,184 @@ +# Makefile for e2fsprog's internal support +# + +srcdir = @srcdir@ +top_srcdir = @top_srcdir@ +VPATH = @srcdir@ +top_builddir = ../.. +my_dir = lib/support +INSTALL = @INSTALL@ +MKDIR_P = @MKDIR_P@ + +@MCONFIG@ + +all:: + +OBJS= cstring.o \ + mkquota.o \ + plausible.o \ + profile.o \ + parse_qtype.o \ + print_fs_flags.o \ + profile_helpers.o \ + prof_err.o \ + quotaio.o \ + quotaio_v2.o \ + quotaio_tree.o \ + dict.o \ + devname.o + +SRCS= $(srcdir)/argv_parse.c \ + $(srcdir)/cstring.c \ + $(srcdir)/mkquota.c \ + $(srcdir)/parse_qtype.c \ + $(srcdir)/plausible.c \ + $(srcdir)/print_fs_flags.c \ + $(srcdir)/profile.c \ + $(srcdir)/profile_helpers.c \ + prof_err.c \ + $(srcdir)/quotaio.c \ + $(srcdir)/quotaio_tree.c \ + $(srcdir)/quotaio_v2.c \ + $(srcdir)/dict.c \ + $(srcdir)/devname.c + +LIBRARY= libsupport +LIBDIR= support + +@MAKEFILE_LIBRARY@ +@MAKEFILE_PROFILE@ + +COMPILE_ET= _ET_DIR_OVERRIDE=$(srcdir)/../et ../et/compile_et + +.c.o: + $(E) " CC $<" + $(Q) $(CC) $(ALL_CFLAGS) -c $< -o $@ + $(Q) $(CHECK_CMD) $(ALL_CFLAGS) $< + $(Q) $(CPPCHECK_CMD) $(CPPFLAGS) $< +@PROFILE_CMT@ $(Q) $(CC) $(ALL_CFLAGS) -g -pg -o profiled/$*.o -c $< + +installdirs:: + +install:: all + +uninstall:: + +prof_err.c prof_err.h: prof_err.et + $(E) " COMPILE_ET prof_err.et" + $(Q) $(COMPILE_ET) $(srcdir)/prof_err.et + +test_profile: $(srcdir)/profile.c profile_helpers.o argv_parse.o \ + prof_err.o profile.h $(DEPSTATIC_LIBCOM_ERR) + $(E) " LD $@" + $(Q) $(CC) -o test_profile -DDEBUG_PROGRAM $(srcdir)/profile.c prof_err.o \ + profile_helpers.o argv_parse.o $(STATIC_LIBCOM_ERR) \ + $(ALL_CFLAGS) + +test_cstring: $(srcdir)/cstring.c + $(E) " CC $@" + $(Q) $(CC) -o test_cstring -DDEBUG_PROGRAM $(srcdir)/cstring.c \ + $(ALL_CFLAGS) + +clean:: + $(RM) -f \#* *.s *.o *.a *~ *.bak core profiled/* \ + ../libsupport.a ../libsupport_p.a $(SMANPAGES) \ + prof_err.c prof_err.h test_profile test_cstring + +#fullcheck check:: tst_uuid +# LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_uuid + +mostlyclean:: clean +distclean:: clean + $(RM) -f .depend Makefile \ + $(srcdir)/TAGS $(srcdir)/Makefile.in.old + +# +# Hack to parallel makes recognize dependencies correctly. +# +../../lib/libsupport.a: libsupport.a +../../lib/libsupport.so: image +../../lib/libsupport.dylib: image + +$(OBJS): + +# +++ Dependency line eater +++ +# +# Makefile dependencies follow. This must be the last section in +# the Makefile.in file +# +argv_parse.o: $(srcdir)/argv_parse.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(srcdir)/argv_parse.h +cstring.o: $(srcdir)/cstring.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(srcdir)/cstring.h +mkquota.o: $(srcdir)/mkquota.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(top_srcdir)/lib/ext2fs/ext2_fs.h \ + $(top_builddir)/lib/ext2fs/ext2_types.h $(top_srcdir)/lib/ext2fs/ext2fs.h \ + $(top_srcdir)/lib/ext2fs/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \ + $(top_srcdir)/lib/ext2fs/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \ + $(top_srcdir)/lib/ext2fs/ext2_ext_attr.h $(top_srcdir)/lib/ext2fs/hashmap.h \ + $(top_srcdir)/lib/ext2fs/bitops.h $(top_srcdir)/lib/e2p/e2p.h \ + $(srcdir)/quotaio.h $(srcdir)/dqblk_v2.h $(srcdir)/quotaio_tree.h \ + $(srcdir)/quotaio_v2.h $(srcdir)/common.h $(srcdir)/dict.h +parse_qtype.o: $(srcdir)/parse_qtype.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(srcdir)/quotaio.h \ + $(top_srcdir)/lib/ext2fs/ext2_fs.h $(top_builddir)/lib/ext2fs/ext2_types.h \ + $(top_srcdir)/lib/ext2fs/ext2fs.h $(top_srcdir)/lib/ext2fs/ext3_extents.h \ + $(top_srcdir)/lib/et/com_err.h $(top_srcdir)/lib/ext2fs/ext2_io.h \ + $(top_builddir)/lib/ext2fs/ext2_err.h \ + $(top_srcdir)/lib/ext2fs/ext2_ext_attr.h $(top_srcdir)/lib/ext2fs/hashmap.h \ + $(top_srcdir)/lib/ext2fs/bitops.h $(srcdir)/dqblk_v2.h \ + $(srcdir)/quotaio_tree.h +plausible.o: $(srcdir)/plausible.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(srcdir)/plausible.h \ + $(top_srcdir)/lib/ext2fs/ext2fs.h $(top_builddir)/lib/ext2fs/ext2_types.h \ + $(top_srcdir)/lib/ext2fs/ext2_fs.h $(top_srcdir)/lib/ext2fs/ext3_extents.h \ + $(top_srcdir)/lib/et/com_err.h $(top_srcdir)/lib/ext2fs/ext2_io.h \ + $(top_builddir)/lib/ext2fs/ext2_err.h \ + $(top_srcdir)/lib/ext2fs/ext2_ext_attr.h $(top_srcdir)/lib/ext2fs/hashmap.h \ + $(top_srcdir)/lib/ext2fs/bitops.h $(srcdir)/nls-enable.h +print_fs_flags.o: $(srcdir)/print_fs_flags.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(top_srcdir)/lib/ext2fs/ext2fs.h \ + $(top_builddir)/lib/ext2fs/ext2_types.h $(top_srcdir)/lib/ext2fs/ext2_fs.h \ + $(top_srcdir)/lib/ext2fs/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \ + $(top_srcdir)/lib/ext2fs/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \ + $(top_srcdir)/lib/ext2fs/ext2_ext_attr.h $(top_srcdir)/lib/ext2fs/hashmap.h \ + $(top_srcdir)/lib/ext2fs/bitops.h +profile.o: $(srcdir)/profile.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(top_srcdir)/lib/et/com_err.h \ + $(srcdir)/profile.h prof_err.h +profile_helpers.o: $(srcdir)/profile_helpers.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(top_srcdir)/lib/et/com_err.h \ + $(srcdir)/profile.h $(srcdir)/profile_helpers.h prof_err.h +prof_err.o: prof_err.c +quotaio.o: $(srcdir)/quotaio.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(srcdir)/common.h \ + $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/quotaio.h \ + $(top_srcdir)/lib/ext2fs/ext2_fs.h $(top_srcdir)/lib/ext2fs/ext2fs.h \ + $(top_srcdir)/lib/ext2fs/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \ + $(top_srcdir)/lib/ext2fs/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \ + $(top_srcdir)/lib/ext2fs/ext2_ext_attr.h $(top_srcdir)/lib/ext2fs/hashmap.h \ + $(top_srcdir)/lib/ext2fs/bitops.h $(srcdir)/dqblk_v2.h \ + $(srcdir)/quotaio_tree.h +quotaio_tree.o: $(srcdir)/quotaio_tree.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(srcdir)/common.h \ + $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/quotaio_tree.h \ + $(srcdir)/quotaio.h $(top_srcdir)/lib/ext2fs/ext2_fs.h \ + $(top_srcdir)/lib/ext2fs/ext2fs.h $(top_srcdir)/lib/ext2fs/ext3_extents.h \ + $(top_srcdir)/lib/et/com_err.h $(top_srcdir)/lib/ext2fs/ext2_io.h \ + $(top_builddir)/lib/ext2fs/ext2_err.h \ + $(top_srcdir)/lib/ext2fs/ext2_ext_attr.h $(top_srcdir)/lib/ext2fs/hashmap.h \ + $(top_srcdir)/lib/ext2fs/bitops.h $(srcdir)/dqblk_v2.h +quotaio_v2.o: $(srcdir)/quotaio_v2.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(srcdir)/common.h \ + $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/quotaio_v2.h \ + $(srcdir)/quotaio.h $(top_srcdir)/lib/ext2fs/ext2_fs.h \ + $(top_srcdir)/lib/ext2fs/ext2fs.h $(top_srcdir)/lib/ext2fs/ext3_extents.h \ + $(top_srcdir)/lib/et/com_err.h $(top_srcdir)/lib/ext2fs/ext2_io.h \ + $(top_builddir)/lib/ext2fs/ext2_err.h \ + $(top_srcdir)/lib/ext2fs/ext2_ext_attr.h $(top_srcdir)/lib/ext2fs/hashmap.h \ + $(top_srcdir)/lib/ext2fs/bitops.h $(srcdir)/dqblk_v2.h \ + $(srcdir)/quotaio_tree.h +dict.o: $(srcdir)/dict.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(srcdir)/dict.h +devname.o: $(srcdir)/devname.c $(top_builddir)/lib/config.h \ + $(top_builddir)/lib/dirpaths.h $(srcdir)/devname.h $(srcdir)/nls-enable.h diff --git a/lib/support/argv_parse.c b/lib/support/argv_parse.c new file mode 100644 index 0000000..1f50f9e --- /dev/null +++ b/lib/support/argv_parse.c @@ -0,0 +1,168 @@ +/* + * argv_parse.c --- utility function for parsing a string into a + * argc, argv array. + * + * This file defines a function argv_parse() which parsing a + * passed-in string, handling double quotes and backslashes, and + * creates an allocated argv vector which can be freed using the + * argv_free() function. + * + * See argv_parse.h for the formal definition of the functions. + * + * Copyright 1999 by Theodore Ts'o. + * + * Permission to use, copy, modify, and distribute this software for + * any purpose with or without fee is hereby granted, provided that + * the above copyright notice and this permission notice appear in all + * copies. THE SOFTWARE IS PROVIDED "AS IS" AND THEODORE TS'O (THE + * AUTHOR) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, + * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER + * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR + * IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. (Isn't + * it sick that the U.S. culture of lawsuit-happy lawyers requires + * this kind of disclaimer?) + * + * Version 1.1, modified 2/27/1999 + */ + +#include "config.h" +#ifdef HAVE_STDLIB_H +#include +#endif +#include +#include +#include "argv_parse.h" + +#define STATE_WHITESPACE 1 +#define STATE_TOKEN 2 +#define STATE_QUOTED 3 + +/* + * Returns 0 on success, -1 on failure. + */ +int argv_parse(char *in_buf, int *ret_argc, char ***ret_argv) +{ + int argc = 0, max_argc = 0; + char **argv, **new_argv, *buf, ch; + char *cp = 0, *outcp = 0; + int state = STATE_WHITESPACE; + + buf = malloc(strlen(in_buf)+1); + if (!buf) + return -1; + + max_argc = 0; argc = 0; argv = 0; + outcp = buf; + for (cp = in_buf; (ch = *cp); cp++) { + if (state == STATE_WHITESPACE) { + if (isspace((int) ch)) + continue; + /* Not whitespace, so start a new token */ + state = STATE_TOKEN; + if (argc >= max_argc) { + max_argc += 3; + new_argv = realloc(argv, + (max_argc+1)*sizeof(char *)); + if (!new_argv) { + free(argv); + free(buf); + return -1; + } + argv = new_argv; + } + argv[argc++] = outcp; + } + if (state == STATE_QUOTED) { + if (ch == '"') + state = STATE_TOKEN; + else + *outcp++ = ch; + continue; + } + /* Must be processing characters in a word */ + if (isspace((int) ch)) { + /* + * Terminate the current word and start + * looking for the beginning of the next word. + */ + *outcp++ = 0; + state = STATE_WHITESPACE; + continue; + } + if (ch == '"') { + state = STATE_QUOTED; + continue; + } + if (ch == '\\') { + ch = *++cp; + switch (ch) { + case '\0': + ch = '\\'; cp--; break; + case 'n': + ch = '\n'; break; + case 't': + ch = '\t'; break; + case 'b': + ch = '\b'; break; + } + } + *outcp++ = ch; + } + if (state != STATE_WHITESPACE) + *outcp++ = '\0'; + if (argv == 0) { + argv = malloc(sizeof(char *)); + free(buf); + if (!argv) + return -1; + } + argv[argc] = 0; + if (ret_argc) + *ret_argc = argc; + if (ret_argv) + *ret_argv = argv; + return 0; +} + +void argv_free(char **argv) +{ + free(*argv); + free(argv); +} + +#ifdef DEBUG +/* + * For debugging + */ + +#include + +int main(int argc, char **argv) +{ + int ac, ret; + char **av, **cpp; + char buf[256]; + + while (!feof(stdin)) { + if (fgets(buf, sizeof(buf), stdin) == NULL) + break; + ret = argv_parse(buf, &ac, &av); + if (ret != 0) { + printf("Argv_parse returned %d!\n", ret); + continue; + } + printf("Argv_parse returned %d arguments...\n", ac); + for (cpp = av; *cpp; cpp++) { + if (cpp != av) + printf(", "); + printf("'%s'", *cpp); + } + printf("\n"); + argv_free(av); + } + exit(0); +} +#endif /* DEBUG */ diff --git a/lib/support/argv_parse.h b/lib/support/argv_parse.h new file mode 100644 index 0000000..86f4564 --- /dev/null +++ b/lib/support/argv_parse.h @@ -0,0 +1,43 @@ +/* + * argv_parse.h --- header file for the argv parser. + * + * This file defines the interface for the functions argv_parse() and + * argv_free(). + * + *********************************************************************** + * int argv_parse(char *in_buf, int *ret_argc, char ***ret_argv) + * + * This function takes as its first argument a string which it will + * parse into an argv argument vector, with each white-space separated + * word placed into its own slot in the argv. This function handles + * double quotes and backslashes so that the parsed words can contain + * special characters. The count of the number words found in the + * parsed string, as well as the argument vector, are returned into + * ret_argc and ret_argv, respectively. + *********************************************************************** + * extern void argv_free(char **argv); + * + * This function frees the argument vector created by argv_parse(). + *********************************************************************** + * + * Copyright 1999 by Theodore Ts'o. + * + * Permission to use, copy, modify, and distribute this software for + * any purpose with or without fee is hereby granted, provided that + * the above copyright notice and this permission notice appear in all + * copies. THE SOFTWARE IS PROVIDED "AS IS" AND THEODORE TS'O (THE + * AUTHOR) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, + * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER + * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR + * IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. (Isn't + * it sick that the U.S. culture of lawsuit-happy lawyers requires + * this kind of disclaimer?) + * + * Version 1.1, modified 2/27/1999 + */ + +extern int argv_parse(char *in_buf, int *ret_argc, char ***ret_argv); +extern void argv_free(char **argv); diff --git a/lib/support/common.h b/lib/support/common.h new file mode 100644 index 0000000..00a9375 --- /dev/null +++ b/lib/support/common.h @@ -0,0 +1,36 @@ +/* + * + * Various things common for all utilities + * + */ + +#ifndef __QUOTA_COMMON_H__ +#define __QUOTA_COMMON_H__ + +#if EXT2_FLAT_INCLUDES +#include "e2_types.h" +#else +#include +#endif /* EXT2_FLAT_INCLUDES */ + +/* #define DEBUG_QUOTA 1 */ + +#ifndef __attribute__ +# if !defined __GNUC__ || __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__ +# define __attribute__(x) +# endif +#endif + +#define log_err(format, arg ...) \ + fprintf(stderr, "[ERROR] %s:%d:%s: " format "\n", \ + __FILE__, __LINE__, __func__, ## arg) + +#ifdef DEBUG_QUOTA +# define log_debug(format, arg ...) \ + fprintf(stderr, "[DEBUG] %s:%d:%s: " format "\n", \ + __FILE__, __LINE__, __func__, ## arg) +#else +# define log_debug(...) +#endif + +#endif /* __QUOTA_COMMON_H__ */ diff --git a/lib/support/cstring.c b/lib/support/cstring.c new file mode 100644 index 0000000..57f4522 --- /dev/null +++ b/lib/support/cstring.c @@ -0,0 +1,162 @@ +/* + * cstring.c -- parse and print strings using the C escape sequences + */ + +#include "config.h" +#include +#include +#include +#ifdef HAVE_GETOPT_H +#include +#endif +#include + +#include "cstring.h" + +int parse_c_string(char *str) +{ + char *to, *from, ch; + int v; + + to = from = str; + + for (to = from = (char *) str; + *from && *from != '"'; to++, from++) { + if (*from == '\\') { + ch = *(++from); + switch (ch) { + case 'a': + *to = '\a'; + break; + case 'b': + *to = '\b'; + break; + case 'f': + *to = '\f'; + break; + case 'n': + *to = '\n'; + break; + case 't': + *to = '\t'; + break; + case 'v': + *to = '\v'; + break; + case 'x': + ch = *(from + 1); + if (ch >= 'a' && ch <= 'f') + ch = ch - 'a' + 'A'; + if (ch >= '0' && ch <= '9') + v = ch - '0'; + else if (ch >= 'A' && ch <= 'F') + v = ch + 10 - 'A'; + else { + *to = 'x'; + break; + } + from++; + ch = *(from + 1); + if (ch >= 'a' && ch <= 'f') + ch = ch - 'a' + 'A'; + if (ch >= '0' && ch <= '9') + v = (v * 16) + (ch - '0'); + else if (ch >= 'A' && ch <= 'F') + v = (v * 16) + (ch + 10 - 'A'); + else { + *to = 'x'; + from--; + break; + } + from++; + *to = v; + break; + default: + if (ch >= '0' && ch <= '9') { + v = ch - '0'; + ch = *(from + 1); + if (ch >= '0' && ch <= '9') { + from++; + v = (8 * v) + (ch - '0'); + ch = *(from + 1); + if (ch >= '0' && ch <= '9') { + from++; + v = (8 * v) + (ch - '0'); + } + } + ch = v; + } + *to = ch; + } + continue; + } + *to = *from; + } + *to = '\0'; + return to - (char *) str; +} + +void print_c_string(FILE *f, const char *cp, int len) +{ + unsigned char ch; + + if (len < 0) + len = strlen(cp); + + while (len--) { + ch = *cp++; + if (ch == '\a') + fputs("\\a", f); + else if (ch == '\b') + fputs("\\b", f); + else if (ch == '\f') + fputs("\\f", f); + else if (ch == '\n') + fputs("\\n", f); + else if (ch == '\t') + fputs("\\t", f); + else if (ch == '\v') + fputs("\\v", f); + else if (ch == '\\') + fputs("\\\\", f); + else if (ch == '\'') + fputs("\\\'", f); + else if (ch == '\"') + fputs("\\\"", f); + else if ((ch < 32) || (ch > 126)) + fprintf(f, "\\%03o", ch); + else + fputc(ch, f); + } +} + +#ifdef DEBUG_PROGRAM +int main(int argc, char **argv) +{ + char buf[4096]; + int c, raw = 0; + + while ((c = getopt(argc, argv, "r")) != EOF) { + switch (c) { + case 'r': + raw++; + break; + default: + fprintf(stderr, "Usage: %s [-r]\n", argv[0]); + exit(1); + } + } + + while (!feof(stdin)) { + if (fgets(buf, sizeof(buf), stdin) == NULL) + break; + c = parse_c_string(buf); + if (raw) + fputs(buf, stdout); + else { + print_c_string(stdout, buf, c); + printf(" <%d>\n", c); + } + } +} +#endif diff --git a/lib/support/cstring.h b/lib/support/cstring.h new file mode 100644 index 0000000..7f80f41 --- /dev/null +++ b/lib/support/cstring.h @@ -0,0 +1,6 @@ +/* + * cstring.h -- header file for C string parse/print utilities + */ + +extern int parse_c_string(char *str); +extern void print_c_string(FILE *f, const char *cp, int len); diff --git a/lib/support/devname.c b/lib/support/devname.c new file mode 100644 index 0000000..e0306dd --- /dev/null +++ b/lib/support/devname.c @@ -0,0 +1,65 @@ +/* + * devname.c --- Support function to translate a user provided string + * identifying a device to an actual device path + * + * Copyright (C) 2022 Red Hat, Inc., Lukas Czerner + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +#include +#include +#include + +#include "config.h" +#include "devname.h" +#include "nls-enable.h" + +/* + * blkid_get_devname() is primarily intended for parsing "NAME=value" + * tokens. It will return the device matching the specified token, NULL if + * nothing is found, or copy of the string if it's not in "NAME=value" + * format. + * get_devname() takes the same parameters and works the same way as + * blkid_get_devname() except it can handle '=' in the file name. + */ +char *get_devname(blkid_cache cache, const char *token, const char *value) +{ + int is_file = 0; + char *ret = NULL; + + if (!token) + goto out; + + if (value) { + ret = blkid_get_devname(cache, token, value); + goto out; + } + + if (access(token, F_OK) == 0) + is_file = 1; + + ret = blkid_get_devname(cache, token, NULL); + if (ret) { + /* + * In case of collision prefer the result from + * blkid_get_devname() to avoid a file masking file system with + * existing tag. + */ + if (is_file && (strcmp(ret, token) != 0)) { + fprintf(stderr, + _("Collision found: '%s' refers to both '%s' " + "and a file '%s'. Using '%s'!\n"), + token, ret, token, ret); + } + goto out; + } + + if (is_file) + ret = strdup(token); +out: + return ret; +} diff --git a/lib/support/devname.h b/lib/support/devname.h new file mode 100644 index 0000000..cc19561 --- /dev/null +++ b/lib/support/devname.h @@ -0,0 +1,19 @@ +/* + * devname.c --- Figure out if a pathname is ext* or something else. + * + * Copyright (C) 2022 Red Hat, Inc., Lukas Czerner + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +#ifndef DEVNAME_H_ +#define DEVNAME_H_ + +#include "blkid/blkid.h" + +char *get_devname(blkid_cache cache, const char *token, const char *value); + +#endif /* DEVNAME_H_ */ diff --git a/lib/support/dict.c b/lib/support/dict.c new file mode 100644 index 0000000..93fdd0b --- /dev/null +++ b/lib/support/dict.c @@ -0,0 +1,1542 @@ +/* + * Dictionary Abstract Data Type + * Copyright (C) 1997 Kaz Kylheku + * + * Free Software License: + * + * All rights are reserved by the author, with the following exceptions: + * Permission is granted to freely reproduce and distribute this software, + * possibly in exchange for a fee, provided that this copyright notice appears + * intact. Permission is also granted to adapt this software to produce + * derivative works, as long as the modified versions carry this copyright + * notice and additional notices stating that the work has been modified. + * This source code may be translated into executable form and incorporated + * into proprietary software; there is no requirement for such software to + * contain a copyright notice related to this source. + * + * $Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $ + * $Name: kazlib_1_20 $ + * The work has been modified. + */ + +#define DICT_NODEBUG + +#ifdef __GNUC__ +#define EXT2FS_ATTR(x) __attribute__(x) +#else +#define EXT2FS_ATTR(x) +#endif + +#include "config.h" +#include +#include +#ifdef DICT_NODEBUG +#define dict_assert(x) +#else +#include +#define dict_assert(x) assert(x) +#endif +#define DICT_IMPLEMENTATION +#include "dict.h" + +#ifdef KAZLIB_RCSID +static const char rcsid[] = "$Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $"; +#endif + +/* + * These macros provide short convenient names for structure members, + * which are embellished with dict_ prefixes so that they are + * properly confined to the documented namespace. It's legal for a + * program which uses dict to define, for instance, a macro called ``parent''. + * Such a macro would interfere with the dnode_t struct definition. + * In general, highly portable and reusable C modules which expose their + * structures need to confine structure member names to well-defined spaces. + * The resulting identifiers aren't necessarily convenient to use, nor + * readable, in the implementation, however! + */ + +#define left dict_left +#define right dict_right +#define parent dict_parent +#define color dict_color +#define key dict_key +#define data dict_data + +#define nilnode dict_nilnode +#define nodecount dict_nodecount +#define maxcount dict_maxcount +#define compare dict_compare +#define allocnode dict_allocnode +#define freenode dict_freenode +#define context dict_context +#define dupes dict_dupes + +#define dictptr dict_dictptr + +#define dict_root(D) ((D)->nilnode.left) +#define dict_nil(D) (&(D)->nilnode) +#define DICT_DEPTH_MAX 64 + +static dnode_t *dnode_alloc(void *context); +static void dnode_free(dnode_t *node, void *context); + +/* + * Perform a ``left rotation'' adjustment on the tree. The given node P and + * its right child C are rearranged so that the P instead becomes the left + * child of C. The left subtree of C is inherited as the new right subtree + * for P. The ordering of the keys within the tree is thus preserved. + */ + +static void rotate_left(dnode_t *upper) +{ + dnode_t *lower, *lowleft, *upparent; + + lower = upper->right; + upper->right = lowleft = lower->left; + lowleft->parent = upper; + + lower->parent = upparent = upper->parent; + + /* don't need to check for root node here because root->parent is + the sentinel nil node, and root->parent->left points back to root */ + + if (upper == upparent->left) { + upparent->left = lower; + } else { + dict_assert (upper == upparent->right); + upparent->right = lower; + } + + lower->left = upper; + upper->parent = lower; +} + +/* + * This operation is the ``mirror'' image of rotate_left. It is + * the same procedure, but with left and right interchanged. + */ + +static void rotate_right(dnode_t *upper) +{ + dnode_t *lower, *lowright, *upparent; + + lower = upper->left; + upper->left = lowright = lower->right; + lowright->parent = upper; + + lower->parent = upparent = upper->parent; + + if (upper == upparent->right) { + upparent->right = lower; + } else { + dict_assert (upper == upparent->left); + upparent->left = lower; + } + + lower->right = upper; + upper->parent = lower; +} + +/* + * Do a postorder traversal of the tree rooted at the specified + * node and free everything under it. Used by dict_free(). + */ + +static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil) +{ + if (node == nil) + return; + free_nodes(dict, node->left, nil); + free_nodes(dict, node->right, nil); + dict->freenode(node, dict->context); +} + +/* + * This procedure performs a verification that the given subtree is a binary + * search tree. It performs an inorder traversal of the tree using the + * dict_next() successor function, verifying that the key of each node is + * strictly lower than that of its successor, if duplicates are not allowed, + * or lower or equal if duplicates are allowed. This function is used for + * debugging purposes. + */ +#ifndef DICT_NODEBUG +static int verify_bintree(dict_t *dict) +{ + dnode_t *first, *next; + + first = dict_first(dict); + + if (dict->dupes) { + while (first && (next = dict_next(dict, first))) { + if (dict->compare(first->key, next->key) > 0) + return 0; + first = next; + } + } else { + while (first && (next = dict_next(dict, first))) { + if (dict->compare(first->key, next->key) >= 0) + return 0; + first = next; + } + } + return 1; +} + +/* + * This function recursively verifies that the given binary subtree satisfies + * three of the red black properties. It checks that every red node has only + * black children. It makes sure that each node is either red or black. And it + * checks that every path has the same count of black nodes from root to leaf. + * It returns the blackheight of the given subtree; this allows blackheights to + * be computed recursively and compared for left and right siblings for + * mismatches. It does not check for every nil node being black, because there + * is only one sentinel nil node. The return value of this function is the + * black height of the subtree rooted at the node ``root'', or zero if the + * subtree is not red-black. + */ + +static unsigned int verify_redblack(dnode_t *nil, dnode_t *root) +{ + unsigned height_left, height_right; + + if (root != nil) { + height_left = verify_redblack(nil, root->left); + height_right = verify_redblack(nil, root->right); + if (height_left == 0 || height_right == 0) + return 0; + if (height_left != height_right) + return 0; + if (root->color == dnode_red) { + if (root->left->color != dnode_black) + return 0; + if (root->right->color != dnode_black) + return 0; + return height_left; + } + if (root->color != dnode_black) + return 0; + return height_left + 1; + } + return 1; +} + +/* + * Compute the actual count of nodes by traversing the tree and + * return it. This could be compared against the stored count to + * detect a mismatch. + */ + +static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root) +{ + if (root == nil) + return 0; + else + return 1 + verify_node_count(nil, root->left) + + verify_node_count(nil, root->right); +} +#endif + +/* + * Verify that the tree contains the given node. This is done by + * traversing all of the nodes and comparing their pointers to the + * given pointer. Returns 1 if the node is found, otherwise + * returns zero. It is intended for debugging purposes. + */ + +static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node) +{ + if (root != nil) { + return root == node + || verify_dict_has_node(nil, root->left, node) + || verify_dict_has_node(nil, root->right, node); + } + return 0; +} + + +#ifdef E2FSCK_NOTUSED +/* + * Dynamically allocate and initialize a dictionary object. + */ + +dict_t *dict_create(dictcount_t maxcount, dict_comp_t comp) +{ + dict_t *new = malloc(sizeof *new); + + if (new) { + new->compare = comp; + new->allocnode = dnode_alloc; + new->freenode = dnode_free; + new->context = NULL; + new->cmp_ctx = NULL; + new->nodecount = 0; + new->maxcount = maxcount; + new->nilnode.left = &new->nilnode; + new->nilnode.right = &new->nilnode; + new->nilnode.parent = &new->nilnode; + new->nilnode.color = dnode_black; + new->dupes = 0; + } + return new; +} +#endif /* E2FSCK_NOTUSED */ + +/* + * Select a different set of node allocator routines. + */ + +void dict_set_allocator(dict_t *dict, dnode_alloc_t al, + dnode_free_t fr, void *context) +{ + dict_assert (dict_count(dict) == 0); + dict_assert ((al == NULL && fr == NULL) || (al != NULL && fr != NULL)); + + dict->allocnode = al ? al : dnode_alloc; + dict->freenode = fr ? fr : dnode_free; + dict->context = context; +} + +void dict_set_cmp_context(dict_t *dict, const void *cmp_ctx) +{ + dict_assert (!dict->cmp_ctx); + dict_assert (dict_count(dict) == 0); + + dict->cmp_ctx = cmp_ctx; +} + +#ifdef E2FSCK_NOTUSED +/* + * Free a dynamically allocated dictionary object. Removing the nodes + * from the tree before deleting it is required. + */ + +void dict_destroy(dict_t *dict) +{ + dict_assert (dict_isempty(dict)); + free(dict); +} +#endif + +/* + * Free all the nodes in the dictionary by using the dictionary's + * installed free routine. The dictionary is emptied. + */ + +void dict_free_nodes(dict_t *dict) +{ + dnode_t *nil = dict_nil(dict), *root = dict_root(dict); + free_nodes(dict, root, nil); + dict->nodecount = 0; + dict->nilnode.left = &dict->nilnode; + dict->nilnode.right = &dict->nilnode; +} + +#ifdef E2FSCK_NOTUSED +/* + * Obsolescent function, equivalent to dict_free_nodes + */ +void dict_free(dict_t *dict) +{ +#ifdef KAZLIB_OBSOLESCENT_DEBUG + dict_assert ("call to obsolescent function dict_free()" && 0); +#endif + dict_free_nodes(dict); +} +#endif + +/* + * Initialize a user-supplied dictionary object. + */ + +dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp) +{ + dict->compare = comp; + dict->allocnode = dnode_alloc; + dict->freenode = dnode_free; + dict->context = NULL; + dict->nodecount = 0; + dict->maxcount = maxcount; + dict->nilnode.left = &dict->nilnode; + dict->nilnode.right = &dict->nilnode; + dict->nilnode.parent = &dict->nilnode; + dict->nilnode.color = dnode_black; + dict->dupes = 0; + return dict; +} + +#ifdef E2FSCK_NOTUSED +/* + * Initialize a dictionary in the likeness of another dictionary + */ + +void dict_init_like(dict_t *dict, const dict_t *template) +{ + dict->compare = template->compare; + dict->allocnode = template->allocnode; + dict->freenode = template->freenode; + dict->context = template->context; + dict->nodecount = 0; + dict->maxcount = template->maxcount; + dict->nilnode.left = &dict->nilnode; + dict->nilnode.right = &dict->nilnode; + dict->nilnode.parent = &dict->nilnode; + dict->nilnode.color = dnode_black; + dict->dupes = template->dupes; + + dict_assert (dict_similar(dict, template)); +} + +/* + * Remove all nodes from the dictionary (without freeing them in any way). + */ + +static void dict_clear(dict_t *dict) +{ + dict->nodecount = 0; + dict->nilnode.left = &dict->nilnode; + dict->nilnode.right = &dict->nilnode; + dict->nilnode.parent = &dict->nilnode; + dict_assert (dict->nilnode.color == dnode_black); +} +#endif /* E2FSCK_NOTUSED */ + + +/* + * Verify the integrity of the dictionary structure. This is provided for + * debugging purposes, and should be placed in assert statements. Just because + * this function succeeds doesn't mean that the tree is not corrupt. Certain + * corruptions in the tree may simply cause undefined behavior. + */ +#ifndef DICT_NODEBUG +int dict_verify(dict_t *dict) +{ + dnode_t *nil = dict_nil(dict), *root = dict_root(dict); + + /* check that the sentinel node and root node are black */ + if (root->color != dnode_black) + return 0; + if (nil->color != dnode_black) + return 0; + if (nil->right != nil) + return 0; + /* nil->left is the root node; check that its parent pointer is nil */ + if (nil->left->parent != nil) + return 0; + /* perform a weak test that the tree is a binary search tree */ + if (!verify_bintree(dict)) + return 0; + /* verify that the tree is a red-black tree */ + if (!verify_redblack(nil, root)) + return 0; + if (verify_node_count(nil, root) != dict_count(dict)) + return 0; + return 1; +} +#endif /* DICT_NODEBUG */ + +#ifdef E2FSCK_NOTUSED +/* + * Determine whether two dictionaries are similar: have the same comparison and + * allocator functions, and same status as to whether duplicates are allowed. + */ +int dict_similar(const dict_t *left, const dict_t *right) +{ + if (left->compare != right->compare) + return 0; + + if (left->allocnode != right->allocnode) + return 0; + + if (left->freenode != right->freenode) + return 0; + + if (left->context != right->context) + return 0; + + if (left->dupes != right->dupes) + return 0; + + return 1; +} +#endif /* E2FSCK_NOTUSED */ + +/* + * Locate a node in the dictionary having the given key. + * If the node is not found, a null a pointer is returned (rather than + * a pointer that dictionary's nil sentinel node), otherwise a pointer to the + * located node is returned. + */ + +dnode_t *dict_lookup(dict_t *dict, const void *key) +{ + dnode_t *root = dict_root(dict); + dnode_t *nil = dict_nil(dict); + dnode_t *saved; + int result; + + /* simple binary search adapted for trees that contain duplicate keys */ + + while (root != nil) { + result = dict->compare(dict->cmp_ctx, key, root->key); + if (result < 0) + root = root->left; + else if (result > 0) + root = root->right; + else { + if (!dict->dupes) { /* no duplicates, return match */ + return root; + } else { /* could be dupes, find leftmost one */ + do { + saved = root; + root = root->left; + while (root != nil + && dict->compare(dict->cmp_ctx, key, root->key)) + root = root->right; + } while (root != nil); + return saved; + } + } + } + + return NULL; +} + +#ifdef E2FSCK_NOTUSED +/* + * Look for the node corresponding to the lowest key that is equal to or + * greater than the given key. If there is no such node, return null. + */ + +dnode_t *dict_lower_bound(dict_t *dict, const void *key) +{ + dnode_t *root = dict_root(dict); + dnode_t *nil = dict_nil(dict); + dnode_t *tentative = 0; + + while (root != nil) { + int result = dict->compare(dict->cmp_ctx, key, root->key); + + if (result > 0) { + root = root->right; + } else if (result < 0) { + tentative = root; + root = root->left; + } else { + if (!dict->dupes) { + return root; + } else { + tentative = root; + root = root->left; + } + } + } + + return tentative; +} + +/* + * Look for the node corresponding to the greatest key that is equal to or + * lower than the given key. If there is no such node, return null. + */ + +dnode_t *dict_upper_bound(dict_t *dict, const void *key) +{ + dnode_t *root = dict_root(dict); + dnode_t *nil = dict_nil(dict); + dnode_t *tentative = 0; + + while (root != nil) { + int result = dict->compare(dict->cmp_ctx, key, root->key); + + if (result < 0) { + root = root->left; + } else if (result > 0) { + tentative = root; + root = root->right; + } else { + if (!dict->dupes) { + return root; + } else { + tentative = root; + root = root->right; + } + } + } + + return tentative; +} +#endif + +/* + * Insert a node into the dictionary. The node should have been + * initialized with a data field. All other fields are ignored. + * The behavior is undefined if the user attempts to insert into + * a dictionary that is already full (for which the dict_isfull() + * function returns true). + */ + +void dict_insert(dict_t *dict, dnode_t *node, const void *key) +{ + dnode_t *where = dict_root(dict), *nil = dict_nil(dict); + dnode_t *parent = nil, *uncle, *grandpa; + int result = -1; + + node->key = key; + + dict_assert (!dict_isfull(dict)); + dict_assert (!dict_contains(dict, node)); + dict_assert (!dnode_is_in_a_dict(node)); + + /* basic binary tree insert */ + + while (where != nil) { + parent = where; + result = dict->compare(dict->cmp_ctx, key, where->key); + /* trap attempts at duplicate key insertion unless it's explicitly allowed */ + dict_assert (dict->dupes || result != 0); + if (result < 0) + where = where->left; + else + where = where->right; + } + + dict_assert (where == nil); + + if (result < 0) + parent->left = node; + else + parent->right = node; + + node->parent = parent; + node->left = nil; + node->right = nil; + + dict->nodecount++; + + /* red black adjustments */ + + node->color = dnode_red; + + while (parent->color == dnode_red) { + grandpa = parent->parent; + if (parent == grandpa->left) { + uncle = grandpa->right; + if (uncle->color == dnode_red) { /* red parent, red uncle */ + parent->color = dnode_black; + uncle->color = dnode_black; + grandpa->color = dnode_red; + node = grandpa; + parent = grandpa->parent; + } else { /* red parent, black uncle */ + if (node == parent->right) { + rotate_left(parent); + parent = node; + dict_assert (grandpa == parent->parent); + /* rotation between parent and child preserves grandpa */ + } + parent->color = dnode_black; + grandpa->color = dnode_red; + rotate_right(grandpa); + break; + } + } else { /* symmetric cases: parent == parent->parent->right */ + uncle = grandpa->left; + if (uncle->color == dnode_red) { + parent->color = dnode_black; + uncle->color = dnode_black; + grandpa->color = dnode_red; + node = grandpa; + parent = grandpa->parent; + } else { + if (node == parent->left) { + rotate_right(parent); + parent = node; + dict_assert (grandpa == parent->parent); + } + parent->color = dnode_black; + grandpa->color = dnode_red; + rotate_left(grandpa); + break; + } + } + } + + dict_root(dict)->color = dnode_black; + + dict_assert (dict_verify(dict)); +} + +#ifdef E2FSCK_NOTUSED +/* + * Delete the given node from the dictionary. If the given node does not belong + * to the given dictionary, undefined behavior results. A pointer to the + * deleted node is returned. + */ + +dnode_t *dict_delete(dict_t *dict, dnode_t *delete) +{ + dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent; + + /* basic deletion */ + + dict_assert (!dict_isempty(dict)); + dict_assert (dict_contains(dict, delete)); + + /* + * If the node being deleted has two children, then we replace it with its + * successor (i.e. the leftmost node in the right subtree.) By doing this, + * we avoid the traditional algorithm under which the successor's key and + * value *only* move to the deleted node and the successor is spliced out + * from the tree. We cannot use this approach because the user may hold + * pointers to the successor, or nodes may be inextricably tied to some + * other structures by way of embedding, etc. So we must splice out the + * node we are given, not some other node, and must not move contents from + * one node to another behind the user's back. + */ + + if (delete->left != nil && delete->right != nil) { + dnode_t *next = dict_next(dict, delete); + dnode_t *nextparent = next->parent; + dnode_color_t nextcolor = next->color; + + dict_assert (next != nil); + dict_assert (next->parent != nil); + dict_assert (next->left == nil); + + /* + * First, splice out the successor from the tree completely, by + * moving up its right child into its place. + */ + + child = next->right; + child->parent = nextparent; + + if (nextparent->left == next) { + nextparent->left = child; + } else { + dict_assert (nextparent->right == next); + nextparent->right = child; + } + + /* + * Now that the successor has been extricated from the tree, install it + * in place of the node that we want deleted. + */ + + next->parent = delparent; + next->left = delete->left; + next->right = delete->right; + next->left->parent = next; + next->right->parent = next; + next->color = delete->color; + delete->color = nextcolor; + + if (delparent->left == delete) { + delparent->left = next; + } else { + dict_assert (delparent->right == delete); + delparent->right = next; + } + + } else { + dict_assert (delete != nil); + dict_assert (delete->left == nil || delete->right == nil); + + child = (delete->left != nil) ? delete->left : delete->right; + + child->parent = delparent = delete->parent; + + if (delete == delparent->left) { + delparent->left = child; + } else { + dict_assert (delete == delparent->right); + delparent->right = child; + } + } + + delete->parent = NULL; + delete->right = NULL; + delete->left = NULL; + + dict->nodecount--; + + dict_assert (verify_bintree(dict)); + + /* red-black adjustments */ + + if (delete->color == dnode_black) { + dnode_t *parent, *sister; + + dict_root(dict)->color = dnode_red; + + while (child->color == dnode_black) { + parent = child->parent; + if (child == parent->left) { + sister = parent->right; + dict_assert (sister != nil); + if (sister->color == dnode_red) { + sister->color = dnode_black; + parent->color = dnode_red; + rotate_left(parent); + sister = parent->right; + dict_assert (sister != nil); + } + if (sister->left->color == dnode_black + && sister->right->color == dnode_black) { + sister->color = dnode_red; + child = parent; + } else { + if (sister->right->color == dnode_black) { + dict_assert (sister->left->color == dnode_red); + sister->left->color = dnode_black; + sister->color = dnode_red; + rotate_right(sister); + sister = parent->right; + dict_assert (sister != nil); + } + sister->color = parent->color; + sister->right->color = dnode_black; + parent->color = dnode_black; + rotate_left(parent); + break; + } + } else { /* symmetric case: child == child->parent->right */ + dict_assert (child == parent->right); + sister = parent->left; + dict_assert (sister != nil); + if (sister->color == dnode_red) { + sister->color = dnode_black; + parent->color = dnode_red; + rotate_right(parent); + sister = parent->left; + dict_assert (sister != nil); + } + if (sister->right->color == dnode_black + && sister->left->color == dnode_black) { + sister->color = dnode_red; + child = parent; + } else { + if (sister->left->color == dnode_black) { + dict_assert (sister->right->color == dnode_red); + sister->right->color = dnode_black; + sister->color = dnode_red; + rotate_left(sister); + sister = parent->left; + dict_assert (sister != nil); + } + sister->color = parent->color; + sister->left->color = dnode_black; + parent->color = dnode_black; + rotate_right(parent); + break; + } + } + } + + child->color = dnode_black; + dict_root(dict)->color = dnode_black; + } + + dict_assert (dict_verify(dict)); + + return delete; +} +#endif /* E2FSCK_NOTUSED */ + +/* + * Allocate a node using the dictionary's allocator routine, give it + * the data item. + */ + +int dict_alloc_insert(dict_t *dict, const void *key, void *data) +{ + dnode_t *node = dict->allocnode(dict->context); + + if (node) { + dnode_init(node, data); + dict_insert(dict, node, key); + return 1; + } + return 0; +} + +#ifdef E2FSCK_NOTUSED +void dict_delete_free(dict_t *dict, dnode_t *node) +{ + dict_delete(dict, node); + dict->freenode(node, dict->context); +} +#endif + +/* + * Return the node with the lowest (leftmost) key. If the dictionary is empty + * (that is, dict_isempty(dict) returns 1) a null pointer is returned. + */ + +dnode_t *dict_first(dict_t *dict) +{ + dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left; + + if (root != nil) + while ((left = root->left) != nil) + root = left; + + return (root == nil) ? NULL : root; +} + +/* + * Return the node with the highest (rightmost) key. If the dictionary is empty + * (that is, dict_isempty(dict) returns 1) a null pointer is returned. + */ + +dnode_t *dict_last(dict_t *dict) +{ + dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right; + + if (root != nil) + while ((right = root->right) != nil) + root = right; + + return (root == nil) ? NULL : root; +} + +/* + * Return the given node's successor node---the node which has the + * next key in the the left to right ordering. If the node has + * no successor, a null pointer is returned rather than a pointer to + * the nil node. + */ + +dnode_t *dict_next(dict_t *dict, dnode_t *curr) +{ + dnode_t *nil = dict_nil(dict), *parent, *left; + + if (curr->right != nil) { + curr = curr->right; + while ((left = curr->left) != nil) + curr = left; + return curr; + } + + parent = curr->parent; + + while (parent != nil && curr == parent->right) { + curr = parent; + parent = curr->parent; + } + + return (parent == nil) ? NULL : parent; +} + +/* + * Return the given node's predecessor, in the key order. + * The nil sentinel node is returned if there is no predecessor. + */ + +dnode_t *dict_prev(dict_t *dict, dnode_t *curr) +{ + dnode_t *nil = dict_nil(dict), *parent, *right; + + if (curr->left != nil) { + curr = curr->left; + while ((right = curr->right) != nil) + curr = right; + return curr; + } + + parent = curr->parent; + + while (parent != nil && curr == parent->left) { + curr = parent; + parent = curr->parent; + } + + return (parent == nil) ? NULL : parent; +} + +void dict_allow_dupes(dict_t *dict) +{ + dict->dupes = 1; +} + +#undef dict_count +#undef dict_isempty +#undef dict_isfull +#undef dnode_get +#undef dnode_put +#undef dnode_getkey + +dictcount_t dict_count(dict_t *dict) +{ + return dict->nodecount; +} + +int dict_isempty(dict_t *dict) +{ + return dict->nodecount == 0; +} + +int dict_isfull(dict_t *dict) +{ + return dict->nodecount == dict->maxcount; +} + +int dict_contains(dict_t *dict, dnode_t *node) +{ + return verify_dict_has_node(dict_nil(dict), dict_root(dict), node); +} + +static dnode_t *dnode_alloc(void *context EXT2FS_ATTR((unused))) +{ + return malloc(sizeof *dnode_alloc(NULL)); +} + +static void dnode_free(dnode_t *node, void *context EXT2FS_ATTR((unused))) +{ + free(node); +} + +dnode_t *dnode_create(void *data) +{ + dnode_t *new = malloc(sizeof *new); + if (new) { + new->data = data; + new->parent = NULL; + new->left = NULL; + new->right = NULL; + } + return new; +} + +dnode_t *dnode_init(dnode_t *dnode, void *data) +{ + dnode->data = data; + dnode->parent = NULL; + dnode->left = NULL; + dnode->right = NULL; + return dnode; +} + +void dnode_destroy(dnode_t *dnode) +{ + dict_assert (!dnode_is_in_a_dict(dnode)); + free(dnode); +} + +void *dnode_get(dnode_t *dnode) +{ + return dnode->data; +} + +const void *dnode_getkey(dnode_t *dnode) +{ + return dnode->key; +} + +#ifdef E2FSCK_NOTUSED +void dnode_put(dnode_t *dnode, void *data) +{ + dnode->data = data; +} +#endif + +#ifndef DICT_NODEBUG +int dnode_is_in_a_dict(dnode_t *dnode) +{ + return (dnode->parent && dnode->left && dnode->right); +} +#endif + +#ifdef E2FSCK_NOTUSED +void dict_process(dict_t *dict, void *context, dnode_process_t function) +{ + dnode_t *node = dict_first(dict), *next; + + while (node != NULL) { + /* check for callback function deleting */ + /* the next node from under us */ + dict_assert (dict_contains(dict, node)); + next = dict_next(dict, node); + function(dict, node, context); + node = next; + } +} + +static void load_begin_internal(dict_load_t *load, dict_t *dict) +{ + load->dictptr = dict; + load->nilnode.left = &load->nilnode; + load->nilnode.right = &load->nilnode; +} + +void dict_load_begin(dict_load_t *load, dict_t *dict) +{ + dict_assert (dict_isempty(dict)); + load_begin_internal(load, dict); +} + +void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key) +{ + dict_t *dict = load->dictptr; + dnode_t *nil = &load->nilnode; + + dict_assert (!dnode_is_in_a_dict(newnode)); + dict_assert (dict->nodecount < dict->maxcount); + +#ifndef DICT_NODEBUG + if (dict->nodecount > 0) { + if (dict->dupes) + dict_assert (dict->compare(nil->left->key, key) <= 0); + else + dict_assert (dict->compare(nil->left->key, key) < 0); + } +#endif + + newnode->key = key; + nil->right->left = newnode; + nil->right = newnode; + newnode->left = nil; + dict->nodecount++; +} + +void dict_load_end(dict_load_t *load) +{ + dict_t *dict = load->dictptr; + dnode_t *tree[DICT_DEPTH_MAX] = { 0 }; + dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next; + dnode_t *complete = 0; + dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount; + dictcount_t botrowcount; + unsigned baselevel = 0, level = 0, i; + + dict_assert (dnode_red == 0 && dnode_black == 1); + + while (fullcount >= nodecount && fullcount) + fullcount >>= 1; + + botrowcount = nodecount - fullcount; + + for (curr = loadnil->left; curr != loadnil; curr = next) { + next = curr->left; + + if (complete == NULL && botrowcount-- == 0) { + dict_assert (baselevel == 0); + dict_assert (level == 0); + baselevel = level = 1; + complete = tree[0]; + + if (complete != 0) { + tree[0] = 0; + complete->right = dictnil; + while (tree[level] != 0) { + tree[level]->right = complete; + complete->parent = tree[level]; + complete = tree[level]; + tree[level++] = 0; + } + } + } + + if (complete == NULL) { + curr->left = dictnil; + curr->right = dictnil; + curr->color = level % 2; + complete = curr; + + dict_assert (level == baselevel); + while (tree[level] != 0) { + tree[level]->right = complete; + complete->parent = tree[level]; + complete = tree[level]; + tree[level++] = 0; + } + } else { + curr->left = complete; + curr->color = (level + 1) % 2; + complete->parent = curr; + tree[level] = curr; + complete = 0; + level = baselevel; + } + } + + if (complete == NULL) + complete = dictnil; + + for (i = 0; i < DICT_DEPTH_MAX; i++) { + if (tree[i] != 0) { + tree[i]->right = complete; + complete->parent = tree[i]; + complete = tree[i]; + } + } + + dictnil->color = dnode_black; + dictnil->right = dictnil; + complete->parent = dictnil; + complete->color = dnode_black; + dict_root(dict) = complete; + + dict_assert (dict_verify(dict)); +} + +void dict_merge(dict_t *dest, dict_t *source) +{ + dict_load_t load; + dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source); + + dict_assert (dict_similar(dest, source)); + + if (source == dest) + return; + + dest->nodecount = 0; + load_begin_internal(&load, dest); + + for (;;) { + if (leftnode != NULL && rightnode != NULL) { + if (dest->compare(leftnode->key, rightnode->key) < 0) + goto copyleft; + else + goto copyright; + } else if (leftnode != NULL) { + goto copyleft; + } else if (rightnode != NULL) { + goto copyright; + } else { + dict_assert (leftnode == NULL && rightnode == NULL); + break; + } + + copyleft: + { + dnode_t *next = dict_next(dest, leftnode); +#ifndef DICT_NODEBUG + leftnode->left = NULL; /* suppress assertion in dict_load_next */ +#endif + dict_load_next(&load, leftnode, leftnode->key); + leftnode = next; + continue; + } + + copyright: + { + dnode_t *next = dict_next(source, rightnode); +#ifndef DICT_NODEBUG + rightnode->left = NULL; +#endif + dict_load_next(&load, rightnode, rightnode->key); + rightnode = next; + continue; + } + } + + dict_clear(source); + dict_load_end(&load); +} +#endif /* E2FSCK_NOTUSED */ + +#ifdef KAZLIB_TEST_MAIN + +#include +#include +#include +#include + +typedef char input_t[256]; + +static int tokenize(char *string, ...) +{ + char **tokptr; + va_list arglist; + int tokcount = 0; + + va_start(arglist, string); + tokptr = va_arg(arglist, char **); + while (tokptr) { + while (*string && isspace((unsigned char) *string)) + string++; + if (!*string) + break; + *tokptr = string; + while (*string && !isspace((unsigned char) *string)) + string++; + tokptr = va_arg(arglist, char **); + tokcount++; + if (!*string) + break; + *string++ = 0; + } + va_end(arglist); + + return tokcount; +} + +static int comparef(const void *cmp_ctx, const void *key1, const void *key2) +{ + return strcmp(key1, key2); +} + +static char *dupstring(char *str) +{ + int sz = strlen(str) + 1; + char *new = malloc(sz); + if (new) + memcpy(new, str, sz); + return new; +} + +static dnode_t *new_node(void *c) +{ + static dnode_t few[5]; + static int count; + + if (count < 5) + return few + count++; + + return NULL; +} + +static void del_node(dnode_t *n, void *c) +{ +} + +static int prompt = 0; + +static void construct(dict_t *d) +{ + input_t in; + int done = 0; + dict_load_t dl; + dnode_t *dn; + char *tok1, *tok2, *val; + const char *key; + char *help = + "p turn prompt on\n" + "q finish construction\n" + "a add new entry\n"; + + if (!dict_isempty(d)) + puts("warning: dictionary not empty!"); + + dict_load_begin(&dl, d); + + while (!done) { + if (prompt) + putchar('>'); + fflush(stdout); + + if (!fgets(in, sizeof(input_t), stdin)) + break; + + switch (in[0]) { + case '?': + puts(help); + break; + case 'p': + prompt = 1; + break; + case 'q': + done = 1; + break; + case 'a': + if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { + puts("what?"); + break; + } + key = dupstring(tok1); + val = dupstring(tok2); + dn = dnode_create(val); + + if (!key || !val || !dn) { + puts("out of memory"); + free((void *) key); + free(val); + if (dn) + dnode_destroy(dn); + } + + dict_load_next(&dl, dn, key); + break; + default: + putchar('?'); + putchar('\n'); + break; + } + } + + dict_load_end(&dl); +} + +int main(void) +{ + input_t in; + dict_t darray[10]; + dict_t *d = &darray[0]; + dnode_t *dn; + int i; + char *tok1, *tok2, *val; + const char *key; + + char *help = + "a add value to dictionary\n" + "d delete value from dictionary\n" + "l lookup value in dictionary\n" + "( lookup lower bound\n" + ") lookup upper bound\n" + "# switch to alternate dictionary (0-9)\n" + "j merge two dictionaries\n" + "f free the whole dictionary\n" + "k allow duplicate keys\n" + "c show number of entries\n" + "t dump whole dictionary in sort order\n" + "m make dictionary out of sorted items\n" + "p turn prompt on\n" + "s switch to non-functioning allocator\n" + "q quit"; + + for (i = 0; i < sizeof darray / sizeof *darray; i++) + dict_init(&darray[i], DICTCOUNT_T_MAX, comparef); + + for (;;) { + if (prompt) + putchar('>'); + fflush(stdout); + + if (!fgets(in, sizeof(input_t), stdin)) + break; + + switch(in[0]) { + case '?': + puts(help); + break; + case 'a': + if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { + puts("what?"); + break; + } + key = dupstring(tok1); + val = dupstring(tok2); + + if (!key || !val) { + puts("out of memory"); + free((void *) key); + free(val); + } + + if (!dict_alloc_insert(d, key, val)) { + puts("dict_alloc_insert failed"); + free((void *) key); + free(val); + break; + } + break; + case 'd': + if (tokenize(in+1, &tok1, (char **) 0) != 1) { + puts("what?"); + break; + } + dn = dict_lookup(d, tok1); + if (!dn) { + puts("dict_lookup failed"); + break; + } + val = dnode_get(dn); + key = dnode_getkey(dn); + dict_delete_free(d, dn); + + free(val); + free((void *) key); + break; + case 'f': + dict_free(d); + break; + case 'l': + case '(': + case ')': + if (tokenize(in+1, &tok1, (char **) 0) != 1) { + puts("what?"); + break; + } + dn = 0; + switch (in[0]) { + case 'l': + dn = dict_lookup(d, tok1); + break; + case '(': + dn = dict_lower_bound(d, tok1); + break; + case ')': + dn = dict_upper_bound(d, tok1); + break; + } + if (!dn) { + puts("lookup failed"); + break; + } + val = dnode_get(dn); + puts(val); + break; + case 'm': + construct(d); + break; + case 'k': + dict_allow_dupes(d); + break; + case 'c': + printf("%lu\n", (unsigned long) dict_count(d)); + break; + case 't': + for (dn = dict_first(d); dn; dn = dict_next(d, dn)) { + printf("%s\t%s\n", (char *) dnode_getkey(dn), + (char *) dnode_get(dn)); + } + break; + case 'q': + exit(0); + break; + case '\0': + break; + case 'p': + prompt = 1; + break; + case 's': + dict_set_allocator(d, new_node, del_node, NULL); + break; + case '#': + if (tokenize(in+1, &tok1, (char **) 0) != 1) { + puts("what?"); + break; + } else { + int dictnum = atoi(tok1); + if (dictnum < 0 || dictnum > 9) { + puts("invalid number"); + break; + } + d = &darray[dictnum]; + } + break; + case 'j': + if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { + puts("what?"); + break; + } else { + int dict1 = atoi(tok1), dict2 = atoi(tok2); + if (dict1 < 0 || dict1 > 9 || dict2 < 0 || dict2 > 9) { + puts("invalid number"); + break; + } + dict_merge(&darray[dict1], &darray[dict2]); + } + break; + default: + putchar('?'); + putchar('\n'); + break; + } + } + + return 0; +} + +#endif diff --git a/lib/support/dict.h b/lib/support/dict.h new file mode 100644 index 0000000..2d87cc0 --- /dev/null +++ b/lib/support/dict.h @@ -0,0 +1,147 @@ +/* + * Dictionary Abstract Data Type + * Copyright (C) 1997 Kaz Kylheku + * + * Free Software License: + * + * All rights are reserved by the author, with the following exceptions: + * Permission is granted to freely reproduce and distribute this software, + * possibly in exchange for a fee, provided that this copyright notice appears + * intact. Permission is also granted to adapt this software to produce + * derivative works, as long as the modified versions carry this copyright + * notice and additional notices stating that the work has been modified. + * This source code may be translated into executable form and incorporated + * into proprietary software; there is no requirement for such software to + * contain a copyright notice related to this source. + * + * $Id: dict.h,v 1.22.2.6 2000/11/13 01:36:44 kaz Exp $ + * $Name: kazlib_1_20 $ + * The work has been modified. + */ + +#ifndef DICT_H +#define DICT_H + +#include +#ifdef KAZLIB_SIDEEFFECT_DEBUG +#include "sfx.h" +#endif + +/* + * Blurb for inclusion into C++ translation units + */ + +#ifdef __cplusplus +extern "C" { +#endif + +typedef unsigned long dictcount_t; +#define DICTCOUNT_T_MAX ULONG_MAX + +/* + * The dictionary is implemented as a red-black tree + */ + +typedef enum { dnode_red, dnode_black } dnode_color_t; + +typedef struct dnode_t { +#if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) + struct dnode_t *dict_left; + struct dnode_t *dict_right; + struct dnode_t *dict_parent; + dnode_color_t dict_color; + const void *dict_key; + void *dict_data; +#else + int dict_dummy; +#endif +} dnode_t; + +typedef int (*dict_comp_t)(const void *, const void *, const void *); +typedef dnode_t *(*dnode_alloc_t)(void *); +typedef void (*dnode_free_t)(dnode_t *, void *); + +typedef struct dict_t { +#if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) + dnode_t dict_nilnode; + dictcount_t dict_nodecount; + dictcount_t dict_maxcount; + dict_comp_t dict_compare; + dnode_alloc_t dict_allocnode; + dnode_free_t dict_freenode; + void *dict_context; + const void *cmp_ctx; + int dict_dupes; +#else + int dict_dummmy; +#endif +} dict_t; + +typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *); + +typedef struct dict_load_t { +#if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) + dict_t *dict_dictptr; + dnode_t dict_nilnode; +#else + int dict_dummmy; +#endif +} dict_load_t; + +extern dict_t *dict_create(dictcount_t, dict_comp_t); +extern void dict_set_allocator(dict_t *, dnode_alloc_t, dnode_free_t, void *); +extern void dict_set_cmp_context(dict_t *, const void *); +extern void dict_destroy(dict_t *); +extern void dict_free_nodes(dict_t *); +extern void dict_free(dict_t *); +extern dict_t *dict_init(dict_t *, dictcount_t, dict_comp_t); +extern void dict_init_like(dict_t *, const dict_t *); +extern int dict_verify(dict_t *); +extern int dict_similar(const dict_t *, const dict_t *); +extern dnode_t *dict_lookup(dict_t *, const void *); +extern dnode_t *dict_lower_bound(dict_t *, const void *); +extern dnode_t *dict_upper_bound(dict_t *, const void *); +extern void dict_insert(dict_t *, dnode_t *, const void *); +extern dnode_t *dict_delete(dict_t *, dnode_t *); +extern int dict_alloc_insert(dict_t *, const void *, void *); +extern void dict_delete_free(dict_t *, dnode_t *); +extern dnode_t *dict_first(dict_t *); +extern dnode_t *dict_last(dict_t *); +extern dnode_t *dict_next(dict_t *, dnode_t *); +extern dnode_t *dict_prev(dict_t *, dnode_t *); +extern dictcount_t dict_count(dict_t *); +extern int dict_isempty(dict_t *); +extern int dict_isfull(dict_t *); +extern int dict_contains(dict_t *, dnode_t *); +extern void dict_allow_dupes(dict_t *); +extern int dnode_is_in_a_dict(dnode_t *); +extern dnode_t *dnode_create(void *); +extern dnode_t *dnode_init(dnode_t *, void *); +extern void dnode_destroy(dnode_t *); +extern void *dnode_get(dnode_t *); +extern const void *dnode_getkey(dnode_t *); +extern void dnode_put(dnode_t *, void *); +extern void dict_process(dict_t *, void *, dnode_process_t); +extern void dict_load_begin(dict_load_t *, dict_t *); +extern void dict_load_next(dict_load_t *, dnode_t *, const void *); +extern void dict_load_end(dict_load_t *); +extern void dict_merge(dict_t *, dict_t *); + +#if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) +#ifdef KAZLIB_SIDEEFFECT_DEBUG +#define dict_isfull(D) (SFX_CHECK(D)->dict_nodecount == (D)->dict_maxcount) +#else +#define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount) +#endif +#define dict_count(D) ((D)->dict_nodecount) +#define dict_isempty(D) ((D)->dict_nodecount == 0) +#define dnode_get(N) ((N)->dict_data) +#define dnode_getkey(N) ((N)->dict_key) +#define dnode_put(N, X) ((N)->dict_data = (X)) +#endif + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/lib/support/dqblk_v2.h b/lib/support/dqblk_v2.h new file mode 100644 index 0000000..d12512a --- /dev/null +++ b/lib/support/dqblk_v2.h @@ -0,0 +1,31 @@ +/* + * Header file for disk format of new quotafile format + * + * Jan Kara - sponsored by SuSE CR + */ + +#ifndef __QUOTA_DQBLK_V2_H__ +#define __QUOTA_DQBLK_V2_H__ + +#include "quotaio_tree.h" + +/* Structure for format specific information */ +struct v2_mem_dqinfo { + struct qtree_mem_dqinfo dqi_qtree; + unsigned int dqi_flags; /* Flags set in quotafile */ + unsigned int dqi_used_entries; /* Number of entries in file - + updated by scan_dquots */ + unsigned int dqi_data_blocks; /* Number of data blocks in file - + updated by scan_dquots */ +}; + +struct v2_mem_dqblk { + long long dqb_off; /* Offset of dquot in file */ +}; + +struct quotafile_ops; /* Will be defined later in quotaio.h */ + +/* Operations above this format */ +extern struct quotafile_ops quotafile_ops_2; + +#endif /* __QUOTA_DQBLK_V2_H__ */ diff --git a/lib/support/mkquota.c b/lib/support/mkquota.c new file mode 100644 index 0000000..9339c99 --- /dev/null +++ b/lib/support/mkquota.c @@ -0,0 +1,707 @@ +/* + * mkquota.c --- create quota files for a filesystem + * + * Aditya Kali + */ +#include "config.h" +#include +#include +#include +#include +#include +#include + +#include "ext2fs/ext2_fs.h" +#include "ext2fs/ext2fs.h" +#include "e2p/e2p.h" + +#include "quotaio.h" +#include "quotaio_v2.h" +#include "quotaio_tree.h" +#include "common.h" +#include "dict.h" + +/* Needed for architectures where sizeof(int) != sizeof(void *) */ +#define UINT_TO_VOIDPTR(val) ((void *)(intptr_t)(val)) +#define VOIDPTR_TO_UINT(ptr) ((unsigned int)(intptr_t)(ptr)) + +#if DEBUG_QUOTA +static void print_inode(struct ext2_inode *inode) +{ + if (!inode) + return; + + fprintf(stderr, " i_mode = %d\n", inode->i_mode); + fprintf(stderr, " i_uid = %d\n", inode->i_uid); + fprintf(stderr, " i_size = %d\n", inode->i_size); + fprintf(stderr, " i_atime = %d\n", inode->i_atime); + fprintf(stderr, " i_ctime = %d\n", inode->i_ctime); + fprintf(stderr, " i_mtime = %d\n", inode->i_mtime); + fprintf(stderr, " i_dtime = %d\n", inode->i_dtime); + fprintf(stderr, " i_gid = %d\n", inode->i_gid); + fprintf(stderr, " i_links_count = %d\n", inode->i_links_count); + fprintf(stderr, " i_blocks = %d\n", inode->i_blocks); + fprintf(stderr, " i_flags = %d\n", inode->i_flags); + + return; +} + +static void print_dquot(const char *desc, struct dquot *dq) +{ + if (desc) + fprintf(stderr, "%s: ", desc); + fprintf(stderr, "%u %lld:%lld:%lld %lld:%lld:%lld\n", + dq->dq_id, (long long) dq->dq_dqb.dqb_curspace, + (long long) dq->dq_dqb.dqb_bsoftlimit, + (long long) dq->dq_dqb.dqb_bhardlimit, + (long long) dq->dq_dqb.dqb_curinodes, + (long long) dq->dq_dqb.dqb_isoftlimit, + (long long) dq->dq_dqb.dqb_ihardlimit); +} +#else +static void print_dquot(const char *desc EXT2FS_ATTR((unused)), + struct dquot *dq EXT2FS_ATTR((unused))) +{ +} +#endif + +/* + * Returns 0 if not able to find the quota file, otherwise returns its + * inode number. + */ +int quota_file_exists(ext2_filsys fs, enum quota_type qtype) +{ + char qf_name[256]; + errcode_t ret; + ext2_ino_t ino; + + if (qtype >= MAXQUOTAS) + return -EINVAL; + + quota_get_qf_name(qtype, QFMT_VFS_V1, qf_name); + + ret = ext2fs_lookup(fs, EXT2_ROOT_INO, qf_name, strlen(qf_name), 0, + &ino); + if (ret) + return 0; + + return ino; +} + +/* + * Set the value for reserved quota inode number field in superblock. + */ +void quota_set_sb_inum(ext2_filsys fs, ext2_ino_t ino, enum quota_type qtype) +{ + ext2_ino_t *inump; + + inump = quota_sb_inump(fs->super, qtype); + + log_debug("setting quota ino in superblock: ino=%u, type=%d", ino, + qtype); + if (inump == NULL) + return; + *inump = ino; + ext2fs_mark_super_dirty(fs); +} + +errcode_t quota_remove_inode(ext2_filsys fs, enum quota_type qtype) +{ + ext2_ino_t qf_ino; + errcode_t retval; + + retval = ext2fs_read_bitmaps(fs); + if (retval) { + log_debug("Couldn't read bitmaps: %s", error_message(retval)); + return retval; + } + + qf_ino = *quota_sb_inump(fs->super, qtype); + if (qf_ino == 0) + return 0; + retval = quota_inode_truncate(fs, qf_ino); + if (retval) + return retval; + if (qf_ino >= EXT2_FIRST_INODE(fs->super)) { + struct ext2_inode inode; + + retval = ext2fs_read_inode(fs, qf_ino, &inode); + if (!retval) { + memset(&inode, 0, sizeof(struct ext2_inode)); + ext2fs_write_inode(fs, qf_ino, &inode); + } + ext2fs_inode_alloc_stats2(fs, qf_ino, -1, 0); + ext2fs_mark_ib_dirty(fs); + + } + quota_set_sb_inum(fs, 0, qtype); + + ext2fs_mark_super_dirty(fs); + fs->flags &= ~EXT2_FLAG_SUPER_ONLY; + retval = ext2fs_write_bitmaps(fs); + if (retval) { + log_debug("Couldn't write bitmaps: %s", error_message(retval)); + return retval; + } + return 0; +} + +static void write_dquots(dict_t *dict, struct quota_handle *qh) +{ + dnode_t *n; + struct dquot *dq; + + for (n = dict_first(dict); n; n = dict_next(dict, n)) { + dq = dnode_get(n); + if (dq) { + print_dquot("write", dq); + dq->dq_h = qh; + update_grace_times(dq); + qh->qh_ops->commit_dquot(dq); + } + } +} + +errcode_t quota_write_inode(quota_ctx_t qctx, unsigned int qtype_bits) +{ + int retval = 0; + enum quota_type qtype; + dict_t *dict; + ext2_filsys fs; + struct quota_handle *h = NULL; + int fmt = QFMT_VFS_V1; + + if (!qctx) + return 0; + + fs = qctx->fs; + retval = ext2fs_get_mem(sizeof(struct quota_handle), &h); + if (retval) { + log_debug("Unable to allocate quota handle: %s", + error_message(retval)); + goto out; + } + + retval = ext2fs_read_bitmaps(fs); + if (retval) { + log_debug("Couldn't read bitmaps: %s", error_message(retval)); + goto out; + } + + for (qtype = 0; qtype < MAXQUOTAS; qtype++) { + if (((1 << qtype) & qtype_bits) == 0) + continue; + + dict = qctx->quota_dict[qtype]; + if (!dict) + continue; + + retval = quota_file_create(h, fs, qtype, fmt); + if (retval) { + log_debug("Cannot initialize io on quotafile: %s", + error_message(retval)); + goto out; + } + + write_dquots(dict, h); + retval = quota_file_close(qctx, h); + if (retval) { + log_debug("Cannot finish IO on new quotafile: %s", + strerror(errno)); + if (h->qh_qf.e2_file) + ext2fs_file_close(h->qh_qf.e2_file); + (void) quota_inode_truncate(fs, h->qh_qf.ino); + goto out; + } + + /* Set quota inode numbers in superblock. */ + quota_set_sb_inum(fs, h->qh_qf.ino, qtype); + ext2fs_mark_super_dirty(fs); + ext2fs_mark_bb_dirty(fs); + fs->flags &= ~EXT2_FLAG_SUPER_ONLY; + } + + retval = ext2fs_write_bitmaps(fs); + if (retval) { + log_debug("Couldn't write bitmaps: %s", error_message(retval)); + goto out; + } +out: + if (h) + ext2fs_free_mem(&h); + return retval; +} + +/******************************************************************/ +/* Helper functions for computing quota in memory. */ +/******************************************************************/ + +static int dict_uint_cmp(const void *cmp_ctx EXT2FS_ATTR((unused)), + const void *a, const void *b) +{ + unsigned int c, d; + + c = VOIDPTR_TO_UINT(a); + d = VOIDPTR_TO_UINT(b); + + if (c == d) + return 0; + else if (c > d) + return 1; + else + return -1; +} + +static inline int project_quota_valid(quota_ctx_t qctx) +{ + return (EXT2_INODE_SIZE(qctx->fs->super) > EXT2_GOOD_OLD_INODE_SIZE); +} + +static inline qid_t get_qid(struct ext2_inode_large *inode, enum quota_type qtype) +{ + unsigned int inode_size; + + switch (qtype) { + case USRQUOTA: + return inode_uid(*inode); + case GRPQUOTA: + return inode_gid(*inode); + case PRJQUOTA: + inode_size = EXT2_GOOD_OLD_INODE_SIZE + + inode->i_extra_isize; + if (inode_includes(inode_size, i_projid)) + return inode_projid(*inode); + return 0; + default: + return 0; + } + + return 0; +} + +static void quota_dnode_free(dnode_t *node, + void *context EXT2FS_ATTR((unused))) +{ + void *ptr = node ? dnode_get(node) : 0; + + ext2fs_free_mem(&ptr); + free(node); +} + +/* + * Set up the quota tracking data structures. + */ +errcode_t quota_init_context(quota_ctx_t *qctx, ext2_filsys fs, + unsigned int qtype_bits) +{ + errcode_t err; + dict_t *dict; + quota_ctx_t ctx; + enum quota_type qtype; + + err = ext2fs_get_mem(sizeof(struct quota_ctx), &ctx); + if (err) { + log_debug("Failed to allocate quota context"); + return err; + } + + memset(ctx, 0, sizeof(struct quota_ctx)); + for (qtype = 0; qtype < MAXQUOTAS; qtype++) { + ctx->quota_file[qtype] = NULL; + if (qtype_bits) { + if (((1 << qtype) & qtype_bits) == 0) + continue; + } else { + if (*quota_sb_inump(fs->super, qtype) == 0) + continue; + } + err = ext2fs_get_mem(sizeof(dict_t), &dict); + if (err) { + log_debug("Failed to allocate dictionary"); + quota_release_context(&ctx); + return err; + } + ctx->quota_dict[qtype] = dict; + dict_init(dict, DICTCOUNT_T_MAX, dict_uint_cmp); + dict_set_allocator(dict, NULL, quota_dnode_free, NULL); + } + + ctx->fs = fs; + *qctx = ctx; + return 0; +} + +void quota_release_context(quota_ctx_t *qctx) +{ + errcode_t err; + dict_t *dict; + enum quota_type qtype; + quota_ctx_t ctx; + + if (!qctx) + return; + + ctx = *qctx; + for (qtype = 0; qtype < MAXQUOTAS; qtype++) { + dict = ctx->quota_dict[qtype]; + ctx->quota_dict[qtype] = 0; + if (dict) { + dict_free_nodes(dict); + free(dict); + } + if (ctx->quota_file[qtype]) { + err = quota_file_close(ctx, ctx->quota_file[qtype]); + if (err) { + log_err("Cannot close quotafile: %s", + strerror(errno)); + ext2fs_free_mem(&ctx->quota_file[qtype]); + } + } + } + *qctx = NULL; + free(ctx); +} + +static struct dquot *get_dq(dict_t *dict, __u32 key) +{ + struct dquot *dq; + dnode_t *n; + + n = dict_lookup(dict, UINT_TO_VOIDPTR(key)); + if (n) + dq = dnode_get(n); + else { + if (ext2fs_get_mem(sizeof(struct dquot), &dq)) { + log_err("Unable to allocate dquot"); + return NULL; + } + memset(dq, 0, sizeof(struct dquot)); + dict_alloc_insert(dict, UINT_TO_VOIDPTR(key), dq); + dq->dq_id = key; + } + return dq; +} + + +/* + * Called to update the blocks used by a particular inode + */ +void quota_data_add(quota_ctx_t qctx, struct ext2_inode_large *inode, + ext2_ino_t ino EXT2FS_ATTR((unused)), + qsize_t space) +{ + struct dquot *dq; + dict_t *dict; + enum quota_type qtype; + + if (!qctx) + return; + + log_debug("ADD_DATA: Inode: %u, UID/GID: %u/%u, space: %ld", ino, + inode_uid(*inode), + inode_gid(*inode), space); + for (qtype = 0; qtype < MAXQUOTAS; qtype++) { + if (qtype == PRJQUOTA && !project_quota_valid(qctx)) + continue; + dict = qctx->quota_dict[qtype]; + if (dict) { + dq = get_dq(dict, get_qid(inode, qtype)); + if (dq) + dq->dq_dqb.dqb_curspace += space; + } + } +} + +/* + * Called to remove some blocks used by a particular inode + */ +void quota_data_sub(quota_ctx_t qctx, struct ext2_inode_large *inode, + ext2_ino_t ino EXT2FS_ATTR((unused)), + qsize_t space) +{ + struct dquot *dq; + dict_t *dict; + enum quota_type qtype; + + if (!qctx) + return; + + log_debug("SUB_DATA: Inode: %u, UID/GID: %u/%u, space: %ld", ino, + inode_uid(*inode), + inode_gid(*inode), space); + for (qtype = 0; qtype < MAXQUOTAS; qtype++) { + if (qtype == PRJQUOTA && !project_quota_valid(qctx)) + continue; + dict = qctx->quota_dict[qtype]; + if (dict) { + dq = get_dq(dict, get_qid(inode, qtype)); + if (dq) + dq->dq_dqb.dqb_curspace -= space; + } + } +} + +/* + * Called to count the files used by an inode's user/group + */ +void quota_data_inodes(quota_ctx_t qctx, struct ext2_inode_large *inode, + ext2_ino_t ino EXT2FS_ATTR((unused)), int adjust) +{ + struct dquot *dq; + dict_t *dict; + enum quota_type qtype; + + if (!qctx) + return; + + log_debug("ADJ_INODE: Inode: %u, UID/GID: %u/%u, adjust: %d", ino, + inode_uid(*inode), + inode_gid(*inode), adjust); + for (qtype = 0; qtype < MAXQUOTAS; qtype++) { + if (qtype == PRJQUOTA && !project_quota_valid(qctx)) + continue; + dict = qctx->quota_dict[qtype]; + if (dict) { + dq = get_dq(dict, get_qid(inode, qtype)); + if (dq) + dq->dq_dqb.dqb_curinodes += adjust; + } + } +} + +errcode_t quota_compute_usage(quota_ctx_t qctx) +{ + ext2_filsys fs; + ext2_ino_t ino; + errcode_t ret; + struct ext2_inode_large *inode; + int inode_size; + qsize_t space; + ext2_inode_scan scan; + + if (!qctx) + return 0; + + fs = qctx->fs; + ret = ext2fs_open_inode_scan(fs, 0, &scan); + if (ret) { + log_err("while opening inode scan. ret=%ld", ret); + return ret; + } + inode_size = fs->super->s_inode_size; + inode = malloc(inode_size); + if (!inode) { + ext2fs_close_inode_scan(scan); + return ENOMEM; + } + while (1) { + ret = ext2fs_get_next_inode_full(scan, &ino, + EXT2_INODE(inode), inode_size); + if (ret) { + log_err("while getting next inode. ret=%ld", ret); + ext2fs_close_inode_scan(scan); + free(inode); + return ret; + } + if (ino == 0) + break; + if (!inode->i_links_count) + continue; + if (ino == EXT2_ROOT_INO || + (ino >= EXT2_FIRST_INODE(fs->super) && + ino != quota_type2inum(PRJQUOTA, fs->super) && + ino != fs->super->s_orphan_file_inum)) { + space = ext2fs_get_stat_i_blocks(fs, + EXT2_INODE(inode)) << 9; + quota_data_add(qctx, inode, ino, space); + quota_data_inodes(qctx, inode, ino, +1); + } + } + + ext2fs_close_inode_scan(scan); + free(inode); + return 0; +} + +struct scan_dquots_data { + dict_t *quota_dict; + int update_limits; /* update limits from disk */ + int update_usage; + int check_consistency; + int usage_is_inconsistent; +}; + +static int scan_dquots_callback(struct dquot *dquot, void *cb_data) +{ + struct scan_dquots_data *scan_data = cb_data; + dict_t *quota_dict = scan_data->quota_dict; + struct dquot *dq; + + dq = get_dq(quota_dict, dquot->dq_id); + if (!dq) + return -1; + dq->dq_id = dquot->dq_id; + dq->dq_flags |= DQF_SEEN; + + print_dquot("mem", dq); + print_dquot("dsk", dquot); + + /* Check if there is inconsistency */ + if (scan_data->check_consistency && + (dq->dq_dqb.dqb_curspace != dquot->dq_dqb.dqb_curspace || + dq->dq_dqb.dqb_curinodes != dquot->dq_dqb.dqb_curinodes)) { + scan_data->usage_is_inconsistent = 1; + fprintf(stderr, "[QUOTA WARNING] Usage inconsistent for ID %u:" + "actual (%lld, %lld) != expected (%lld, %lld)\n", + dq->dq_id, (long long) dq->dq_dqb.dqb_curspace, + (long long) dq->dq_dqb.dqb_curinodes, + (long long) dquot->dq_dqb.dqb_curspace, + (long long) dquot->dq_dqb.dqb_curinodes); + } + + if (scan_data->update_limits) { + dq->dq_dqb.dqb_ihardlimit = dquot->dq_dqb.dqb_ihardlimit; + dq->dq_dqb.dqb_isoftlimit = dquot->dq_dqb.dqb_isoftlimit; + dq->dq_dqb.dqb_bhardlimit = dquot->dq_dqb.dqb_bhardlimit; + dq->dq_dqb.dqb_bsoftlimit = dquot->dq_dqb.dqb_bsoftlimit; + } + + if (scan_data->update_usage) { + dq->dq_dqb.dqb_curspace = dquot->dq_dqb.dqb_curspace; + dq->dq_dqb.dqb_curinodes = dquot->dq_dqb.dqb_curinodes; + } + + return 0; +} + +/* + * Read quotas from disk and updates the in-memory information determined by + * 'flags' from the on-disk data. + */ +errcode_t quota_read_all_dquots(quota_ctx_t qctx, ext2_ino_t qf_ino, + enum quota_type qtype, unsigned int flags) +{ + struct scan_dquots_data scan_data; + struct quota_handle *qh; + errcode_t err; + + if (!qctx) + return 0; + + err = ext2fs_get_mem(sizeof(struct quota_handle), &qh); + if (err) { + log_debug("Unable to allocate quota handle"); + return err; + } + + err = quota_file_open(qctx, qh, qf_ino, qtype, -1, 0); + if (err) { + log_debug("Open quota file failed"); + goto out; + } + + scan_data.quota_dict = qctx->quota_dict[qh->qh_type]; + scan_data.check_consistency = 0; + scan_data.update_limits = !!(flags & QREAD_LIMITS); + scan_data.update_usage = !!(flags & QREAD_USAGE); + qh->qh_ops->scan_dquots(qh, scan_dquots_callback, &scan_data); + + err = quota_file_close(qctx, qh); + if (err) { + log_debug("Cannot finish IO on new quotafile: %s", + strerror(errno)); + if (qh->qh_qf.e2_file) + ext2fs_file_close(qh->qh_qf.e2_file); + } +out: + ext2fs_free_mem(&qh); + return err; +} + +/* + * Compares the measured quota in qctx->quota_dict with that in the quota inode + * on disk and updates the limits in qctx->quota_dict. 'usage_inconsistent' is + * set to 1 if the supplied and on-disk quota usage values are not identical. + */ +errcode_t quota_compare_and_update(quota_ctx_t qctx, enum quota_type qtype, + int *usage_inconsistent) +{ + struct quota_handle qh; + struct scan_dquots_data scan_data; + struct dquot *dq; + dnode_t *n; + dict_t *dict = qctx->quota_dict[qtype]; + errcode_t err = 0; + + if (!dict) + goto out; + + err = quota_file_open(qctx, &qh, 0, qtype, -1, 0); + if (err) { + log_debug("Open quota file failed"); + goto out; + } + + scan_data.quota_dict = qctx->quota_dict[qtype]; + scan_data.update_limits = 1; + scan_data.update_usage = 0; + scan_data.check_consistency = 1; + scan_data.usage_is_inconsistent = 0; + err = qh.qh_ops->scan_dquots(&qh, scan_dquots_callback, &scan_data); + if (err) { + log_debug("Error scanning dquots"); + *usage_inconsistent = 1; + goto out_close_qh; + } + + for (n = dict_first(dict); n; n = dict_next(dict, n)) { + dq = dnode_get(n); + if (!dq) + continue; + if ((dq->dq_flags & DQF_SEEN) == 0) { + fprintf(stderr, "[QUOTA WARNING] " + "Missing quota entry ID %d\n", dq->dq_id); + scan_data.usage_is_inconsistent = 1; + } + } + *usage_inconsistent = scan_data.usage_is_inconsistent; + +out_close_qh: + err = quota_file_close(qctx, &qh); + if (err) { + log_debug("Cannot close quotafile: %s", error_message(errno)); + if (qh.qh_qf.e2_file) + ext2fs_file_close(qh.qh_qf.e2_file); + } +out: + return err; +} + +int parse_quota_opts(const char *opts, int (*func)(char *)) +{ + char *buf, *token, *next, *p; + int len; + int ret = 0; + + len = strlen(opts); + buf = malloc(len + 1); + if (!buf) { + fprintf(stderr, + "Couldn't allocate memory to parse quota options!\n"); + return -ENOMEM; + } + strcpy(buf, opts); + for (token = buf; token && *token; token = next) { + p = strchr(token, ','); + next = 0; + if (p) { + *p = 0; + next = p + 1; + } + ret = func(token); + if (ret) + break; + } + free(buf); + return ret; +} diff --git a/lib/support/nls-enable.h b/lib/support/nls-enable.h new file mode 100644 index 0000000..2f62c01 --- /dev/null +++ b/lib/support/nls-enable.h @@ -0,0 +1,21 @@ +#if defined(ENABLE_NLS) && !defined(DEBUGFS) +#include +#include +#define _(a) (gettext (a)) +#ifdef gettext_noop +#define N_(a) gettext_noop (a) +#else +#define N_(a) (a) +#endif +#define P_(singular, plural, n) (ngettext (singular, plural, n)) +#ifndef NLS_CAT_NAME +#define NLS_CAT_NAME "e2fsprogs" +#endif +#ifndef LOCALEDIR +#define LOCALEDIR "/usr/share/locale" +#endif +#else +#define _(a) (a) +#define N_(a) a +#define P_(singular, plural, n) ((n) == 1 ? (singular) : (plural)) +#endif diff --git a/lib/support/parse_qtype.c b/lib/support/parse_qtype.c new file mode 100644 index 0000000..d8df07d --- /dev/null +++ b/lib/support/parse_qtype.c @@ -0,0 +1,90 @@ +/* + * parse_qtype.c + */ + +#include "config.h" +#include +#include +#include +#include +#include +#include + +#include "quotaio.h" + +#define PARSE_DELIM ":," + +int parse_quota_types(const char *in_str, unsigned int *qtype_bits, + char **err_token) +{ + char *buf, *token, *next, *tmp; + unsigned int qtype = *qtype_bits; + int len, ret = 0; + + if (!in_str) + return 0; + + len = strlen(in_str); + buf = malloc(len + 1); + if (!buf) + return ENOMEM; + strcpy(buf, in_str); + + for (token = buf, next = strtok_r(buf, PARSE_DELIM, &tmp); + token && *token; token = next) { + int not = 0; + char *p = token; + + if (*p == '^') { + not = 1; + p++; + } + if (!strcmp(p, "usr") || !strcmp(p, "usrquota")) { + if (not) + qtype &= ~QUOTA_USR_BIT; + else + qtype |= QUOTA_USR_BIT; + } else if (!strcmp(p, "grp") || !strcmp(p, "grpquota")) { + if (not) + qtype &= ~QUOTA_GRP_BIT; + else + qtype |= QUOTA_GRP_BIT; + } else if (!strcmp(p, "prj") || !strcmp(p, "prjquota")) { + if (not) + qtype &= ~QUOTA_PRJ_BIT; + else + qtype |= QUOTA_PRJ_BIT; + } else { + if (err_token) { + *err_token = malloc(strlen(token) + 1); + if (*err_token) + strcpy(*err_token, token); + } + ret = EINVAL; + goto errout; + } +#ifdef DEBUG_PROGRAM + printf("word: %s\n", token); +#endif + next = strtok_r(NULL, PARSE_DELIM, &tmp); + } + *qtype_bits = qtype; +errout: + free(buf); + return ret; +} + +#ifdef DEBUG_PROGRAM +int main(int argc, char **argv) +{ + unsigned int qtype_bits = 0; + int ret; + char *err_token = 0; + + ret = parse_quota_types(argv[1], &qtype_bits, &err_token); + printf("parse_quota_types returns %d, %d\n", ret, qtype_bits); + if (err_token) + printf("err_token is %s\n", err_token); + return 0; +} +#endif diff --git a/lib/support/plausible.c b/lib/support/plausible.c new file mode 100644 index 0000000..65a6b2e --- /dev/null +++ b/lib/support/plausible.c @@ -0,0 +1,287 @@ +/* + * plausible.c --- Figure out if a pathname is ext* or something else. + * + * Copyright 2014, Oracle, Inc. + * + * Some parts are: + * Copyright 1995, 1996, 1997, 1998, 1999, 2000 by Theodore Ts'o. + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +#ifndef _LARGEFILE_SOURCE +#define _LARGEFILE_SOURCE +#endif +#ifndef _LARGEFILE64_SOURCE +#define _LARGEFILE64_SOURCE +#endif + +#include "config.h" +#include +#include +#include +#ifdef HAVE_SYS_STAT_H +#include +#endif +#ifdef HAVE_UNISTD_H +#include +#endif +#ifdef HAVE_MAGIC_H +#include +#endif +#include "plausible.h" +#include "ext2fs/ext2fs.h" +#include "nls-enable.h" +#include "blkid/blkid.h" + +#ifdef HAVE_MAGIC_H +static magic_t (*dl_magic_open)(int); +static const char *(*dl_magic_file)(magic_t, const char *); +static int (*dl_magic_load)(magic_t, const char *); +static void (*dl_magic_close)(magic_t); + +/* + * NO_CHECK functionality was only added in file 4.20. + * Older systems like RHEL 5.x still have file 4.17 + */ +#ifndef MAGIC_NO_CHECK_COMPRESS +#define MAGIC_NO_CHECK_COMPRESS 0x0001000 +#endif +#ifndef MAGIC_NO_CHECK_ELF +#define MAGIC_NO_CHECK_ELF 0x0010000 +#endif + +#ifdef HAVE_DLOPEN +#include + +static void *magic_handle; + +static int magic_library_available(void) +{ + if (!magic_handle) { + magic_handle = dlopen("libmagic.so.1", RTLD_NOW); + if (!magic_handle) + return 0; + + dl_magic_open = (magic_t (*)(int)) + dlsym(magic_handle, "magic_open"); + dl_magic_file = (const char *(*)(magic_t, const char *)) + dlsym(magic_handle, "magic_file"); + dl_magic_load = (int (*)(magic_t, const char *)) + dlsym(magic_handle, "magic_load"); + dl_magic_close = (void (*)(magic_t)) + dlsym(magic_handle, "magic_close"); + } + + if (!dl_magic_open || !dl_magic_file || + !dl_magic_load || !dl_magic_close) + return 0; + return 1; +} +#else +static int magic_library_available(void) +{ + dl_magic_open = magic_open; + dl_magic_file = magic_file; + dl_magic_load = magic_load; + dl_magic_close = magic_close; + + return 1; +} +#endif +#endif + +static void print_ext2_info(const char *device) + +{ + struct ext2_super_block *sb; + ext2_filsys fs; + errcode_t retval; + time_t tm; + + retval = ext2fs_open2(device, 0, EXT2_FLAG_64BITS, 0, 0, + default_io_manager, &fs); + if (retval) + return; + sb = fs->super; + + if (sb->s_mtime) { + tm = sb->s_mtime; + if (sb->s_last_mounted[0]) + printf(_("\tlast mounted on %.*s on %s"), + EXT2_LEN_STR(sb->s_last_mounted), ctime(&tm)); + else + printf(_("\tlast mounted on %s"), ctime(&tm)); + } else if (sb->s_mkfs_time) { + tm = sb->s_mkfs_time; + printf(_("\tcreated on %s"), ctime(&tm)); + } else if (sb->s_wtime) { + tm = sb->s_wtime; + printf(_("\tlast modified on %s"), ctime(&tm)); + } + ext2fs_close_free(&fs); +} + +/* + * return 1 if there is no partition table, 0 if a partition table is + * detected, and -1 on an error. + */ +#ifdef HAVE_BLKID_PROBE_ENABLE_PARTITIONS +static int check_partition_table(const char *device) +{ + blkid_probe pr; + const char *value; + int ret; + + pr = blkid_new_probe_from_filename(device); + if (!pr) + return -1; + + ret = blkid_probe_enable_partitions(pr, 1); + if (ret < 0) + goto errout; + + ret = blkid_probe_enable_superblocks(pr, 0); + if (ret < 0) + goto errout; + + ret = blkid_do_fullprobe(pr); + if (ret < 0) + goto errout; + + ret = blkid_probe_lookup_value(pr, "PTTYPE", &value, NULL); + if (ret == 0) + fprintf(stderr, _("Found a %s partition table in %s\n"), + value, device); + else + ret = 1; + +errout: + blkid_free_probe(pr); + return ret; +} +#else +static int check_partition_table(const char *device EXT2FS_ATTR((unused))) +{ + return -1; +} +#endif + +/* + * return 1 if the device looks plausible, creating the file if necessary + */ +int check_plausibility(const char *device, int flags, int *ret_is_dev) +{ + int fd, ret, is_dev = 0; + ext2fs_struct_stat s; + int fl = O_RDONLY; + blkid_cache cache = NULL; + char *fs_type = NULL; + char *fs_label = NULL; + + fd = ext2fs_open_file(device, fl, 0666); + if ((fd < 0) && (errno == ENOENT) && (flags & NO_SIZE)) { + fprintf(stderr, _("The file %s does not exist and no " + "size was specified.\n"), device); + exit(1); + } + if ((fd < 0) && (errno == ENOENT) && (flags & CREATE_FILE)) { + fl |= O_CREAT; + fd = ext2fs_open_file(device, fl, 0666); + if (fd >= 0 && (flags & VERBOSE_CREATE)) + printf(_("Creating regular file %s\n"), device); + } + if (fd < 0) { + fprintf(stderr, _("Could not open %s: %s\n"), + device, error_message(errno)); + if (errno == ENOENT) + fputs(_("\nThe device apparently does not exist; " + "did you specify it correctly?\n"), stderr); + exit(1); + } + + if (ext2fs_fstat(fd, &s) < 0) { + perror("stat"); + exit(1); + } + close(fd); + + if (S_ISBLK(s.st_mode)) + is_dev = 1; +#if defined(__FreeBSD__) || defined(__FreeBSD_kernel__) + /* On FreeBSD, all disk devices are character specials */ + if (S_ISCHR(s.st_mode)) + is_dev = 1; +#endif + if (ret_is_dev) + *ret_is_dev = is_dev; + + if ((flags & CHECK_BLOCK_DEV) && !is_dev) { + printf(_("%s is not a block special device.\n"), device); + return 0; + } + + /* + * Note: we use the older-style blkid API's here because we + * want as much functionality to be available when using the + * internal blkid library, when e2fsprogs is compiled for + * non-Linux systems that will probably not have the libraries + * from util-linux available. We only use the newer + * blkid-probe interfaces to access functionality not + * available in the original blkid library. + */ + if ((flags & CHECK_FS_EXIST) && blkid_get_cache(&cache, NULL) >= 0) { + fs_type = blkid_get_tag_value(cache, "TYPE", device); + if (fs_type) + fs_label = blkid_get_tag_value(cache, "LABEL", device); + blkid_put_cache(cache); + } + + if (fs_type) { + if (fs_label) + printf(_("%s contains a %s file system labelled '%s'\n"), + device, fs_type, fs_label); + else + printf(_("%s contains a %s file system\n"), device, + fs_type); + if (strncmp(fs_type, "ext", 3) == 0) + print_ext2_info(device); + free(fs_type); + free(fs_label); + return 0; + } + +#ifdef HAVE_MAGIC_H + if ((flags & CHECK_FS_EXIST) && + !getenv("E2FSPROGS_LIBMAGIC_SUPPRESS") && + magic_library_available()) { + const char *msg; + magic_t mag; + int has_magic = 0; + + mag = dl_magic_open(MAGIC_RAW | MAGIC_SYMLINK | MAGIC_DEVICES | + MAGIC_ERROR | MAGIC_NO_CHECK_ELF | + MAGIC_NO_CHECK_COMPRESS); + dl_magic_load(mag, NULL); + + msg = dl_magic_file(mag, device); + if (msg && strcmp(msg, "data") && strcmp(msg, "empty")) { + printf(_("%s contains `%s' data\n"), device, msg); + has_magic = 1; + } + + dl_magic_close(mag); + return !has_magic; + } +#endif + if (flags & CHECK_FS_EXIST) { + ret = check_partition_table(device); + if (ret >= 0) + return ret; + } + return 1; +} + diff --git a/lib/support/plausible.h b/lib/support/plausible.h new file mode 100644 index 0000000..b85150c --- /dev/null +++ b/lib/support/plausible.h @@ -0,0 +1,29 @@ +/* + * plausible.h --- header file defining prototypes for helper functions + * used by tune2fs and mke2fs + * + * Copyright 2014 by Oracle, Inc. + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +#ifndef PLAUSIBLE_H_ +#define PLAUSIBLE_H_ + +/* + * Flags for check_plausibility() + */ +#define CHECK_BLOCK_DEV 0x0001 +#define CREATE_FILE 0x0002 +#define CHECK_FS_EXIST 0x0004 +#define VERBOSE_CREATE 0x0008 +#define NO_SIZE 0x0010 +#define QUIET_CHECK 0x0020 + +extern int check_plausibility(const char *device, int flags, + int *ret_is_dev); + +#endif /* PLAUSIBLE_H_ */ diff --git a/lib/support/print_fs_flags.c b/lib/support/print_fs_flags.c new file mode 100644 index 0000000..f47cd66 --- /dev/null +++ b/lib/support/print_fs_flags.c @@ -0,0 +1,75 @@ +/* + * print_flags.c - Print ext2_filsys flags + * + * Copyright (C) 1993, 1994 Remy Card + * Laboratoire MASI, Institut Blaise Pascal + * Universite Pierre et Marie Curie (Paris VI) + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Library + * General Public License, version 2. + * %End-Header% + */ + +#include "config.h" +#include + +#include "ext2fs/ext2fs.h" + +struct flags_name { + unsigned long flag; + const char *name; +}; + +static const struct flags_name flags_array[] = { + { EXT2_FLAG_RW, "EXT2_FLAG_RW" }, + { EXT2_FLAG_CHANGED, "EXT2_FLAG_CHANGED" }, + { EXT2_FLAG_DIRTY, "EXT2_FLAG_DIRTY" }, + { EXT2_FLAG_VALID, "EXT2_FLAG_VALID" }, + { EXT2_FLAG_IB_DIRTY, "EXT2_FLAG_IB_DIRTY" }, + { EXT2_FLAG_BB_DIRTY, "EXT2_FLAG_BB_DIRTY" }, + { EXT2_FLAG_SWAP_BYTES, "EXT2_FLAG_SWAP_BYTES" }, + { EXT2_FLAG_SWAP_BYTES_READ, "EXT2_FLAG_SWAP_BYTES_READ" }, + { EXT2_FLAG_SWAP_BYTES_WRITE, "EXT2_FLAG_SWAP_BYTES_WRITE" }, + { EXT2_FLAG_MASTER_SB_ONLY, "EXT2_FLAG_MASTER_SB_ONLY" }, + { EXT2_FLAG_FORCE, "EXT2_FLAG_FORCE" }, + { EXT2_FLAG_SUPER_ONLY, "EXT2_FLAG_SUPER_ONLY" }, + { EXT2_FLAG_JOURNAL_DEV_OK, "EXT2_FLAG_JOURNAL_DEV_OK" }, + { EXT2_FLAG_IMAGE_FILE, "EXT2_FLAG_IMAGE_FILE" }, + { EXT2_FLAG_EXCLUSIVE, "EXT2_FLAG_EXCLUSIVE" }, + { EXT2_FLAG_SOFTSUPP_FEATURES, "EXT2_FLAG_SOFTSUPP_FEATURES" }, + { EXT2_FLAG_NOFREE_ON_ERROR, "EXT2_FLAG_NOFREE_ON_ERROR" }, + { EXT2_FLAG_64BITS, "EXT2_FLAG_64BITS" }, + { EXT2_FLAG_PRINT_PROGRESS, "EXT2_FLAG_PRINT_PROGRESS" }, + { EXT2_FLAG_DIRECT_IO, "EXT2_FLAG_DIRECT_IO" }, + { EXT2_FLAG_SKIP_MMP, "EXT2_FLAG_SKIP_MMP" }, + { EXT2_FLAG_IGNORE_CSUM_ERRORS, "EXT2_FLAG_IGNORE_CSUM_ERRORS" }, + { EXT2_FLAG_SHARE_DUP, "EXT2_FLAG_SHARE_DUP" }, + { EXT2_FLAG_IGNORE_SB_ERRORS, "EXT2_FLAG_IGNORE_SB_ERRORS" }, + { EXT2_FLAG_BBITMAP_TAIL_PROBLEM, "EXT2_FLAG_BBITMAP_TAIL_PROBLEM" }, + { EXT2_FLAG_IBITMAP_TAIL_PROBLEM, "EXT2_FLAG_IBITMAP_TAIL_PROBLEM" }, + { EXT2_FLAG_THREADS, "EXT2_FLAG_THREADS" }, + { 0, NULL }, +}; + +void print_fs_flags(FILE * f, unsigned long flags) +{ + const struct flags_name *fp; + int first = 1, pos = 16; + + for (fp = flags_array; fp->flag != 0; fp++) { + if ((flags & fp->flag) == 0) + continue; + pos += strlen(fp->name) + 1; + if (pos > 72) { + fputs("\n\t", f); + pos = 9 + strlen(fp->name); + } + if (first) + first = 0; + else + fputc(' ', f); + fputs(fp->name, f); + } + fputc('\n', f); +} diff --git a/lib/support/print_fs_flags.h b/lib/support/print_fs_flags.h new file mode 100644 index 0000000..bdd58a0 --- /dev/null +++ b/lib/support/print_fs_flags.h @@ -0,0 +1,5 @@ +/* + * print_flags.h -- header file for printing the fs flags + */ + +void print_fs_flags(FILE * f, unsigned long flags); diff --git a/lib/support/prof_err.et b/lib/support/prof_err.et new file mode 100644 index 0000000..c9316c7 --- /dev/null +++ b/lib/support/prof_err.et @@ -0,0 +1,66 @@ +error_table prof + +error_code PROF_VERSION, "Profile version 0.0" + +# +# generated by prof_tree.c +# +error_code PROF_MAGIC_NODE, "Bad magic value in profile_node" +error_code PROF_NO_SECTION, "Profile section not found" +error_code PROF_NO_RELATION, "Profile relation not found" +error_code PROF_ADD_NOT_SECTION, + "Attempt to add a relation to node which is not a section" +error_code PROF_SECTION_WITH_VALUE, + "A profile section header has a non-zero value" +error_code PROF_BAD_LINK_LIST, "Bad linked list in profile structures" +error_code PROF_BAD_GROUP_LVL, "Bad group level in profile structures" +error_code PROF_BAD_PARENT_PTR, + "Bad parent pointer in profile structures" +error_code PROF_MAGIC_ITERATOR, "Bad magic value in profile iterator" +error_code PROF_SET_SECTION_VALUE, "Can't set value on section node" +error_code PROF_EINVAL, "Invalid argument passed to profile library" +error_code PROF_READ_ONLY, "Attempt to modify read-only profile" + +# +# generated by prof_parse.c +# + +error_code PROF_SECTION_NOTOP, "Profile section header not at top level" +error_code PROF_SECTION_SYNTAX, "Syntax error in profile section header" +error_code PROF_RELATION_SYNTAX, "Syntax error in profile relation" +error_code PROF_EXTRA_CBRACE, "Extra closing brace in profile" +error_code PROF_MISSING_OBRACE, "Missing open brace in profile" + +# +# generated by prof_init.c +# +error_code PROF_MAGIC_PROFILE, "Bad magic value in profile_t" +error_code PROF_MAGIC_SECTION, "Bad magic value in profile_section_t" +error_code PROF_TOPSECTION_ITER_NOSUPP, + "Iteration through all top level section not supported" +error_code PROF_INVALID_SECTION, "Invalid profile_section object" +error_code PROF_END_OF_SECTIONS, "No more sections" +error_code PROF_BAD_NAMESET, "Bad nameset passed to query routine" +error_code PROF_NO_PROFILE, "No profile file open" + +# +# generated by prof_file.c +# +error_code PROF_MAGIC_FILE, "Bad magic value in profile_file_t" +error_code PROF_FAIL_OPEN, "Couldn't open profile file" + +# +# generated by prof_set.c +# +error_code PROF_EXISTS, "Section already exists" + +# +# generated by prof_get.c +# +error_code PROF_BAD_BOOLEAN, "Invalid boolean value" +error_code PROF_BAD_INTEGER, "Invalid integer value" + +error_code PROF_MAGIC_FILE_DATA, "Bad magic value in profile_file_data_t" + + +end diff --git a/lib/support/profile.c b/lib/support/profile.c new file mode 100644 index 0000000..bdb14b1 --- /dev/null +++ b/lib/support/profile.c @@ -0,0 +1,1910 @@ +/* + * profile.c -- A simple configuration file parsing "library in a file" + * + * The profile library was originally written by Theodore Ts'o in 1995 + * for use in the MIT Kerberos v5 library. It has been + * modified/enhanced/bug-fixed over time by other members of the MIT + * Kerberos team. This version was originally taken from the Kerberos + * v5 distribution, version 1.4.2, and radically simplified for use in + * e2fsprogs. (Support for locking for multi-threaded operations, + * being able to modify and update the configuration file + * programmatically, and Mac/Windows portability have been removed. + * It has been folded into a single C source file to make it easier to + * fold into an application program.) + * + * Copyright (C) 2005, 2006 by Theodore Ts'o. + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + * + * Copyright (C) 1985-2005 by the Massachusetts Institute of Technology. + * + * All rights reserved. + * + * Export of this software from the United States of America may require + * a specific license from the United States Government. It is the + * responsibility of any person or organization contemplating export to + * obtain such a license before exporting. + * + * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and + * distribute this software and its documentation for any purpose and + * without fee is hereby granted, provided that the above copyright + * notice appear in all copies and that both that copyright notice and + * this permission notice appear in supporting documentation, and that + * the name of M.I.T. not be used in advertising or publicity pertaining + * to distribution of the software without specific, written prior + * permission. Furthermore if you modify this software you must label + * your software as modified software and not distribute it in such a + * fashion that it might be confused with the original MIT software. + * M.I.T. makes no representations about the suitability of this software + * for any purpose. It is provided "as is" without express or implied + * warranty. + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED + * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. + * + */ + +#include "config.h" +#ifdef HAVE_UNISTD_H +#include +#endif +#include +#ifdef HAVE_STDLIB_H +#include +#endif +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#ifdef HAVE_PWD_H +#include +#endif + +#include +#include "profile.h" +#include "prof_err.h" + +#undef STAT_ONCE_PER_SECOND +#undef HAVE_STAT + +/* + * prof_int.h + */ + +typedef long prf_magic_t; + +/* + * This is the structure which stores the profile information for a + * particular configuration file. + */ +struct _prf_file_t { + prf_magic_t magic; + char *filespec; +#ifdef STAT_ONCE_PER_SECOND + time_t last_stat; +#endif + time_t timestamp; /* time tree was last updated from file */ + int flags; /* r/w, dirty */ + int upd_serial; /* incremented when data changes */ + struct profile_node *root; + struct _prf_file_t *next; +}; + +typedef struct _prf_file_t *prf_file_t; + +/* + * The profile flags + */ +#define PROFILE_FILE_RW 0x0001 +#define PROFILE_FILE_DIRTY 0x0002 +#define PROFILE_FILE_NO_RELOAD 0x0004 + +/* + * This structure defines the high-level, user visible profile_t + * object, which is used as a handle by users who need to query some + * configuration file(s) + */ +struct _profile_t { + prf_magic_t magic; + prf_file_t first_file; +}; + +/* + * Used by the profile iterator in prof_get.c + */ +#define PROFILE_ITER_LIST_SECTION 0x0001 +#define PROFILE_ITER_SECTIONS_ONLY 0x0002 +#define PROFILE_ITER_RELATIONS_ONLY 0x0004 + +#define PROFILE_ITER_FINAL_SEEN 0x0100 + +/* + * Check if a filespec is last in a list (NULL on UNIX, invalid FSSpec on MacOS + */ + +#define PROFILE_LAST_FILESPEC(x) (((x) == NULL) || ((x)[0] == '\0')) + +struct profile_node { + errcode_t magic; + char *name; + char *value; + int group_level; + unsigned int final:1; /* Indicate don't search next file */ + unsigned int deleted:1; + struct profile_node *first_child; + struct profile_node *parent; + struct profile_node *next, *prev; +}; + +#define CHECK_MAGIC(node) \ + if ((node)->magic != PROF_MAGIC_NODE) \ + return PROF_MAGIC_NODE; + +/* profile parser declarations */ +struct parse_state { + int state; + int group_level; + int line_num; + struct profile_node *root_section; + struct profile_node *current_section; +}; + +static const char *default_filename = ""; + +static profile_syntax_err_cb_t syntax_err_cb; + +static errcode_t parse_line(char *line, struct parse_state *state); + +#ifdef DEBUG_PROGRAM +static errcode_t profile_write_tree_file + (struct profile_node *root, FILE *dstfile); + +static errcode_t profile_write_tree_to_buffer + (struct profile_node *root, char **buf); +#endif + + +static void profile_free_node + (struct profile_node *relation); + +static errcode_t profile_create_node + (const char *name, const char *value, + struct profile_node **ret_node); + +#ifdef DEBUG_PROGRAM +static errcode_t profile_verify_node + (struct profile_node *node); +#endif + +static errcode_t profile_add_node + (struct profile_node *section, + const char *name, const char *value, + struct profile_node **ret_node); + +static errcode_t profile_find_node + (struct profile_node *section, + const char *name, const char *value, + int section_flag, void **state, + struct profile_node **node); + +static errcode_t profile_node_iterator + (void **iter_p, struct profile_node **ret_node, + char **ret_name, char **ret_value); + +static errcode_t profile_open_file + (const char * file, prf_file_t *ret_prof); + +static errcode_t profile_update_file + (prf_file_t prf); + +static void profile_free_file + (prf_file_t profile); + +static errcode_t profile_get_value(profile_t profile, const char *name, + const char *subname, const char *subsubname, + const char **ret_value); + + +/* + * prof_init.c --- routines that manipulate the user-visible profile_t + * object. + */ + +static int compstr(const void *m1, const void *m2) +{ + const char *s1 = *((const char * const *) m1); + const char *s2 = *((const char * const *) m2); + + return strcmp(s1, s2); +} + +static void free_list(char **list) +{ + char **cp; + + if (list == 0) + return; + + for (cp = list; *cp; cp++) + free(*cp); + free(list); +} + +static errcode_t get_dirlist(const char *dirname, char***ret_array) +{ + DIR *dir; + struct dirent *de; + struct stat st; + errcode_t retval; + char *fn, *cp; + char **array = 0, **new_array; + int max = 0, num = 0; + + dir = opendir(dirname); + if (!dir) + return errno; + + while ((de = readdir(dir)) != NULL) { + for (cp = de->d_name; *cp; cp++) { + if (!isalnum(*cp) && + (*cp != '-') && + (*cp != '_')) + break; + } + if (*cp) + continue; + fn = malloc(strlen(dirname) + strlen(de->d_name) + 2); + if (!fn) { + retval = ENOMEM; + goto errout; + } + sprintf(fn, "%s/%s", dirname, de->d_name); + if ((stat(fn, &st) < 0) || !S_ISREG(st.st_mode)) { + free(fn); + continue; + } + if (num >= max) { + max += 10; + new_array = realloc(array, sizeof(char *) * (max+1)); + if (!new_array) { + retval = ENOMEM; + free(fn); + goto errout; + } + array = new_array; + } + array[num++] = fn; + } + if (array) { + qsort(array, num, sizeof(char *), compstr); + array[num++] = 0; + } + *ret_array = array; + closedir(dir); + return 0; +errout: + if (array) + array[num] = 0; + closedir(dir); + free_list(array); + return retval; +} + +errcode_t +profile_init(const char * const *files, profile_t *ret_profile) +{ + const char * const *fs; + profile_t profile; + prf_file_t new_file, *last; + errcode_t retval = 0; + char **cpp, *cp, **array = 0; + + profile = malloc(sizeof(struct _profile_t)); + if (!profile) + return ENOMEM; + memset(profile, 0, sizeof(struct _profile_t)); + profile->magic = PROF_MAGIC_PROFILE; + last = &profile->first_file; + + /* if the filenames list is not specified return an empty profile */ + if ( files ) { + for (fs = files; !PROFILE_LAST_FILESPEC(*fs); fs++) { + if (array) + free_list(array); + array = NULL; + retval = get_dirlist(*fs, &array); + if (retval == 0) { + if (!array) + continue; + for (cpp = array; (cp = *cpp); cpp++) { + retval = profile_open_file(cp, &new_file); + if (retval == EACCES) + continue; + if (retval) + goto errout; + *last = new_file; + last = &new_file->next; + } + } else if ((retval != ENOTDIR) && + strcmp(*fs, default_filename)) + goto errout; + + retval = profile_open_file(*fs, &new_file); + /* if this file is missing, skip to the next */ + if (retval == ENOENT || retval == EACCES) { + continue; + } + if (retval) + goto errout; + *last = new_file; + last = &new_file->next; + } + /* + * If all the files were not found, return the appropriate error. + */ + if (!profile->first_file) { + retval = ENOENT; + goto errout; + } + } + + free_list(array); + *ret_profile = profile; + return 0; +errout: + free_list(array); + profile_release(profile); + return retval; +} + +void +profile_release(profile_t profile) +{ + prf_file_t p, next; + + if (!profile || profile->magic != PROF_MAGIC_PROFILE) + return; + + for (p = profile->first_file; p; p = next) { + next = p->next; + profile_free_file(p); + } + profile->magic = 0; + free(profile); +} + +/* + * This function sets the value of the pseudo file "". If + * the file "" had previously been passed to profile_init(), + * then def_string parameter will be parsed and used as the profile + * information for the "" file. + */ +errcode_t profile_set_default(profile_t profile, const char *def_string) +{ + struct parse_state state; + prf_file_t prf; + errcode_t retval; + const char *in; + char *line, *p, *end; + int line_size, len; + + if (!def_string || !profile || profile->magic != PROF_MAGIC_PROFILE) + return PROF_MAGIC_PROFILE; + + for (prf = profile->first_file; prf; prf = prf->next) { + if (strcmp(prf->filespec, default_filename) == 0) + break; + } + if (!prf) + return 0; + + if (prf->root) { + profile_free_node(prf->root); + prf->root = 0; + } + + memset(&state, 0, sizeof(struct parse_state)); + retval = profile_create_node("(root)", 0, &state.root_section); + if (retval) + return retval; + + line = 0; + line_size = 0; + in = def_string; + while (*in) { + end = strchr(in, '\n'); + len = end ? (end - in) : (int) strlen(in); + if (len >= line_size) { + line_size = len+1; + p = realloc(line, line_size); + if (!p) { + retval = ENOMEM; + goto errout; + } + line = p; + } + memcpy(line, in, len); + line[len] = 0; + retval = parse_line(line, &state); + if (retval) { + errout: + if (syntax_err_cb) + (syntax_err_cb)(prf->filespec, retval, + state.line_num); + free(line); + if (prf->root) + profile_free_node(prf->root); + return retval; + } + if (!end) + break; + in = end+1; + } + prf->root = state.root_section; + free(line); + + return 0; +} + +/* + * prof_file.c ---- routines that manipulate an individual profile file. + */ + +errcode_t profile_open_file(const char * filespec, + prf_file_t *ret_prof) +{ + prf_file_t prf; + errcode_t retval; + char *home_env = 0; + unsigned int len; + char *expanded_filename; + + prf = malloc(sizeof(struct _prf_file_t)); + if (!prf) + return ENOMEM; + memset(prf, 0, sizeof(struct _prf_file_t)); + prf->magic = PROF_MAGIC_FILE; + + len = strlen(filespec)+1; + if (filespec[0] == '~' && filespec[1] == '/') { + home_env = getenv("HOME"); +#ifdef HAVE_PWD_H + if (home_env == NULL) { +#ifdef HAVE_GETWUID_R + struct passwd *pw, pwx; + uid_t uid; + char pwbuf[BUFSIZ]; + + uid = getuid(); + if (!getpwuid_r(uid, &pwx, pwbuf, sizeof(pwbuf), &pw) + && pw != NULL && pw->pw_dir[0] != 0) + home_env = pw->pw_dir; +#else + struct passwd *pw; + + pw = getpwuid(getuid()); + home_env = pw->pw_dir; +#endif + } +#endif + if (home_env) + len += strlen(home_env); + } + expanded_filename = malloc(len); + if (expanded_filename == 0) { + profile_free_file(prf); + return errno; + } + if (home_env) { + strcpy(expanded_filename, home_env); + strcat(expanded_filename, filespec+1); + } else + memcpy(expanded_filename, filespec, len); + + prf->filespec = expanded_filename; + + if (strcmp(prf->filespec, default_filename) != 0) { + retval = profile_update_file(prf); + if (retval) { + profile_free_file(prf); + return retval; + } + } + + *ret_prof = prf; + return 0; +} + +errcode_t profile_update_file(prf_file_t prf) +{ + errcode_t retval; +#ifdef HAVE_STAT + struct stat st; +#ifdef STAT_ONCE_PER_SECOND + time_t now; +#endif +#endif + FILE *f; + char buf[2048]; + struct parse_state state; + + if (prf->flags & PROFILE_FILE_NO_RELOAD) + return 0; + +#ifdef HAVE_STAT +#ifdef STAT_ONCE_PER_SECOND + now = time(0); + if (now == prf->last_stat && prf->root != NULL) { + return 0; + } +#endif + if (stat(prf->filespec, &st)) { + retval = errno; + return retval; + } +#ifdef STAT_ONCE_PER_SECOND + prf->last_stat = now; +#endif + if (st.st_mtime == prf->timestamp && prf->root != NULL) { + return 0; + } + if (prf->root) { + profile_free_node(prf->root); + prf->root = 0; + } +#else + /* + * If we don't have the stat() call, assume that our in-core + * memory image is correct. That is, we won't reread the + * profile file if it changes. + */ + if (prf->root) { + return 0; + } +#endif + memset(&state, 0, sizeof(struct parse_state)); + retval = profile_create_node("(root)", 0, &state.root_section); + if (retval) + return retval; + errno = 0; + f = fopen(prf->filespec, "r"); + if (f == NULL) { + retval = errno; + if (retval == 0) + retval = ENOENT; + return retval; + } + prf->upd_serial++; + while (!feof(f)) { + if (fgets(buf, sizeof(buf), f) == NULL) + break; + retval = parse_line(buf, &state); + if (retval) { + if (syntax_err_cb) + (syntax_err_cb)(prf->filespec, retval, + state.line_num); + fclose(f); + return retval; + } + } + prf->root = state.root_section; + + fclose(f); + +#ifdef HAVE_STAT + prf->timestamp = st.st_mtime; +#endif + return 0; +} + +void profile_free_file(prf_file_t prf) +{ + if (prf->root) + profile_free_node(prf->root); + free(prf->filespec); + free(prf); +} + +/* Begin the profile parser */ + +profile_syntax_err_cb_t profile_set_syntax_err_cb(profile_syntax_err_cb_t hook) +{ + profile_syntax_err_cb_t old; + + old = syntax_err_cb; + syntax_err_cb = hook; + return(old); +} + +#define STATE_INIT_COMMENT 0 +#define STATE_STD_LINE 1 +#define STATE_GET_OBRACE 2 + +static char *skip_over_blanks(char *cp) +{ + while (*cp && isspace((int) (*cp))) + cp++; + return cp; +} + +static int end_or_comment(char ch) +{ + return (ch == 0 || ch == '#' || ch == ';'); +} + +static char *skip_over_nonblanks(char *cp) +{ + while (!end_or_comment(*cp) && !isspace(*cp)) + cp++; + return cp; +} + +static void strip_line(char *line) +{ + char *p = line + strlen(line); + while (p > line && (p[-1] == '\n' || p[-1] == '\r')) + *p-- = 0; +} + +static void parse_quoted_string(char *str) +{ + char *to, *from; + + to = from = str; + + for (to = from = str; *from && *from != '"'; to++, from++) { + if (*from == '\\') { + from++; + switch (*from) { + case 'n': + *to = '\n'; + break; + case 't': + *to = '\t'; + break; + case 'b': + *to = '\b'; + break; + default: + *to = *from; + } + continue; + } + *to = *from; + } + *to = '\0'; +} + +static errcode_t parse_line(char *line, struct parse_state *state) +{ + char *cp, ch, *tag, *value; + char *p; + errcode_t retval; + struct profile_node *node; + int do_subsection = 0; + void *iter = 0; + + state->line_num++; + if (state->state == STATE_GET_OBRACE) { + cp = skip_over_blanks(line); + if (*cp != '{') + return PROF_MISSING_OBRACE; + state->state = STATE_STD_LINE; + return 0; + } + if (state->state == STATE_INIT_COMMENT) { + if (line[0] != '[') + return 0; + state->state = STATE_STD_LINE; + } + + if (*line == 0) + return 0; + strip_line(line); + cp = skip_over_blanks(line); + ch = *cp; + if (end_or_comment(ch)) + return 0; + if (ch == '[') { + if (state->group_level > 0) + return PROF_SECTION_NOTOP; + cp++; + cp = skip_over_blanks(cp); + p = strchr(cp, ']'); + if (p == NULL) + return PROF_SECTION_SYNTAX; + if (*cp == '"') { + cp++; + parse_quoted_string(cp); + } else { + *p-- = '\0'; + while (isspace(*p) && (p > cp)) + *p-- = '\0'; + if (*cp == 0) + return PROF_SECTION_SYNTAX; + } + retval = profile_find_node(state->root_section, cp, 0, 1, + &iter, &state->current_section); + if (retval == PROF_NO_SECTION) { + retval = profile_add_node(state->root_section, + cp, 0, + &state->current_section); + if (retval) + return retval; + } else if (retval) + return retval; + + /* + * Finish off the rest of the line. + */ + cp = p+1; + if (*cp == '*') { + state->current_section->final = 1; + cp++; + } + /* + * Spaces or comments after ']' should not be fatal + */ + cp = skip_over_blanks(cp); + if (!end_or_comment(*cp)) + return PROF_SECTION_SYNTAX; + return 0; + } + if (ch == '}') { + if (state->group_level == 0) + return PROF_EXTRA_CBRACE; + if (*(cp+1) == '*') + state->current_section->final = 1; + state->current_section = state->current_section->parent; + state->group_level--; + return 0; + } + /* + * Parse the relations + */ + tag = cp; + cp = strchr(cp, '='); + if (!cp) + return PROF_RELATION_SYNTAX; + if (cp == tag) + return PROF_RELATION_SYNTAX; + *cp = '\0'; + if (*tag == '"') { + tag++; + parse_quoted_string(tag); + } else { + /* Look for whitespace on left-hand side. */ + p = skip_over_nonblanks(tag); + if (*p) + *p++ = 0; + p = skip_over_blanks(p); + /* If we have more non-whitespace, it's an error. */ + if (*p) + return PROF_RELATION_SYNTAX; + } + + cp = skip_over_blanks(cp+1); + value = cp; + ch = value[0]; + if (ch == '"') { + value++; + parse_quoted_string(value); + } else if (end_or_comment(ch)) { + do_subsection++; + state->state = STATE_GET_OBRACE; + } else if (value[0] == '{') { + cp = skip_over_blanks(value+1); + ch = *cp; + if (end_or_comment(ch)) + do_subsection++; + else + return PROF_RELATION_SYNTAX; + } else { + cp = skip_over_nonblanks(value); + p = skip_over_blanks(cp); + ch = *p; + *cp = 0; + if (!end_or_comment(ch)) + return PROF_RELATION_SYNTAX; + } + if (do_subsection) { + p = strchr(tag, '*'); + if (p) + *p = '\0'; + retval = profile_add_node(state->current_section, + tag, 0, &state->current_section); + if (retval) + return retval; + if (p) + state->current_section->final = 1; + state->group_level++; + return 0; + } + p = strchr(tag, '*'); + if (p) + *p = '\0'; + profile_add_node(state->current_section, tag, value, &node); + if (p) + node->final = 1; + return 0; +} + +#ifdef DEBUG_PROGRAM +/* + * Return TRUE if the string begins or ends with whitespace + */ +static int need_double_quotes(char *str) +{ + if (!str || !*str) + return 0; + if (isspace((int) (*str)) ||isspace((int) (*(str + strlen(str) - 1)))) + return 1; + if (strchr(str, '\n') || strchr(str, '\t') || strchr(str, '\b') || + strchr(str, ' ') || strchr(str, '#') || strchr(str, ';')) + return 1; + return 0; +} + +/* + * Output a string with double quotes, doing appropriate backquoting + * of characters as necessary. + */ +static void output_quoted_string(char *str, void (*cb)(const char *,void *), + void *data) +{ + char ch; + char buf[2]; + + cb("\"", data); + if (!str) { + cb("\"", data); + return; + } + buf[1] = 0; + while ((ch = *str++)) { + switch (ch) { + case '\\': + cb("\\\\", data); + break; + case '\n': + cb("\\n", data); + break; + case '\t': + cb("\\t", data); + break; + case '\b': + cb("\\b", data); + break; + default: + /* This would be a lot faster if we scanned + forward for the next "interesting" + character. */ + buf[0] = ch; + cb(buf, data); + break; + } + } + cb("\"", data); +} + +#ifndef EOL +#define EOL "\n" +#endif + +/* Errors should be returned, not ignored! */ +static void dump_profile(struct profile_node *root, int level, + void (*cb)(const char *, void *), void *data) +{ + int i; + struct profile_node *p; + void *iter; + long retval; + + iter = 0; + do { + retval = profile_find_node(root, 0, 0, 0, &iter, &p); + if (retval) + break; + for (i=0; i < level; i++) + cb("\t", data); + if (need_double_quotes(p->name)) + output_quoted_string(p->name, cb, data); + else + cb(p->name, data); + cb(" = ", data); + if (need_double_quotes(p->value)) + output_quoted_string(p->value, cb, data); + else + cb(p->value, data); + cb(EOL, data); + } while (iter != 0); + + iter = 0; + do { + retval = profile_find_node(root, 0, 0, 1, &iter, &p); + if (retval) + break; + if (level == 0) { /* [xxx] */ + cb("[", data); + if (need_double_quotes(p->name)) + output_quoted_string(p->name, cb, data); + else + cb(p->name, data); + cb("]", data); + cb(p->final ? "*" : "", data); + cb(EOL, data); + dump_profile(p, level+1, cb, data); + cb(EOL, data); + } else { /* xxx = { ... } */ + for (i=0; i < level; i++) + cb("\t", data); + if (need_double_quotes(p->name)) + output_quoted_string(p->name, cb, data); + else + cb(p->name, data); + cb(" = {", data); + cb(EOL, data); + dump_profile(p, level+1, cb, data); + for (i=0; i < level; i++) + cb("\t", data); + cb("}", data); + cb(p->final ? "*" : "", data); + cb(EOL, data); + } + } while (iter != 0); +} + +static void dump_profile_to_file_cb(const char *str, void *data) +{ + fputs(str, data); +} + +errcode_t profile_write_tree_file(struct profile_node *root, FILE *dstfile) +{ + dump_profile(root, 0, dump_profile_to_file_cb, dstfile); + return 0; +} + +struct prof_buf { + char *base; + size_t cur, max; + int err; +}; + +static void add_data_to_buffer(struct prof_buf *b, const void *d, size_t len) +{ + if (b->err) + return; + if (b->max - b->cur < len) { + size_t newsize; + char *newptr; + + newsize = b->max + (b->max >> 1) + len + 1024; + newptr = realloc(b->base, newsize); + if (newptr == NULL) { + b->err = 1; + return; + } + b->base = newptr; + b->max = newsize; + } + memcpy(b->base + b->cur, d, len); + b->cur += len; /* ignore overflow */ +} + +static void dump_profile_to_buffer_cb(const char *str, void *data) +{ + add_data_to_buffer((struct prof_buf *)data, str, strlen(str)); +} + +errcode_t profile_write_tree_to_buffer(struct profile_node *root, + char **buf) +{ + struct prof_buf prof_buf = { 0, 0, 0, 0 }; + + dump_profile(root, 0, dump_profile_to_buffer_cb, &prof_buf); + if (prof_buf.err) { + *buf = NULL; + return ENOMEM; + } + add_data_to_buffer(&prof_buf, "", 1); /* append nul */ + if (prof_buf.max - prof_buf.cur > (prof_buf.max >> 3)) { + char *newptr = realloc(prof_buf.base, prof_buf.cur); + if (newptr) + prof_buf.base = newptr; + } + *buf = prof_buf.base; + return 0; +} +#endif + +/* + * prof_tree.c --- these routines maintain the parse tree of the + * config file. + * + * All of the details of how the tree is stored is abstracted away in + * this file; all of the other profile routines build, access, and + * modify the tree via the accessor functions found in this file. + * + * Each node may represent either a relation or a section header. + * + * A section header must have its value field set to 0, and may a one + * or more child nodes, pointed to by first_child. + * + * A relation has as its value a pointer to allocated memory + * containing a string. Its first_child pointer must be null. + * + */ + +/* + * Free a node, and any children + */ +void profile_free_node(struct profile_node *node) +{ + struct profile_node *child, *next; + + if (node->magic != PROF_MAGIC_NODE) + return; + + free(node->name); + free(node->value); + + for (child=node->first_child; child; child = next) { + next = child->next; + profile_free_node(child); + } + node->magic = 0; + + free(node); +} + +#ifndef HAVE_STRDUP +#undef strdup +#define strdup MYstrdup +static char *MYstrdup (const char *s) +{ + size_t sz = strlen(s) + 1; + char *p = malloc(sz); + if (p != 0) + memcpy(p, s, sz); + return p; +} +#endif + +/* + * Create a node + */ +errcode_t profile_create_node(const char *name, const char *value, + struct profile_node **ret_node) +{ + struct profile_node *new; + + new = malloc(sizeof(struct profile_node)); + if (!new) + return ENOMEM; + memset(new, 0, sizeof(struct profile_node)); + new->magic = PROF_MAGIC_NODE; + new->name = strdup(name); + if (new->name == 0) { + profile_free_node(new); + return ENOMEM; + } + if (value) { + new->value = strdup(value); + if (new->value == 0) { + profile_free_node(new); + return ENOMEM; + } + } + + *ret_node = new; + return 0; +} + +/* + * This function verifies that all of the representation invariants of + * the profile are true. If not, we have a programming bug somewhere, + * probably in this file. + */ +#ifdef DEBUG_PROGRAM +errcode_t profile_verify_node(struct profile_node *node) +{ + struct profile_node *p, *last; + errcode_t retval; + + CHECK_MAGIC(node); + + if (node->value && node->first_child) + return PROF_SECTION_WITH_VALUE; + + last = 0; + for (p = node->first_child; p; last = p, p = p->next) { + if (p->prev != last) + return PROF_BAD_LINK_LIST; + if (last && (last->next != p)) + return PROF_BAD_LINK_LIST; + if (node->group_level+1 != p->group_level) + return PROF_BAD_GROUP_LVL; + if (p->parent != node) + return PROF_BAD_PARENT_PTR; + retval = profile_verify_node(p); + if (retval) + return retval; + } + return 0; +} +#endif + +/* + * Add a node to a particular section + */ +errcode_t profile_add_node(struct profile_node *section, const char *name, + const char *value, struct profile_node **ret_node) +{ + errcode_t retval; + struct profile_node *p, *last, *new; + + CHECK_MAGIC(section); + + if (section->value) + return PROF_ADD_NOT_SECTION; + + /* + * Find the place to insert the new node. We look for the + * place *after* the last match of the node name, since + * order matters. + */ + for (p=section->first_child, last = 0; p; last = p, p = p->next) { + int cmp; + cmp = strcmp(p->name, name); + if (cmp > 0) + break; + } + retval = profile_create_node(name, value, &new); + if (retval) + return retval; + new->group_level = section->group_level+1; + new->deleted = 0; + new->parent = section; + new->prev = last; + new->next = p; + if (p) + p->prev = new; + if (last) + last->next = new; + else + section->first_child = new; + if (ret_node) + *ret_node = new; + return 0; +} + +/* + * Iterate through the section, returning the nodes which match + * the given name. If name is NULL, then iterate through all the + * nodes in the section. If section_flag is non-zero, only return the + * section which matches the name; don't return relations. If value + * is non-NULL, then only return relations which match the requested + * value. (The value argument is ignored if section_flag is non-zero.) + * + * The first time this routine is called, the state pointer must be + * null. When this profile_find_node_relation() returns, if the state + * pointer is non-NULL, then this routine should be called again. + * (This won't happen if section_flag is non-zero, obviously.) + * + */ +errcode_t profile_find_node(struct profile_node *section, const char *name, + const char *value, int section_flag, void **state, + struct profile_node **node) +{ + struct profile_node *p; + + CHECK_MAGIC(section); + p = *state; + if (p) { + CHECK_MAGIC(p); + } else + p = section->first_child; + + for (; p; p = p->next) { + if (name && (strcmp(p->name, name))) + continue; + if (section_flag) { + if (p->value) + continue; + } else { + if (!p->value) + continue; + if (value && (strcmp(p->value, value))) + continue; + } + if (p->deleted) + continue; + /* A match! */ + if (node) + *node = p; + break; + } + if (p == 0) { + *state = 0; + return section_flag ? PROF_NO_SECTION : PROF_NO_RELATION; + } + /* + * OK, we've found one match; now let's try to find another + * one. This way, if we return a non-zero state pointer, + * there's guaranteed to be another match that's returned. + */ + for (p = p->next; p; p = p->next) { + if (name && (strcmp(p->name, name))) + continue; + if (section_flag) { + if (p->value) + continue; + } else { + if (!p->value) + continue; + if (value && (strcmp(p->value, value))) + continue; + } + /* A match! */ + break; + } + *state = p; + return 0; +} + +/* + * This is a general-purpose iterator for returning all nodes that + * match the specified name array. + */ +struct profile_iterator { + prf_magic_t magic; + profile_t profile; + int flags; + const char *const *names; + const char *name; + prf_file_t file; + int file_serial; + int done_idx; + struct profile_node *node; + int num; +}; + +errcode_t +profile_iterator_create(profile_t profile, const char *const *names, int flags, + void **ret_iter) +{ + struct profile_iterator *iter; + int done_idx = 0; + + if (profile == 0) + return PROF_NO_PROFILE; + if (profile->magic != PROF_MAGIC_PROFILE) + return PROF_MAGIC_PROFILE; + if (!names) + return PROF_BAD_NAMESET; + if (!(flags & PROFILE_ITER_LIST_SECTION)) { + if (!names[0]) + return PROF_BAD_NAMESET; + done_idx = 1; + } + + if ((iter = malloc(sizeof(struct profile_iterator))) == NULL) + return ENOMEM; + + iter->magic = PROF_MAGIC_ITERATOR; + iter->profile = profile; + iter->names = names; + iter->flags = flags; + iter->file = profile->first_file; + iter->done_idx = done_idx; + iter->node = 0; + iter->num = 0; + *ret_iter = iter; + return 0; +} + +void profile_iterator_free(void **iter_p) +{ + struct profile_iterator *iter; + + if (!iter_p) + return; + iter = *iter_p; + if (!iter || iter->magic != PROF_MAGIC_ITERATOR) + return; + free(iter); + *iter_p = 0; +} + +/* + * Note: the returned character strings in ret_name and ret_value + * points to the stored character string in the parse string. Before + * this string value is returned to a calling application + * (profile_node_iterator is not an exported interface), it should be + * strdup()'ed. + */ +errcode_t profile_node_iterator(void **iter_p, struct profile_node **ret_node, + char **ret_name, char **ret_value) +{ + struct profile_iterator *iter = *iter_p; + struct profile_node *section, *p; + const char *const *cpp; + errcode_t retval; + int skip_num = 0; + + if (!iter || iter->magic != PROF_MAGIC_ITERATOR) + return PROF_MAGIC_ITERATOR; + if (iter->file && iter->file->magic != PROF_MAGIC_FILE) + return PROF_MAGIC_FILE; + /* + * If the file has changed, then the node pointer is invalid, + * so we'll have search the file again looking for it. + */ + if (iter->node && (iter->file && + iter->file->upd_serial != iter->file_serial)) { + iter->flags &= ~PROFILE_ITER_FINAL_SEEN; + skip_num = iter->num; + iter->node = 0; + } + if (iter->node && iter->node->magic != PROF_MAGIC_NODE) { + return PROF_MAGIC_NODE; + } +get_new_file: + if (iter->node == 0) { + if (iter->file == NULL || + (iter->flags & PROFILE_ITER_FINAL_SEEN)) { + profile_iterator_free(iter_p); + if (ret_node) + *ret_node = 0; + if (ret_name) + *ret_name = 0; + if (ret_value) + *ret_value =0; + return 0; + } + if ((retval = profile_update_file(iter->file))) { + if (retval == ENOENT || retval == EACCES) { + /* XXX memory leak? */ + if (iter->file) + iter->file = iter->file->next; + skip_num = 0; + retval = 0; + goto get_new_file; + } else { + profile_iterator_free(iter_p); + return retval; + } + } + iter->file_serial = iter->file->upd_serial; + /* + * Find the section to list if we are a LIST_SECTION, + * or find the containing section if not. + */ + section = iter->file->root; + for (cpp = iter->names; cpp[iter->done_idx]; cpp++) { + for (p=section->first_child; p; p = p->next) { + if (!strcmp(p->name, *cpp) && !p->value) + break; + } + if (!p) { + section = 0; + break; + } + section = p; + if (p->final) + iter->flags |= PROFILE_ITER_FINAL_SEEN; + } + if (!section) { + if (iter->file) + iter->file = iter->file->next; + skip_num = 0; + goto get_new_file; + } + iter->name = *cpp; + iter->node = section->first_child; + } + /* + * OK, now we know iter->node is set up correctly. Let's do + * the search. + */ + for (p = iter->node; p; p = p->next) { + if (iter->name && strcmp(p->name, iter->name)) + continue; + if ((iter->flags & PROFILE_ITER_SECTIONS_ONLY) && + p->value) + continue; + if ((iter->flags & PROFILE_ITER_RELATIONS_ONLY) && + !p->value) + continue; + if (skip_num > 0) { + skip_num--; + continue; + } + if (p->deleted) + continue; + break; + } + iter->num++; + if (!p) { + if (iter->file) + iter->file = iter->file->next; + iter->node = 0; + skip_num = 0; + goto get_new_file; + } + if ((iter->node = p->next) == NULL) + if (iter->file) + iter->file = iter->file->next; + if (ret_node) + *ret_node = p; + if (ret_name) + *ret_name = p->name; + if (ret_value) + *ret_value = p->value; + return 0; +} + + +/* + * prof_get.c --- routines that expose the public interfaces for + * querying items from the profile. + * + */ + +/* + * This function only gets the first value from the file; it is a + * helper function for profile_get_string, profile_get_integer, etc. + */ +errcode_t profile_get_value(profile_t profile, const char *name, + const char *subname, const char *subsubname, + const char **ret_value) +{ + errcode_t retval; + void *state; + char *value; + const char *names[4]; + + names[0] = name; + names[1] = subname; + names[2] = subsubname; + names[3] = 0; + + if ((retval = profile_iterator_create(profile, names, + PROFILE_ITER_RELATIONS_ONLY, + &state))) + return retval; + + if ((retval = profile_node_iterator(&state, 0, 0, &value))) + goto cleanup; + + if (value) + *ret_value = value; + else + retval = PROF_NO_RELATION; + +cleanup: + profile_iterator_free(&state); + return retval; +} + +errcode_t +profile_get_string(profile_t profile, const char *name, const char *subname, + const char *subsubname, const char *def_val, + char **ret_string) +{ + const char *value; + errcode_t retval; + + if (profile) { + retval = profile_get_value(profile, name, subname, + subsubname, &value); + if (retval == PROF_NO_SECTION || retval == PROF_NO_RELATION) + value = def_val; + else if (retval) + return retval; + } else + value = def_val; + + if (value) { + *ret_string = malloc(strlen(value)+1); + if (*ret_string == 0) + return ENOMEM; + strcpy(*ret_string, value); + } else + *ret_string = 0; + return 0; +} + +errcode_t +profile_get_integer(profile_t profile, const char *name, const char *subname, + const char *subsubname, int def_val, int *ret_int) +{ + const char *value; + errcode_t retval; + char *end_value; + long ret_long; + + *ret_int = def_val; + if (profile == 0) + return 0; + + retval = profile_get_value(profile, name, subname, subsubname, &value); + if (retval == PROF_NO_SECTION || retval == PROF_NO_RELATION) { + *ret_int = def_val; + return 0; + } else if (retval) + return retval; + + if (value[0] == 0) + /* Empty string is no good. */ + return PROF_BAD_INTEGER; + errno = 0; + ret_long = strtol(value, &end_value, 0); + + /* Overflow or underflow. */ + if ((ret_long == LONG_MIN || ret_long == LONG_MAX) && errno != 0) + return PROF_BAD_INTEGER; + /* Value outside "int" range. */ + if ((long) (int) ret_long != ret_long) + return PROF_BAD_INTEGER; + /* Garbage in string. */ + if (end_value != value + strlen (value)) + return PROF_BAD_INTEGER; + + + *ret_int = ret_long; + return 0; +} + +errcode_t +profile_get_uint(profile_t profile, const char *name, const char *subname, + const char *subsubname, unsigned int def_val, + unsigned int *ret_int) +{ + const char *value; + errcode_t retval; + char *end_value; + unsigned long ret_long; + + *ret_int = def_val; + if (profile == 0) + return 0; + + retval = profile_get_value(profile, name, subname, subsubname, &value); + if (retval == PROF_NO_SECTION || retval == PROF_NO_RELATION) { + *ret_int = def_val; + return 0; + } else if (retval) + return retval; + + if (value[0] == 0) + /* Empty string is no good. */ + return PROF_BAD_INTEGER; + errno = 0; + ret_long = strtoul(value, &end_value, 0); + + /* Overflow or underflow. */ + if ((ret_long == ULONG_MAX) && errno != 0) + return PROF_BAD_INTEGER; + /* Value outside "int" range. */ + if ((unsigned long) (unsigned int) ret_long != ret_long) + return PROF_BAD_INTEGER; + /* Garbage in string. */ + if (end_value != value + strlen (value)) + return PROF_BAD_INTEGER; + + *ret_int = ret_long; + return 0; +} + +errcode_t +profile_get_double(profile_t profile, const char *name, const char *subname, + const char *subsubname, double def_val, double *ret_double) +{ + const char *value; + errcode_t retval; + char *end_value; + double double_val; + + *ret_double = def_val; + if (profile == 0) + return 0; + + retval = profile_get_value(profile, name, subname, subsubname, &value); + if (retval == PROF_NO_SECTION || retval == PROF_NO_RELATION) { + *ret_double = def_val; + return 0; + } else if (retval) + return retval; + + if (value[0] == 0) + /* Empty string is no good. */ + return PROF_BAD_INTEGER; + errno = 0; + double_val = strtod(value, &end_value); + + /* Overflow or underflow. */ + if (errno != 0) + return PROF_BAD_INTEGER; + /* Garbage in string. */ + if (end_value != value + strlen(value)) + return PROF_BAD_INTEGER; + + *ret_double = double_val; + return 0; +} + +static const char *const conf_yes[] = { + "y", "yes", "true", "t", "1", "on", + 0, +}; + +static const char *const conf_no[] = { + "n", "no", "false", "nil", "0", "off", + 0, +}; + +static errcode_t +profile_parse_boolean(const char *s, int *ret_boolean) +{ + const char *const *p; + + if (ret_boolean == NULL) + return PROF_EINVAL; + + for(p=conf_yes; *p; p++) { + if (!strcasecmp(*p,s)) { + *ret_boolean = 1; + return 0; + } + } + + for(p=conf_no; *p; p++) { + if (!strcasecmp(*p,s)) { + *ret_boolean = 0; + return 0; + } + } + + return PROF_BAD_BOOLEAN; +} + +errcode_t +profile_get_boolean(profile_t profile, const char *name, const char *subname, + const char *subsubname, int def_val, int *ret_boolean) +{ + const char *value; + errcode_t retval; + + if (profile == 0) { + *ret_boolean = def_val; + return 0; + } + + retval = profile_get_value(profile, name, subname, subsubname, &value); + if (retval == PROF_NO_SECTION || retval == PROF_NO_RELATION) { + *ret_boolean = def_val; + return 0; + } else if (retval) + return retval; + + return profile_parse_boolean (value, ret_boolean); +} + +errcode_t +profile_iterator(void **iter_p, char **ret_name, char **ret_value) +{ + char *name, *value; + errcode_t retval; + + retval = profile_node_iterator(iter_p, 0, &name, &value); + if (retval) + return retval; + + if (ret_name) { + if (name) { + *ret_name = malloc(strlen(name)+1); + if (!*ret_name) + return ENOMEM; + strcpy(*ret_name, name); + } else + *ret_name = 0; + } + if (ret_value) { + if (value) { + *ret_value = malloc(strlen(value)+1); + if (!*ret_value) { + if (ret_name) { + free(*ret_name); + *ret_name = 0; + } + return ENOMEM; + } + strcpy(*ret_value, value); + } else + *ret_value = 0; + } + return 0; +} + +#ifdef DEBUG_PROGRAM + +/* + * test_profile.c --- testing program for the profile routine + */ + +#include "argv_parse.h" +#include "profile_helpers.h" + +const char *program_name = "test_profile"; + +#define PRINT_VALUE 1 +#define PRINT_VALUES 2 + +static void do_cmd(profile_t profile, char **argv) +{ + errcode_t retval; + const char **names, *value; + char **values, **cpp; + char *cmd; + int print_status; + + cmd = *(argv); + names = (const char **) argv + 1; + print_status = 0; + retval = 0; + if (cmd == 0) + return; + if (!strcmp(cmd, "query")) { + retval = profile_get_values(profile, names, &values); + print_status = PRINT_VALUES; + } else if (!strcmp(cmd, "query1")) { + const char *name = 0; + const char *subname = 0; + const char *subsubname = 0; + + name = names[0]; + if (name) + subname = names[1]; + if (subname) + subsubname = names[2]; + if (subsubname && names[3]) { + fprintf(stderr, + "Only 3 levels are allowed with query1\n"); + retval = EINVAL; + } else + retval = profile_get_value(profile, name, subname, + subsubname, &value); + print_status = PRINT_VALUE; + } else if (!strcmp(cmd, "list_sections")) { + retval = profile_get_subsection_names(profile, names, + &values); + print_status = PRINT_VALUES; + } else if (!strcmp(cmd, "list_relations")) { + retval = profile_get_relation_names(profile, names, + &values); + print_status = PRINT_VALUES; + } else if (!strcmp(cmd, "dump")) { + retval = profile_write_tree_file + (profile->first_file->root, stdout); +#if 0 + } else if (!strcmp(cmd, "clear")) { + retval = profile_clear_relation(profile, names); + } else if (!strcmp(cmd, "update")) { + retval = profile_update_relation(profile, names+2, + *names, *(names+1)); +#endif + } else if (!strcmp(cmd, "verify")) { + retval = profile_verify_node + (profile->first_file->root); +#if 0 + } else if (!strcmp(cmd, "rename_section")) { + retval = profile_rename_section(profile, names+1, *names); + } else if (!strcmp(cmd, "add")) { + value = *names; + if (strcmp(value, "NULL") == 0) + value = NULL; + retval = profile_add_relation(profile, names+1, value); + } else if (!strcmp(cmd, "flush")) { + retval = profile_flush(profile); +#endif + } else { + printf("Invalid command.\n"); + } + if (retval) { + com_err(cmd, retval, ""); + print_status = 0; + } + switch (print_status) { + case PRINT_VALUE: + printf("%s\n", value); + break; + case PRINT_VALUES: + for (cpp = values; *cpp; cpp++) + printf("%s\n", *cpp); + profile_free_list(values); + break; + } +} + +static void do_batchmode(profile_t profile) +{ + int argc, ret; + char **argv; + char buf[256]; + + while (!feof(stdin)) { + if (fgets(buf, sizeof(buf), stdin) == NULL) + break; + printf(">%s", buf); + ret = argv_parse(buf, &argc, &argv); + if (ret != 0) { + printf("Argv_parse returned %d!\n", ret); + continue; + } + do_cmd(profile, argv); + printf("\n"); + argv_free(argv); + } + profile_release(profile); + exit(0); + +} + +void syntax_err_report(const char *filename, long err, int line_num) +{ + fprintf(stderr, "Syntax error in %s, line number %d: %s\n", + filename, line_num, error_message(err)); + exit(1); +} + +const char *default_str = "[foo]\n\tbar=quux\n\tsub = {\n\t\twin = true\n}\n"; + +int main(int argc, char **argv) +{ + profile_t profile; + long retval; + char *cmd; + + if (argc < 2) { + fprintf(stderr, "Usage: %s filename [cmd argset]\n", program_name); + exit(1); + } + + initialize_prof_error_table(); + + profile_set_syntax_err_cb(syntax_err_report); + + retval = profile_init_path(argv[1], &profile); + if (retval) { + com_err(program_name, retval, "while initializing profile"); + exit(1); + } + retval = profile_set_default(profile, default_str); + if (retval) { + com_err(program_name, retval, "while setting default"); + exit(1); + } + + cmd = *(argv+2); + if (!cmd || !strcmp(cmd, "batch")) + do_batchmode(profile); + else + do_cmd(profile, argv+2); + profile_release(profile); + + return 0; +} + +#endif diff --git a/lib/support/profile.h b/lib/support/profile.h new file mode 100644 index 0000000..aec870a --- /dev/null +++ b/lib/support/profile.h @@ -0,0 +1,107 @@ +/* + * profile.h + * + * Copyright (C) 2005 by Theodore Ts'o. + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + * + * Copyright (C) 1985-2005 by the Massachusetts Institute of Technology. + * + * All rights reserved. + * + * Export of this software from the United States of America may require + * a specific license from the United States Government. It is the + * responsibility of any person or organization contemplating export to + * obtain such a license before exporting. + * + * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and + * distribute this software and its documentation for any purpose and + * without fee is hereby granted, provided that the above copyright + * notice appear in all copies and that both that copyright notice and + * this permission notice appear in supporting documentation, and that + * the name of M.I.T. not be used in advertising or publicity pertaining + * to distribution of the software without specific, written prior + * permission. Furthermore if you modify this software you must label + * your software as modified software and not distribute it in such a + * fashion that it might be confused with the original MIT software. + * M.I.T. makes no representations about the suitability of this software + * for any purpose. It is provided "as is" without express or implied + * warranty. + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED + * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. + */ + +#ifndef _PROFILE_H +#define _PROFILE_H + +typedef struct _profile_t *profile_t; + +typedef void (*profile_syntax_err_cb_t)(const char *file, long err, + int line_num); + +/* + * Used by the profile iterator in prof_get.c + */ +#define PROFILE_ITER_LIST_SECTION 0x0001 +#define PROFILE_ITER_SECTIONS_ONLY 0x0002 +#define PROFILE_ITER_RELATIONS_ONLY 0x0004 + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +long profile_init + (const char * const *files, profile_t *ret_profile); + +void profile_release + (profile_t profile); + +long profile_set_default + (profile_t profile, const char *def_string); + +long profile_get_string + (profile_t profile, const char *name, const char *subname, + const char *subsubname, const char *def_val, + char **ret_string); +long profile_get_integer + (profile_t profile, const char *name, const char *subname, + const char *subsubname, int def_val, + int *ret_default); + +long profile_get_uint + (profile_t profile, const char *name, const char *subname, + const char *subsubname, unsigned int def_val, + unsigned int *ret_int); + +long profile_get_double + (profile_t profile, const char *name, const char *subname, + const char *subsubname, double def_val, + double *ret_float); + +long profile_get_boolean + (profile_t profile, const char *name, const char *subname, + const char *subsubname, int def_val, + int *ret_default); + +long profile_iterator_create + (profile_t profile, const char *const *names, + int flags, void **ret_iter); + +void profile_iterator_free + (void **iter_p); + +long profile_iterator + (void **iter_p, char **ret_name, char **ret_value); + +profile_syntax_err_cb_t profile_set_syntax_err_cb(profile_syntax_err_cb_t hook); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* _KRB5_H */ diff --git a/lib/support/profile_helpers.c b/lib/support/profile_helpers.c new file mode 100644 index 0000000..d7d6f15 --- /dev/null +++ b/lib/support/profile_helpers.c @@ -0,0 +1,317 @@ +/* + * profile_helpers.c -- Helper functions for the profile library + * + * These functions are not part of the "core" profile library, and do + * not require access to the internal functions and data structures of + * the profile library. They are mainly convenience functions for + * programs that want to do something unusual such as obtaining the + * list of sections or relations, or accessing multiple values from a + * relation that is listed more than once. This functionality can all + * be done using the profile_iterator abstraction, but it is less + * convenient. + * + * Copyright (C) 2006 by Theodore Ts'o. + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +#include "config.h" +#include +#include +#include + +#include +#include "profile.h" +#include "profile_helpers.h" +#include "prof_err.h" + +/* + * These functions --- init_list(), end_list(), and add_to_list() are + * internal functions used to build up a null-terminated char ** list + * of strings to be returned by functions like profile_get_values. + * + * The profile_string_list structure is used for internal booking + * purposes to build up the list, which is returned in *ret_list by + * the end_list() function. + * + * The publicly exported interface for freeing char** list is + * profile_free_list(). + */ + +struct profile_string_list { + char **list; + int num; + int max; +}; + +/* + * Initialize the string list abstraction. + */ +static errcode_t init_list(struct profile_string_list *list) +{ + list->num = 0; + list->max = 10; + list->list = malloc(list->max * sizeof(char *)); + if (list->list == 0) + return ENOMEM; + list->list[0] = 0; + return 0; +} + +/* + * Free any memory left over in the string abstraction, returning the + * built up list in *ret_list if it is non-null. + */ +static void end_list(struct profile_string_list *list, char ***ret_list) +{ + char **cp; + + if (list == 0) + return; + + if (ret_list) { + *ret_list = list->list; + return; + } else { + for (cp = list->list; *cp; cp++) + free(*cp); + free(list->list); + } + list->num = list->max = 0; + list->list = 0; +} + +/* + * Add a string to the list. + */ +static errcode_t add_to_list(struct profile_string_list *list, char *str) +{ + char **newlist; + int newmax; + + if (list->num+1 >= list->max) { + newmax = list->max + 10; + newlist = realloc(list->list, newmax * sizeof(char *)); + if (newlist == 0) + return ENOMEM; + list->max = newmax; + list->list = newlist; + } + + list->list[list->num++] = str; + list->list[list->num] = 0; + return 0; +} + +/* + * Return TRUE if the string is already a member of the list. + */ +static int is_list_member(struct profile_string_list *list, const char *str) +{ + char **cpp; + + if (!list->list) + return 0; + + for (cpp = list->list; *cpp; cpp++) { + if (!strcmp(*cpp, str)) + return 1; + } + return 0; +} + +/* + * This function frees a null-terminated list as returned by + * profile_get_values. + */ +void profile_free_list(char **list) +{ + char **cp; + + if (list == 0) + return; + + for (cp = list; *cp; cp++) + free(*cp); + free(list); +} + +errcode_t +profile_get_values(profile_t profile, const char *const *names, + char ***ret_values) +{ + errcode_t retval; + void *state; + char *value; + struct profile_string_list values; + + if ((retval = profile_iterator_create(profile, names, + PROFILE_ITER_RELATIONS_ONLY, + &state))) + return retval; + + if ((retval = init_list(&values))) + goto cleanup_iterator; + + do { + if ((retval = profile_iterator(&state, 0, &value))) + goto cleanup; + if (value) + add_to_list(&values, value); + } while (state); + + if (values.num == 0) { + retval = PROF_NO_RELATION; + goto cleanup; + } + + end_list(&values, ret_values); + return 0; + +cleanup: + end_list(&values, 0); +cleanup_iterator: + profile_iterator_free(&state); + return retval; +} + +/* + * This function will return the list of the names of subsections in the + * under the specified section name. + */ +errcode_t +profile_get_subsection_names(profile_t profile, const char **names, + char ***ret_names) +{ + errcode_t retval; + void *state; + char *name; + struct profile_string_list values; + + if ((retval = profile_iterator_create(profile, names, + PROFILE_ITER_LIST_SECTION | PROFILE_ITER_SECTIONS_ONLY, + &state))) + return retval; + + if ((retval = init_list(&values))) + goto cleanup_iterator; + + do { + if ((retval = profile_iterator(&state, &name, 0))) + goto cleanup; + if (name) + add_to_list(&values, name); + } while (state); + + end_list(&values, ret_names); + return 0; + +cleanup: + end_list(&values, 0); +cleanup_iterator: + profile_iterator_free(&state); + return retval; +} + +/* + * This function will return the list of the names of relations in the + * under the specified section name. + */ +errcode_t +profile_get_relation_names(profile_t profile, const char **names, + char ***ret_names) +{ + errcode_t retval; + void *state; + char *name; + struct profile_string_list values; + + if ((retval = profile_iterator_create(profile, names, + PROFILE_ITER_LIST_SECTION | PROFILE_ITER_RELATIONS_ONLY, + &state))) + return retval; + + if ((retval = init_list(&values))) + goto cleanup_iterator; + + do { + if ((retval = profile_iterator(&state, &name, 0))) + goto cleanup; + if (name) { + if (is_list_member(&values, name)) + free(name); + else + add_to_list(&values, name); + } + } while (state); + + end_list(&values, ret_names); + return 0; + +cleanup: + end_list(&values, 0); +cleanup_iterator: + profile_iterator_free(&state); + return retval; +} + + +void +profile_release_string(char *str) +{ + free(str); +} + +errcode_t +profile_init_path(const char * filepath, + profile_t *ret_profile) +{ + int n_entries, i; + unsigned int ent_len; + const char *s, *t; + char **filenames; + errcode_t retval; + + /* count the distinct filename components */ + for(s = filepath, n_entries = 1; *s; s++) { + if (*s == ':') + n_entries++; + } + + /* the array is NULL terminated */ + filenames = (char **) malloc((n_entries+1) * sizeof(char*)); + if (filenames == 0) + return ENOMEM; + + /* measure, copy, and skip each one */ + for(s = filepath, i=0; (t = strchr(s, ':')) || (t=s+strlen(s)); s=t+1, i++) { + ent_len = t-s; + filenames[i] = (char*) malloc(ent_len + 1); + if (filenames[i] == 0) { + /* if malloc fails, free the ones that worked */ + while(--i >= 0) free(filenames[i]); + free(filenames); + return ENOMEM; + } + strncpy(filenames[i], s, ent_len); + filenames[i][ent_len] = 0; + if (*t == 0) { + i++; + break; + } + } + /* cap the array */ + filenames[i] = 0; + + retval = profile_init((const char * const *) filenames, + ret_profile); + + /* count back down and free the entries */ + while(--i >= 0) free(filenames[i]); + free(filenames); + + return retval; +} diff --git a/lib/support/profile_helpers.h b/lib/support/profile_helpers.h new file mode 100644 index 0000000..af63ca5 --- /dev/null +++ b/lib/support/profile_helpers.h @@ -0,0 +1,28 @@ +/* + * profile_helpers.h -- Function prototypes for profile helper functions + * + * Copyright (C) 2006 by Theodore Ts'o. + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +long profile_get_values + (profile_t profile, const char *const *names, char ***ret_values); + +void profile_free_list + (char **list); + +long profile_get_relation_names + (profile_t profile, const char **names, char ***ret_names); + +long profile_get_subsection_names + (profile_t profile, const char **names, char ***ret_names); + +void profile_release_string (char *str); + +long profile_init_path + (const char * filelist, profile_t *ret_profile); + diff --git a/lib/support/quotaio.c b/lib/support/quotaio.c new file mode 100644 index 0000000..b41bb74 --- /dev/null +++ b/lib/support/quotaio.c @@ -0,0 +1,412 @@ +/** quotaio.c + * + * Generic IO operations on quotafiles + * Jan Kara - sponsored by SuSE CR + * Aditya Kali - Ported to e2fsprogs + */ + +#include "config.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "common.h" +#include "quotaio.h" + +static const char * const extensions[MAXQUOTAS] = { + [USRQUOTA] = "user", + [GRPQUOTA] = "group", + [PRJQUOTA] = "project", +}; +static const char * const basenames[] = { + "", /* undefined */ + "quota", /* QFMT_VFS_OLD */ + "aquota", /* QFMT_VFS_V0 */ + "", /* QFMT_OCFS2 */ + "aquota" /* QFMT_VFS_V1 */ +}; + +/* Header in all newer quotafiles */ +struct disk_dqheader { + __le32 dqh_magic; + __le32 dqh_version; +} __attribute__ ((packed)); + +/** + * Convert type of quota to written representation + */ +const char *quota_type2name(enum quota_type qtype) +{ + if (qtype >= MAXQUOTAS) + return "unknown"; + return extensions[qtype]; +} + +ext2_ino_t quota_type2inum(enum quota_type qtype, + struct ext2_super_block *sb) +{ + switch (qtype) { + case USRQUOTA: + return EXT4_USR_QUOTA_INO; + case GRPQUOTA: + return EXT4_GRP_QUOTA_INO; + case PRJQUOTA: + return sb->s_prj_quota_inum; + default: + return 0; + } + return 0; +} + +/** + * Creates a quota file name for given type and format. + */ +const char *quota_get_qf_name(enum quota_type type, int fmt, char *buf) +{ + if (!buf) + return NULL; + snprintf(buf, QUOTA_NAME_LEN, "%s.%s", + basenames[fmt], extensions[type]); + + return buf; +} + +/* + * Set grace time if needed + */ +void update_grace_times(struct dquot *q) +{ + time_t now; + + time(&now); + if (q->dq_dqb.dqb_bsoftlimit && toqb(q->dq_dqb.dqb_curspace) > + q->dq_dqb.dqb_bsoftlimit) { + if (!q->dq_dqb.dqb_btime) + q->dq_dqb.dqb_btime = + now + q->dq_h->qh_info.dqi_bgrace; + } else { + q->dq_dqb.dqb_btime = 0; + } + + if (q->dq_dqb.dqb_isoftlimit && q->dq_dqb.dqb_curinodes > + q->dq_dqb.dqb_isoftlimit) { + if (!q->dq_dqb.dqb_itime) + q->dq_dqb.dqb_itime = + now + q->dq_h->qh_info.dqi_igrace; + } else { + q->dq_dqb.dqb_itime = 0; + } +} + +errcode_t quota_inode_truncate(ext2_filsys fs, ext2_ino_t ino) +{ + struct ext2_inode inode; + errcode_t err; + enum quota_type qtype; + + if ((err = ext2fs_read_inode(fs, ino, &inode))) + return err; + + for (qtype = 0; qtype < MAXQUOTAS; qtype++) + if (ino == quota_type2inum(qtype, fs->super)) + break; + + if (qtype != MAXQUOTAS) { + inode.i_dtime = fs->now ? fs->now : time(0); + if (!ext2fs_inode_has_valid_blocks2(fs, &inode)) + return 0; + err = ext2fs_punch(fs, ino, &inode, NULL, 0, ~0ULL); + if (err) + return err; + fs->flags &= ~EXT2_FLAG_SUPER_ONLY; + memset(&inode, 0, sizeof(struct ext2_inode)); + } else { + inode.i_flags &= ~EXT2_IMMUTABLE_FL; + } + err = ext2fs_write_inode(fs, ino, &inode); + return err; +} + +/* Functions to read/write quota file. */ +static unsigned int quota_write_nomount(struct quota_file *qf, + ext2_loff_t offset, + void *buf, unsigned int size) +{ + ext2_file_t e2_file = qf->e2_file; + unsigned int bytes_written = 0; + errcode_t err; + + err = ext2fs_file_llseek(e2_file, offset, EXT2_SEEK_SET, NULL); + if (err) { + log_err("ext2fs_file_llseek failed: %ld", err); + return 0; + } + + err = ext2fs_file_write(e2_file, buf, size, &bytes_written); + if (err) { + log_err("ext2fs_file_write failed: %ld", err); + return 0; + } + + /* Correct inode.i_size is set in end_io. */ + return bytes_written; +} + +static unsigned int quota_read_nomount(struct quota_file *qf, + ext2_loff_t offset, + void *buf, unsigned int size) +{ + ext2_file_t e2_file = qf->e2_file; + unsigned int bytes_read = 0; + errcode_t err; + + err = ext2fs_file_llseek(e2_file, offset, EXT2_SEEK_SET, NULL); + if (err) { + log_err("ext2fs_file_llseek failed: %ld", err); + return 0; + } + + err = ext2fs_file_read(e2_file, buf, size, &bytes_read); + if (err) { + log_err("ext2fs_file_read failed: %ld", err); + return 0; + } + + return bytes_read; +} + +/* + * Detect quota format and initialize quota IO + */ +errcode_t quota_file_open(quota_ctx_t qctx, struct quota_handle *h, + ext2_ino_t qf_ino, enum quota_type qtype, + int fmt, int flags) +{ + ext2_filsys fs = qctx->fs; + ext2_file_t e2_file; + errcode_t err; + int allocated_handle = 0; + + if (qtype >= MAXQUOTAS) + return EINVAL; + + if (fmt == -1) + fmt = QFMT_VFS_V1; + + err = ext2fs_read_bitmaps(fs); + if (err) + return err; + + if (qf_ino == 0) + qf_ino = *quota_sb_inump(fs->super, qtype); + + log_debug("Opening quota ino=%u, type=%d", qf_ino, qtype); + err = ext2fs_file_open(fs, qf_ino, flags, &e2_file); + if (err) { + log_err("ext2fs_file_open failed: %s", error_message(err)); + return err; + } + + if (!h) { + if (qctx->quota_file[qtype]) { + h = qctx->quota_file[qtype]; + if (((flags & EXT2_FILE_WRITE) == 0) || + (h->qh_file_flags & EXT2_FILE_WRITE)) { + ext2fs_file_close(e2_file); + return 0; + } + (void) quota_file_close(qctx, h); + } + err = ext2fs_get_mem(sizeof(struct quota_handle), &h); + if (err) { + log_err("Unable to allocate quota handle"); + ext2fs_file_close(e2_file); + return err; + } + allocated_handle = 1; + } + + h->qh_qf.e2_file = e2_file; + h->qh_qf.fs = fs; + h->qh_qf.ino = qf_ino; + h->e2fs_write = quota_write_nomount; + h->e2fs_read = quota_read_nomount; + h->qh_file_flags = flags; + h->qh_io_flags = 0; + h->qh_type = qtype; + h->qh_fmt = fmt; + memset(&h->qh_info, 0, sizeof(h->qh_info)); + h->qh_ops = "afile_ops_2; + + if (h->qh_ops->check_file && + (h->qh_ops->check_file(h, qtype, fmt) == 0)) { + log_err("qh_ops->check_file failed"); + err = EIO; + goto errout; + } + + if (h->qh_ops->init_io && (h->qh_ops->init_io(h) < 0)) { + log_err("qh_ops->init_io failed"); + err = EIO; + goto errout; + } + if (allocated_handle) + qctx->quota_file[qtype] = h; + + return 0; +errout: + ext2fs_file_close(e2_file); + if (allocated_handle) + ext2fs_free_mem(&h); + return err; +} + +static errcode_t quota_inode_init_new(ext2_filsys fs, ext2_ino_t ino) +{ + struct ext2_inode inode; + errcode_t err = 0; + + err = ext2fs_read_inode(fs, ino, &inode); + if (err) { + log_err("ex2fs_read_inode failed"); + return err; + } + + if (EXT2_I_SIZE(&inode)) { + err = quota_inode_truncate(fs, ino); + if (err) + return err; + } + + memset(&inode, 0, sizeof(struct ext2_inode)); + ext2fs_iblk_set(fs, &inode, 0); + inode.i_atime = inode.i_mtime = + inode.i_ctime = fs->now ? fs->now : time(0); + inode.i_links_count = 1; + inode.i_mode = LINUX_S_IFREG | 0600; + inode.i_flags |= EXT2_IMMUTABLE_FL; + if (ext2fs_has_feature_extents(fs->super)) + inode.i_flags |= EXT4_EXTENTS_FL; + + err = ext2fs_write_new_inode(fs, ino, &inode); + if (err) { + log_err("ext2fs_write_new_inode failed: %ld", err); + return err; + } + return err; +} + +/* + * Create new quotafile of specified format on given filesystem + */ +errcode_t quota_file_create(struct quota_handle *h, ext2_filsys fs, + enum quota_type qtype, int fmt) +{ + ext2_file_t e2_file; + errcode_t err; + ext2_ino_t qf_inum = 0; + + if (fmt == -1) + fmt = QFMT_VFS_V1; + + h->qh_qf.fs = fs; + qf_inum = quota_type2inum(qtype, fs->super); + if (qf_inum == 0 && qtype == PRJQUOTA) { + err = ext2fs_new_inode(fs, EXT2_ROOT_INO, LINUX_S_IFREG | 0600, + 0, &qf_inum); + if (err) + return err; + ext2fs_inode_alloc_stats2(fs, qf_inum, +1, 0); + ext2fs_mark_ib_dirty(fs); + } else if (qf_inum == 0) { + return EXT2_ET_BAD_INODE_NUM; + } + + err = ext2fs_read_bitmaps(fs); + if (err) + goto out_err; + + err = quota_inode_init_new(fs, qf_inum); + if (err) { + log_err("init_new_quota_inode failed"); + goto out_err; + } + h->qh_qf.ino = qf_inum; + h->qh_file_flags = EXT2_FILE_WRITE | EXT2_FILE_CREATE; + h->e2fs_write = quota_write_nomount; + h->e2fs_read = quota_read_nomount; + + log_debug("Creating quota ino=%u, type=%d", qf_inum, qtype); + err = ext2fs_file_open(fs, qf_inum, h->qh_file_flags, &e2_file); + if (err) { + log_err("ext2fs_file_open failed: %ld", err); + goto out_err; + } + h->qh_qf.e2_file = e2_file; + + h->qh_io_flags = 0; + h->qh_type = qtype; + h->qh_fmt = fmt; + memset(&h->qh_info, 0, sizeof(h->qh_info)); + h->qh_ops = "afile_ops_2; + + if (h->qh_ops->new_io && (h->qh_ops->new_io(h) < 0)) { + log_err("qh_ops->new_io failed"); + err = EIO; + goto out_err1; + } + + return 0; + +out_err1: + ext2fs_file_close(e2_file); +out_err: + + if (qf_inum) + quota_inode_truncate(fs, qf_inum); + + return err; +} + +/* + * Close quotafile and release handle + */ +errcode_t quota_file_close(quota_ctx_t qctx, struct quota_handle *h) +{ + if (h->qh_io_flags & IOFL_INFODIRTY) { + if (h->qh_ops->write_info && h->qh_ops->write_info(h) < 0) + return EIO; + h->qh_io_flags &= ~IOFL_INFODIRTY; + } + + if (h->qh_ops->end_io && h->qh_ops->end_io(h) < 0) + return EIO; + if (h->qh_qf.e2_file) + ext2fs_file_close(h->qh_qf.e2_file); + if (qctx->quota_file[h->qh_type] == h) + ext2fs_free_mem(&qctx->quota_file[h->qh_type]); + return 0; +} + +/* + * Create empty quota structure + */ +struct dquot *get_empty_dquot(void) +{ + struct dquot *dquot; + + if (ext2fs_get_memzero(sizeof(struct dquot), &dquot)) { + log_err("Failed to allocate dquot"); + return NULL; + } + + dquot->dq_id = -1; + return dquot; +} diff --git a/lib/support/quotaio.h b/lib/support/quotaio.h new file mode 100644 index 0000000..84fac35 --- /dev/null +++ b/lib/support/quotaio.h @@ -0,0 +1,268 @@ +/** quotaio.h + * + * Interface to the quota library. + * + * The quota library provides interface for creating and updating the quota + * files and the ext4 superblock fields. It supports the new VFS_V1 quota + * format. The quota library also provides support for keeping track of quotas + * in memory. + * The typical way to use the quota library is as follows: + * { + * quota_ctx_t qctx; + * + * quota_init_context(&qctx, fs, QUOTA_ALL_BIT); + * { + * quota_compute_usage(qctx); + * AND/OR + * quota_data_add/quota_data_sub/quota_data_inodes(); + * } + * quota_write_inode(qctx, USRQUOTA); + * quota_write_inode(qctx, GRPQUOTA); + * quota_release_context(&qctx); + * } + * + * This initial version does not support reading the quota files. This support + * will be added in near future. + * + * Aditya Kali + * Header of IO operations for quota utilities + * + * Jan Kara + */ + +#ifndef GUARD_QUOTAIO_H +#define GUARD_QUOTAIO_H + +#include +#include +#include + +#include "ext2fs/ext2_fs.h" +#include "ext2fs/ext2fs.h" +#include "dqblk_v2.h" + +typedef int64_t qsize_t; /* Type in which we store size limitations */ + +enum quota_type { + USRQUOTA = 0, + GRPQUOTA = 1, + PRJQUOTA = 2, + MAXQUOTAS = 3, +}; + +#if MAXQUOTAS > 32 +#error "cannot have more than 32 quota types to fit in qtype_bits" +#endif + +#define QUOTA_USR_BIT (1 << USRQUOTA) +#define QUOTA_GRP_BIT (1 << GRPQUOTA) +#define QUOTA_PRJ_BIT (1 << PRJQUOTA) +#define QUOTA_ALL_BIT (QUOTA_USR_BIT | QUOTA_GRP_BIT | QUOTA_PRJ_BIT) + +typedef struct quota_ctx *quota_ctx_t; +struct dict_t; + +struct quota_ctx { + ext2_filsys fs; + struct dict_t *quota_dict[MAXQUOTAS]; + struct quota_handle *quota_file[MAXQUOTAS]; +}; + +/* + * Definitions of magics and versions of current quota files + */ +#define INITQMAGICS {\ + 0xd9c01f11, /* USRQUOTA */\ + 0xd9c01927, /* GRPQUOTA */\ + 0xd9c03f14 /* PRJQUOTA */\ +} + +/* Size of blocks in which are counted size limits in generic utility parts */ +#define QUOTABLOCK_BITS 10 +#define QUOTABLOCK_SIZE (1 << QUOTABLOCK_BITS) +#define toqb(x) (((x) + QUOTABLOCK_SIZE - 1) >> QUOTABLOCK_BITS) + +/* Quota format type IDs */ +#define QFMT_VFS_OLD 1 +#define QFMT_VFS_V0 2 +#define QFMT_VFS_V1 4 + +/* + * The following constants define the default amount of time given a user + * before the soft limits are treated as hard limits (usually resulting + * in an allocation failure). The timer is started when the user crosses + * their soft limit, it is reset when they go below their soft limit. + */ +#define MAX_IQ_TIME 604800 /* (7*24*60*60) 1 week */ +#define MAX_DQ_TIME 604800 /* (7*24*60*60) 1 week */ + +#define IOFL_INFODIRTY 0x01 /* Did info change? */ + +struct quotafile_ops; + +/* Generic information about quotafile */ +struct util_dqinfo { + time_t dqi_bgrace; /* Block grace time for given quotafile */ + time_t dqi_igrace; /* Inode grace time for given quotafile */ + union { + struct v2_mem_dqinfo v2_mdqi; + } u; /* Format specific info about quotafile */ +}; + +struct quota_file { + ext2_filsys fs; + ext2_ino_t ino; + ext2_file_t e2_file; +}; + +/* Structure for one opened quota file */ +struct quota_handle { + enum quota_type qh_type; /* Type of quotafile */ + int qh_fmt; /* Quotafile format */ + int qh_file_flags; + int qh_io_flags; /* IO flags for file */ + struct quota_file qh_qf; + unsigned int (*e2fs_read)(struct quota_file *qf, ext2_loff_t offset, + void *buf, unsigned int size); + unsigned int (*e2fs_write)(struct quota_file *qf, ext2_loff_t offset, + void *buf, unsigned int size); + struct quotafile_ops *qh_ops; /* Operations on quotafile */ + struct util_dqinfo qh_info; /* Generic quotafile info */ +}; + +/* Utility quota block */ +struct util_dqblk { + qsize_t dqb_ihardlimit; + qsize_t dqb_isoftlimit; + qsize_t dqb_curinodes; + qsize_t dqb_bhardlimit; + qsize_t dqb_bsoftlimit; + qsize_t dqb_curspace; + time_t dqb_btime; + time_t dqb_itime; + union { + struct v2_mem_dqblk v2_mdqb; + } u; /* Format specific dquot information */ +}; + +/* Structure for one loaded quota */ +struct dquot { + struct dquot *dq_next; /* Pointer to next dquot in the list */ + qid_t dq_id; /* ID dquot belongs to */ + int dq_flags; /* Some flags for utils */ + struct quota_handle *dq_h; /* Handle of quotafile for this dquot */ + struct util_dqblk dq_dqb; /* Parsed data of dquot */ +}; + +#define DQF_SEEN 0x0001 + +/* Structure of quotafile operations */ +struct quotafile_ops { + /* Check whether quotafile is in our format */ + int (*check_file) (struct quota_handle *h, int type, int fmt); + /* Open quotafile */ + int (*init_io) (struct quota_handle *h); + /* Create new quotafile */ + int (*new_io) (struct quota_handle *h); + /* Write all changes and close quotafile */ + int (*end_io) (struct quota_handle *h); + /* Write info about quotafile */ + int (*write_info) (struct quota_handle *h); + /* Read dquot into memory */ + struct dquot *(*read_dquot) (struct quota_handle *h, qid_t id); + /* Write given dquot to disk */ + int (*commit_dquot) (struct dquot *dquot); + /* Scan quotafile and call callback on every structure */ + int (*scan_dquots) (struct quota_handle *h, + int (*process_dquot) (struct dquot *dquot, + void *data), + void *data); + /* Function to print format specific file information */ + int (*report) (struct quota_handle *h, int verbose); +}; + +/* This might go into a special header file but that sounds a bit silly... */ +extern struct quotafile_ops quotafile_ops_meta; + +/* Open existing quotafile of given type (and verify its format) on given + * filesystem. */ +errcode_t quota_file_open(quota_ctx_t qctx, struct quota_handle *h, + ext2_ino_t qf_ino, enum quota_type type, + int fmt, int flags); + + +/* Create new quotafile of specified format on given filesystem */ +errcode_t quota_file_create(struct quota_handle *h, ext2_filsys fs, + enum quota_type qtype, int fmt); + +/* Close quotafile */ +errcode_t quota_file_close(quota_ctx_t qctx, struct quota_handle *h); + +/* Get empty quota structure */ +struct dquot *get_empty_dquot(void); + +errcode_t quota_inode_truncate(ext2_filsys fs, ext2_ino_t ino); + +const char *quota_type2name(enum quota_type qtype); +ext2_ino_t quota_type2inum(enum quota_type qtype, struct ext2_super_block *); + +void update_grace_times(struct dquot *q); + +/* size for the buffer returned by quota_get_qf_name(); must be greater + than maxlen of extensions[] and fmtnames[] (plus 2) found in quotaio.c */ +#define QUOTA_NAME_LEN 16 + +const char *quota_get_qf_name(enum quota_type, int fmt, char *buf); + +/* In mkquota.c */ +errcode_t quota_init_context(quota_ctx_t *qctx, ext2_filsys fs, + unsigned int qtype_bits); +void quota_data_inodes(quota_ctx_t qctx, struct ext2_inode_large *inode, + ext2_ino_t ino, int adjust); +void quota_data_add(quota_ctx_t qctx, struct ext2_inode_large *inode, + ext2_ino_t ino, qsize_t space); +void quota_data_sub(quota_ctx_t qctx, struct ext2_inode_large *inode, + ext2_ino_t ino, qsize_t space); +errcode_t quota_write_inode(quota_ctx_t qctx, enum quota_type qtype); +/* Flags for quota_read_all_dquots() */ +#define QREAD_USAGE 0x01 +#define QREAD_LIMITS 0x02 +errcode_t quota_read_all_dquots(quota_ctx_t qctx, ext2_ino_t qf_ino, + enum quota_type type, unsigned int flags); +errcode_t quota_compute_usage(quota_ctx_t qctx); +void quota_release_context(quota_ctx_t *qctx); +errcode_t quota_remove_inode(ext2_filsys fs, enum quota_type qtype); +int quota_file_exists(ext2_filsys fs, enum quota_type qtype); +void quota_set_sb_inum(ext2_filsys fs, ext2_ino_t ino, enum quota_type qtype); +errcode_t quota_compare_and_update(quota_ctx_t qctx, enum quota_type qtype, + int *usage_inconsistent); +int parse_quota_opts(const char *opts, int (*func)(char *)); + +/* parse_qtype.c */ +int parse_quota_types(const char *in_str, unsigned int *qtype_bits, + char **err_token); + +/* + * Return pointer to reserved inode field in superblock for given quota type. + * + * This allows the caller to get or set the quota inode by type without the + * need for the quota array to be contiguous in the superblock. + */ +static inline ext2_ino_t *quota_sb_inump(struct ext2_super_block *sb, + enum quota_type qtype) +{ + switch (qtype) { + case USRQUOTA: + return &sb->s_usr_quota_inum; + case GRPQUOTA: + return &sb->s_grp_quota_inum; + case PRJQUOTA: + return &sb->s_prj_quota_inum; + default: + return NULL; + } + + return NULL; +} + +#endif /* GUARD_QUOTAIO_H */ diff --git a/lib/support/quotaio_tree.c b/lib/support/quotaio_tree.c new file mode 100644 index 0000000..5910e63 --- /dev/null +++ b/lib/support/quotaio_tree.c @@ -0,0 +1,687 @@ +/* + * Implementation of new quotafile format + * + * Jan Kara - sponsored by SuSE CR + */ + +#include "config.h" +#include +#include +#include +#include +#include +#include + +#include "common.h" +#include "quotaio_tree.h" +#include "quotaio.h" + +typedef char *dqbuf_t; + +#define freedqbuf(buf) ext2fs_free_mem(&buf) + +static inline dqbuf_t getdqbuf(void) +{ + dqbuf_t buf; + if (ext2fs_get_memzero(QT_BLKSIZE, &buf)) { + log_err("Failed to allocate dqbuf"); + return NULL; + } + + return buf; +} + +/* Is given dquot empty? */ +int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk) +{ + unsigned int i; + + for (i = 0; i < info->dqi_entry_size; i++) + if (disk[i]) + return 0; + return 1; +} + +int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info) +{ + return (QT_BLKSIZE - sizeof(struct qt_disk_dqdbheader)) / + info->dqi_entry_size; +} + +static int get_index(qid_t id, int depth) +{ + return (id >> ((QT_TREEDEPTH - depth - 1) * 8)) & 0xff; +} + +static inline void mark_quotafile_info_dirty(struct quota_handle *h) +{ + h->qh_io_flags |= IOFL_INFODIRTY; +} + +/* Read given block */ +static void read_blk(struct quota_handle *h, unsigned int blk, dqbuf_t buf) +{ + int err; + + err = h->e2fs_read(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf, + QT_BLKSIZE); + if (err < 0) + log_err("Cannot read block %u: %s", blk, strerror(errno)); + else if (err != QT_BLKSIZE) + memset(buf + err, 0, QT_BLKSIZE - err); +} + +/* Write block */ +static int write_blk(struct quota_handle *h, unsigned int blk, dqbuf_t buf) +{ + int err; + + err = h->e2fs_write(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf, + QT_BLKSIZE); + if (err < 0 && errno != ENOSPC) + log_err("Cannot write block (%u): %s", blk, strerror(errno)); + if (err != QT_BLKSIZE) + return -ENOSPC; + return 0; +} + +/* Get free block in file (either from free list or create new one) */ +static int get_free_dqblk(struct quota_handle *h) +{ + dqbuf_t buf = getdqbuf(); + struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; + struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; + int blk; + + if (!buf) + return -ENOMEM; + + if (info->dqi_free_blk) { + blk = info->dqi_free_blk; + read_blk(h, blk, buf); + info->dqi_free_blk = ext2fs_le32_to_cpu(dh->dqdh_next_free); + } else { + memset(buf, 0, QT_BLKSIZE); + /* Assure block allocation... */ + if (write_blk(h, info->dqi_blocks, buf) < 0) { + freedqbuf(buf); + log_err("Cannot allocate new quota block " + "(out of disk space)."); + return -ENOSPC; + } + blk = info->dqi_blocks++; + } + mark_quotafile_info_dirty(h); + freedqbuf(buf); + return blk; +} + +/* Put given block to free list */ +static void put_free_dqblk(struct quota_handle *h, dqbuf_t buf, + unsigned int blk) +{ + struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; + struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; + + dh->dqdh_next_free = ext2fs_cpu_to_le32(info->dqi_free_blk); + dh->dqdh_prev_free = ext2fs_cpu_to_le32(0); + dh->dqdh_entries = ext2fs_cpu_to_le16(0); + info->dqi_free_blk = blk; + mark_quotafile_info_dirty(h); + write_blk(h, blk, buf); +} + +/* Remove given block from the list of blocks with free entries */ +static void remove_free_dqentry(struct quota_handle *h, dqbuf_t buf, + unsigned int blk) +{ + dqbuf_t tmpbuf = getdqbuf(); + struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; + unsigned int nextblk = ext2fs_le32_to_cpu(dh->dqdh_next_free), prevblk = + + ext2fs_le32_to_cpu(dh->dqdh_prev_free); + + if (!tmpbuf) + return; + + if (nextblk) { + read_blk(h, nextblk, tmpbuf); + ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free = + dh->dqdh_prev_free; + write_blk(h, nextblk, tmpbuf); + } + if (prevblk) { + read_blk(h, prevblk, tmpbuf); + ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_next_free = + dh->dqdh_next_free; + write_blk(h, prevblk, tmpbuf); + } else { + h->qh_info.u.v2_mdqi.dqi_qtree.dqi_free_entry = nextblk; + mark_quotafile_info_dirty(h); + } + freedqbuf(tmpbuf); + dh->dqdh_next_free = dh->dqdh_prev_free = ext2fs_cpu_to_le32(0); + write_blk(h, blk, buf); /* No matter whether write succeeds + * block is out of list */ +} + +/* Insert given block to the beginning of list with free entries */ +static void insert_free_dqentry(struct quota_handle *h, dqbuf_t buf, + unsigned int blk) +{ + dqbuf_t tmpbuf = getdqbuf(); + struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; + struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; + + if (!tmpbuf) + return; + + dh->dqdh_next_free = ext2fs_cpu_to_le32(info->dqi_free_entry); + dh->dqdh_prev_free = ext2fs_cpu_to_le32(0); + write_blk(h, blk, buf); + if (info->dqi_free_entry) { + read_blk(h, info->dqi_free_entry, tmpbuf); + ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free = + ext2fs_cpu_to_le32(blk); + write_blk(h, info->dqi_free_entry, tmpbuf); + } + freedqbuf(tmpbuf); + info->dqi_free_entry = blk; + mark_quotafile_info_dirty(h); +} + +/* Find space for dquot */ +static unsigned int find_free_dqentry(struct quota_handle *h, + struct dquot *dquot, int *err) +{ + int blk, i; + struct qt_disk_dqdbheader *dh; + struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; + char *ddquot; + dqbuf_t buf; + + *err = 0; + buf = getdqbuf(); + if (!buf) { + *err = -ENOMEM; + return 0; + } + + dh = (struct qt_disk_dqdbheader *)buf; + if (info->dqi_free_entry) { + blk = info->dqi_free_entry; + read_blk(h, blk, buf); + } else { + blk = get_free_dqblk(h); + if (blk < 0) { + freedqbuf(buf); + *err = blk; + return 0; + } + memset(buf, 0, QT_BLKSIZE); + info->dqi_free_entry = blk; + mark_quotafile_info_dirty(h); + } + + /* Block will be full? */ + if (ext2fs_le16_to_cpu(dh->dqdh_entries) + 1 >= + qtree_dqstr_in_blk(info)) + remove_free_dqentry(h, buf, blk); + + dh->dqdh_entries = + ext2fs_cpu_to_le16(ext2fs_le16_to_cpu(dh->dqdh_entries) + 1); + /* Find free structure in block */ + ddquot = buf + sizeof(struct qt_disk_dqdbheader); + for (i = 0; + i < qtree_dqstr_in_blk(info) && !qtree_entry_unused(info, ddquot); + i++) + ddquot += info->dqi_entry_size; + + if (i == qtree_dqstr_in_blk(info)) + log_err("find_free_dqentry(): Data block full unexpectedly."); + + write_blk(h, blk, buf); + dquot->dq_dqb.u.v2_mdqb.dqb_off = + (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) + + i * info->dqi_entry_size; + freedqbuf(buf); + return blk; +} + +/* Insert reference to structure into the trie */ +static int do_insert_tree(struct quota_handle *h, struct dquot *dquot, + unsigned int * treeblk, int depth) +{ + dqbuf_t buf; + int newson = 0, newact = 0; + __le32 *ref; + unsigned int newblk; + int ret = 0; + + log_debug("inserting in tree: treeblk=%u, depth=%d", *treeblk, depth); + buf = getdqbuf(); + if (!buf) + return -ENOMEM; + + if (!*treeblk) { + ret = get_free_dqblk(h); + if (ret < 0) + goto out_buf; + *treeblk = ret; + memset(buf, 0, QT_BLKSIZE); + newact = 1; + } else { + read_blk(h, *treeblk, buf); + } + + ref = (__le32 *) buf; + newblk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]); + if (!newblk) + newson = 1; + if (depth == QT_TREEDEPTH - 1) { + if (newblk) + log_err("Inserting already present quota entry " + "(block %u).", + ref[get_index(dquot->dq_id, depth)]); + newblk = find_free_dqentry(h, dquot, &ret); + } else { + ret = do_insert_tree(h, dquot, &newblk, depth + 1); + } + + if (newson && ret >= 0) { + ref[get_index(dquot->dq_id, depth)] = + ext2fs_cpu_to_le32(newblk); + write_blk(h, *treeblk, buf); + } else if (newact && ret < 0) { + put_free_dqblk(h, buf, *treeblk); + } + +out_buf: + freedqbuf(buf); + return ret; +} + +/* Wrapper for inserting quota structure into tree */ +static void dq_insert_tree(struct quota_handle *h, struct dquot *dquot) +{ + unsigned int tmp = QT_TREEOFF; + + if (do_insert_tree(h, dquot, &tmp, 0) < 0) + log_err("Cannot write quota (id %u): %s", + (unsigned int) dquot->dq_id, strerror(errno)); +} + +/* Write dquot to file */ +void qtree_write_dquot(struct dquot *dquot) +{ + errcode_t retval; + unsigned int ret; + char *ddquot; + struct quota_handle *h = dquot->dq_h; + struct qtree_mem_dqinfo *info = + &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree; + log_debug("writing ddquot 1: off=%llu, info->dqi_entry_size=%u", + dquot->dq_dqb.u.v2_mdqb.dqb_off, + info->dqi_entry_size); + retval = ext2fs_get_mem(info->dqi_entry_size, &ddquot); + if (retval) { + errno = ENOMEM; + log_err("Quota write failed (id %u): %s", + (unsigned int)dquot->dq_id, strerror(errno)); + return; + } + memset(ddquot, 0, info->dqi_entry_size); + + if (!dquot->dq_dqb.u.v2_mdqb.dqb_off) + dq_insert_tree(dquot->dq_h, dquot); + info->dqi_ops->mem2disk_dqblk(ddquot, dquot); + log_debug("writing ddquot 2: off=%llu, info->dqi_entry_size=%u", + dquot->dq_dqb.u.v2_mdqb.dqb_off, + info->dqi_entry_size); + ret = h->e2fs_write(&h->qh_qf, dquot->dq_dqb.u.v2_mdqb.dqb_off, ddquot, + info->dqi_entry_size); + + if (ret != info->dqi_entry_size) { + if (ret > 0) + errno = ENOSPC; + log_err("Quota write failed (id %u): %s", + (unsigned int)dquot->dq_id, strerror(errno)); + } + ext2fs_free_mem(&ddquot); +} + +/* Free dquot entry in data block */ +static void free_dqentry(struct quota_handle *h, struct dquot *dquot, + unsigned int blk) +{ + struct qt_disk_dqdbheader *dh; + struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; + dqbuf_t buf = getdqbuf(); + + if (!buf) + return; + + if (dquot->dq_dqb.u.v2_mdqb.dqb_off >> QT_BLKSIZE_BITS != blk) + log_err("Quota structure has offset to other block (%u) " + "than it should (%u).", blk, + (unsigned int) (dquot->dq_dqb.u.v2_mdqb.dqb_off >> + QT_BLKSIZE_BITS)); + + read_blk(h, blk, buf); + dh = (struct qt_disk_dqdbheader *)buf; + dh->dqdh_entries = + ext2fs_cpu_to_le16(ext2fs_le16_to_cpu(dh->dqdh_entries) - 1); + + if (!ext2fs_le16_to_cpu(dh->dqdh_entries)) { /* Block got free? */ + remove_free_dqentry(h, buf, blk); + put_free_dqblk(h, buf, blk); + } else { + memset(buf + (dquot->dq_dqb.u.v2_mdqb.dqb_off & + ((1 << QT_BLKSIZE_BITS) - 1)), + 0, info->dqi_entry_size); + + /* First free entry? */ + if (ext2fs_le16_to_cpu(dh->dqdh_entries) == + qtree_dqstr_in_blk(info) - 1) + /* This will also write data block */ + insert_free_dqentry(h, buf, blk); + else + write_blk(h, blk, buf); + } + dquot->dq_dqb.u.v2_mdqb.dqb_off = 0; + freedqbuf(buf); +} + +/* Remove reference to dquot from tree */ +static void remove_tree(struct quota_handle *h, struct dquot *dquot, + unsigned int * blk, int depth) +{ + dqbuf_t buf = getdqbuf(); + unsigned int newblk; + __le32 *ref = (__le32 *) buf; + + if (!buf) + return; + + read_blk(h, *blk, buf); + newblk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]); + if (depth == QT_TREEDEPTH - 1) { + free_dqentry(h, dquot, newblk); + newblk = 0; + } else { + remove_tree(h, dquot, &newblk, depth + 1); + } + + if (!newblk) { + int i; + + ref[get_index(dquot->dq_id, depth)] = ext2fs_cpu_to_le32(0); + + /* Block got empty? */ + for (i = 0; i < QT_BLKSIZE && !buf[i]; i++); + + /* Don't put the root block into the free block list */ + if (i == QT_BLKSIZE && *blk != QT_TREEOFF) { + put_free_dqblk(h, buf, *blk); + *blk = 0; + } else { + write_blk(h, *blk, buf); + } + } + freedqbuf(buf); +} + +/* Delete dquot from tree */ +void qtree_delete_dquot(struct dquot *dquot) +{ + unsigned int tmp = QT_TREEOFF; + + if (!dquot->dq_dqb.u.v2_mdqb.dqb_off) /* Even not allocated? */ + return; + remove_tree(dquot->dq_h, dquot, &tmp, 0); +} + +/* Find entry in block */ +static ext2_loff_t find_block_dqentry(struct quota_handle *h, + struct dquot *dquot, unsigned int blk) +{ + struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; + dqbuf_t buf = getdqbuf(); + int i; + char *ddquot = buf + sizeof(struct qt_disk_dqdbheader); + + if (!buf) + return -ENOMEM; + + read_blk(h, blk, buf); + for (i = 0; + i < qtree_dqstr_in_blk(info) && !info->dqi_ops->is_id(ddquot, dquot); + i++) + ddquot += info->dqi_entry_size; + + if (i == qtree_dqstr_in_blk(info)) + log_err("Quota for id %u referenced but not present.", + dquot->dq_id); + freedqbuf(buf); + return (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) + + i * info->dqi_entry_size; +} + +/* Find entry for given id in the tree */ +static ext2_loff_t find_tree_dqentry(struct quota_handle *h, + struct dquot *dquot, + unsigned int blk, int depth) +{ + dqbuf_t buf = getdqbuf(); + ext2_loff_t ret = 0; + __le32 *ref = (__le32 *) buf; + + if (!buf) + return -ENOMEM; + + read_blk(h, blk, buf); + ret = 0; + blk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]); + if (!blk) /* No reference? */ + goto out_buf; + if (depth < QT_TREEDEPTH - 1) + ret = find_tree_dqentry(h, dquot, blk, depth + 1); + else + ret = find_block_dqentry(h, dquot, blk); +out_buf: + freedqbuf(buf); + return ret; +} + +/* Find entry for given id in the tree - wrapper function */ +static inline ext2_loff_t find_dqentry(struct quota_handle *h, + struct dquot *dquot) +{ + return find_tree_dqentry(h, dquot, QT_TREEOFF, 0); +} + +/* + * Read dquot from disk. + */ +struct dquot *qtree_read_dquot(struct quota_handle *h, qid_t id) +{ + struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; + ext2_loff_t offset; + unsigned int ret; + char *ddquot; + struct dquot *dquot = get_empty_dquot(); + + if (!dquot) + return NULL; + if (ext2fs_get_mem(info->dqi_entry_size, &ddquot)) { + ext2fs_free_mem(&dquot); + return NULL; + } + + dquot->dq_id = id; + dquot->dq_h = h; + dquot->dq_dqb.u.v2_mdqb.dqb_off = 0; + memset(&dquot->dq_dqb, 0, sizeof(struct util_dqblk)); + + offset = find_dqentry(h, dquot); + if (offset > 0) { + dquot->dq_dqb.u.v2_mdqb.dqb_off = offset; + ret = h->e2fs_read(&h->qh_qf, offset, ddquot, + info->dqi_entry_size); + if (ret != info->dqi_entry_size) { + if (ret > 0) + errno = EIO; + log_err("Cannot read quota structure for id %u: %s", + dquot->dq_id, strerror(errno)); + } + info->dqi_ops->disk2mem_dqblk(dquot, ddquot); + } + ext2fs_free_mem(&ddquot); + return dquot; +} + +static int check_reference(struct quota_handle *h, unsigned int blk) +{ + if (blk >= h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks) { + log_err("Illegal reference (%u >= %u) in %s quota file", + blk, h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks, + quota_type2name(h->qh_type)); + return -1; + } + return 0; +} + +/* + * Scan all dquots in file and call callback on each + */ +#define set_bit(bmp, ind) ((bmp)[(ind) >> 3] |= (1 << ((ind) & 7))) +#define get_bit(bmp, ind) ((bmp)[(ind) >> 3] & (1 << ((ind) & 7))) + +static int report_block(struct dquot *dquot, unsigned int blk, char *bitmap, + int (*process_dquot) (struct dquot *, void *), + void *data) +{ + struct qtree_mem_dqinfo *info = + &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree; + dqbuf_t buf = getdqbuf(); + struct qt_disk_dqdbheader *dh; + char *ddata; + int entries, i; + + if (!buf) + return -1; + + set_bit(bitmap, blk); + read_blk(dquot->dq_h, blk, buf); + dh = (struct qt_disk_dqdbheader *)buf; + ddata = buf + sizeof(struct qt_disk_dqdbheader); + entries = ext2fs_le16_to_cpu(dh->dqdh_entries); + for (i = 0; i < qtree_dqstr_in_blk(info); + i++, ddata += info->dqi_entry_size) + if (!qtree_entry_unused(info, ddata)) { + dquot->dq_dqb.u.v2_mdqb.dqb_off = + (blk << QT_BLKSIZE_BITS) + + sizeof(struct qt_disk_dqdbheader) + + i * info->dqi_entry_size; + info->dqi_ops->disk2mem_dqblk(dquot, ddata); + if (process_dquot(dquot, data) < 0) + break; + } + freedqbuf(buf); + return entries; +} + +static int report_tree(struct dquot *dquot, unsigned int blk, int depth, + char *bitmap, + int (*process_dquot) (struct dquot *, void *), + void *data) +{ + int entries = 0, ret, i; + dqbuf_t buf = getdqbuf(); + __le32 *ref = (__le32 *) buf; + + if (!buf) + return -1; + + read_blk(dquot->dq_h, blk, buf); + if (depth == QT_TREEDEPTH - 1) { + for (i = 0; i < QT_BLKSIZE >> 2; i++) { + blk = ext2fs_le32_to_cpu(ref[i]); + if (check_reference(dquot->dq_h, blk)) { + entries = -1; + goto errout; + } + if (blk && !get_bit(bitmap, blk)) { + ret = report_block(dquot, blk, bitmap, + process_dquot, data); + if (ret < 0) { + entries = ret; + goto errout; + } + entries += ret; + } + } + } else { + for (i = 0; i < QT_BLKSIZE >> 2; i++) { + blk = ext2fs_le32_to_cpu(ref[i]); + if (blk) { + if (check_reference(dquot->dq_h, blk)) { + entries = -1; + goto errout; + } + ret = report_tree(dquot, blk, depth + 1, + bitmap, process_dquot, + data); + if (ret < 0) { + entries = ret; + goto errout; + } + entries += ret; + } + } + } +errout: + freedqbuf(buf); + return entries; +} + +static unsigned int find_set_bits(char *bmp, int blocks) +{ + unsigned int used = 0; + int i; + + for (i = 0; i < blocks; i++) + if (get_bit(bmp, i)) + used++; + return used; +} + +int qtree_scan_dquots(struct quota_handle *h, + int (*process_dquot) (struct dquot *, void *), + void *data) +{ + int ret; + char *bitmap; + struct v2_mem_dqinfo *v2info = &h->qh_info.u.v2_mdqi; + struct qtree_mem_dqinfo *info = &v2info->dqi_qtree; + struct dquot *dquot = get_empty_dquot(); + + if (!dquot) + return -1; + + dquot->dq_h = h; + if (ext2fs_get_memzero((info->dqi_blocks + 7) >> 3, &bitmap)) { + ext2fs_free_mem(&dquot); + return -1; + } + ret = report_tree(dquot, QT_TREEOFF, 0, bitmap, process_dquot, data); + if (ret < 0) + goto errout; + v2info->dqi_used_entries = ret; + v2info->dqi_data_blocks = find_set_bits(bitmap, info->dqi_blocks); + ret = 0; +errout: + ext2fs_free_mem(&bitmap); + ext2fs_free_mem(&dquot); + return ret; +} diff --git a/lib/support/quotaio_tree.h b/lib/support/quotaio_tree.h new file mode 100644 index 0000000..b0b7257 --- /dev/null +++ b/lib/support/quotaio_tree.h @@ -0,0 +1,64 @@ +/* + * Definitions of structures for vfsv0 quota format + */ + +#ifndef _LINUX_QUOTA_TREE_H +#define _LINUX_QUOTA_TREE_H + +#include + +typedef __u32 qid_t; /* Type in which we store ids in memory */ + +#define QT_TREEOFF 1 /* Offset of tree in file in blocks */ +#define QT_TREEDEPTH 4 /* Depth of quota tree */ +#define QT_BLKSIZE_BITS 10 +#define QT_BLKSIZE (1 << QT_BLKSIZE_BITS) /* Size of block with quota + * structures */ + +/* + * Structure of header of block with quota structures. It is padded to 16 bytes + * so there will be space for exactly 21 quota-entries in a block + */ +struct qt_disk_dqdbheader { + __le32 dqdh_next_free; /* Number of next block with free + * entry */ + __le32 dqdh_prev_free; /* Number of previous block with free + * entry */ + __le16 dqdh_entries; /* Number of valid entries in block */ + __le16 dqdh_pad1; + __le32 dqdh_pad2; +} __attribute__ ((packed)); + +struct dquot; +struct quota_handle; + +/* Operations */ +struct qtree_fmt_operations { + /* Convert given entry from in memory format to disk one */ + void (*mem2disk_dqblk)(void *disk, struct dquot *dquot); + /* Convert given entry from disk format to in memory one */ + void (*disk2mem_dqblk)(struct dquot *dquot, void *disk); + /* Is this structure for given id? */ + int (*is_id)(void *disk, struct dquot *dquot); +}; + +/* In-memory copy of version specific information */ +struct qtree_mem_dqinfo { + unsigned int dqi_blocks; /* # of blocks in quota file */ + unsigned int dqi_free_blk; /* First block in list of free blocks */ + unsigned int dqi_free_entry; /* First block with free entry */ + unsigned int dqi_entry_size; /* Size of quota entry in quota file */ + struct qtree_fmt_operations *dqi_ops; /* Operations for entry + * manipulation */ +}; + +void qtree_write_dquot(struct dquot *dquot); +struct dquot *qtree_read_dquot(struct quota_handle *h, qid_t id); +void qtree_delete_dquot(struct dquot *dquot); +int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk); +int qtree_scan_dquots(struct quota_handle *h, + int (*process_dquot) (struct dquot *, void *), void *data); + +int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info); + +#endif /* _LINUX_QUOTAIO_TREE_H */ diff --git a/lib/support/quotaio_v2.c b/lib/support/quotaio_v2.c new file mode 100644 index 0000000..d09294b --- /dev/null +++ b/lib/support/quotaio_v2.c @@ -0,0 +1,389 @@ +/* + * Implementation of new quotafile format + * + * Jan Kara - sponsored by SuSE CR + */ + +#include "config.h" +#include +#include +#include +#include +#include +#include + +#include "common.h" +#include "quotaio_v2.h" +#include "dqblk_v2.h" +#include "quotaio.h" +#include "quotaio_tree.h" + +static int v2_check_file(struct quota_handle *h, int type, int fmt); +static int v2_init_io(struct quota_handle *h); +static int v2_new_io(struct quota_handle *h); +static int v2_write_info(struct quota_handle *h); +static struct dquot *v2_read_dquot(struct quota_handle *h, qid_t id); +static int v2_commit_dquot(struct dquot *dquot); +static int v2_scan_dquots(struct quota_handle *h, + int (*process_dquot) (struct dquot *dquot, + void *data), + void *data); +static int v2_report(struct quota_handle *h, int verbose); + +struct quotafile_ops quotafile_ops_2 = { + .check_file = v2_check_file, + .init_io = v2_init_io, + .new_io = v2_new_io, + .write_info = v2_write_info, + .read_dquot = v2_read_dquot, + .commit_dquot = v2_commit_dquot, + .scan_dquots = v2_scan_dquots, + .report = v2_report, +}; + +/* + * Copy dquot from disk to memory + */ +static void v2r0_disk2memdqblk(struct dquot *dquot, void *dp) +{ + struct util_dqblk *m = &dquot->dq_dqb; + struct v2r0_disk_dqblk *d = dp, empty; + + dquot->dq_id = ext2fs_le32_to_cpu(d->dqb_id); + m->dqb_ihardlimit = ext2fs_le32_to_cpu(d->dqb_ihardlimit); + m->dqb_isoftlimit = ext2fs_le32_to_cpu(d->dqb_isoftlimit); + m->dqb_bhardlimit = ext2fs_le32_to_cpu(d->dqb_bhardlimit); + m->dqb_bsoftlimit = ext2fs_le32_to_cpu(d->dqb_bsoftlimit); + m->dqb_curinodes = ext2fs_le32_to_cpu(d->dqb_curinodes); + m->dqb_curspace = ext2fs_le64_to_cpu(d->dqb_curspace); + m->dqb_itime = ext2fs_le64_to_cpu(d->dqb_itime); + m->dqb_btime = ext2fs_le64_to_cpu(d->dqb_btime); + + memset(&empty, 0, sizeof(struct v2r0_disk_dqblk)); + empty.dqb_itime = ext2fs_cpu_to_le64(1); + if (!memcmp(&empty, dp, sizeof(struct v2r0_disk_dqblk))) + m->dqb_itime = 0; +} + +/* + * Copy dquot from memory to disk + */ +static void v2r0_mem2diskdqblk(void *dp, struct dquot *dquot) +{ + struct util_dqblk *m = &dquot->dq_dqb; + struct v2r0_disk_dqblk *d = dp; + + d->dqb_ihardlimit = ext2fs_cpu_to_le32(m->dqb_ihardlimit); + d->dqb_isoftlimit = ext2fs_cpu_to_le32(m->dqb_isoftlimit); + d->dqb_bhardlimit = ext2fs_cpu_to_le32(m->dqb_bhardlimit); + d->dqb_bsoftlimit = ext2fs_cpu_to_le32(m->dqb_bsoftlimit); + d->dqb_curinodes = ext2fs_cpu_to_le32(m->dqb_curinodes); + d->dqb_curspace = ext2fs_cpu_to_le64(m->dqb_curspace); + d->dqb_itime = ext2fs_cpu_to_le64(m->dqb_itime); + d->dqb_btime = ext2fs_cpu_to_le64(m->dqb_btime); + d->dqb_id = ext2fs_cpu_to_le32(dquot->dq_id); + if (qtree_entry_unused(&dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree, dp)) + d->dqb_itime = ext2fs_cpu_to_le64(1); +} + +static int v2r0_is_id(void *dp, struct dquot *dquot) +{ + struct v2r0_disk_dqblk *d = dp; + struct qtree_mem_dqinfo *info = + &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree; + + if (qtree_entry_unused(info, dp)) + return 0; + return ext2fs_le32_to_cpu(d->dqb_id) == dquot->dq_id; +} + +static struct qtree_fmt_operations v2r0_fmt_ops = { + .mem2disk_dqblk = v2r0_mem2diskdqblk, + .disk2mem_dqblk = v2r0_disk2memdqblk, + .is_id = v2r0_is_id, +}; + +/* + * Copy dquot from disk to memory + */ +static void v2r1_disk2memdqblk(struct dquot *dquot, void *dp) +{ + struct util_dqblk *m = &dquot->dq_dqb; + struct v2r1_disk_dqblk *d = dp, empty; + + dquot->dq_id = ext2fs_le32_to_cpu(d->dqb_id); + m->dqb_ihardlimit = ext2fs_le64_to_cpu(d->dqb_ihardlimit); + m->dqb_isoftlimit = ext2fs_le64_to_cpu(d->dqb_isoftlimit); + m->dqb_bhardlimit = ext2fs_le64_to_cpu(d->dqb_bhardlimit); + m->dqb_bsoftlimit = ext2fs_le64_to_cpu(d->dqb_bsoftlimit); + m->dqb_curinodes = ext2fs_le64_to_cpu(d->dqb_curinodes); + m->dqb_curspace = ext2fs_le64_to_cpu(d->dqb_curspace); + m->dqb_itime = ext2fs_le64_to_cpu(d->dqb_itime); + m->dqb_btime = ext2fs_le64_to_cpu(d->dqb_btime); + + memset(&empty, 0, sizeof(struct v2r1_disk_dqblk)); + empty.dqb_itime = ext2fs_cpu_to_le64(1); + if (!memcmp(&empty, dp, sizeof(struct v2r1_disk_dqblk))) + m->dqb_itime = 0; +} + +/* + * Copy dquot from memory to disk + */ +static void v2r1_mem2diskdqblk(void *dp, struct dquot *dquot) +{ + struct util_dqblk *m = &dquot->dq_dqb; + struct v2r1_disk_dqblk *d = dp; + + d->dqb_ihardlimit = ext2fs_cpu_to_le64(m->dqb_ihardlimit); + d->dqb_isoftlimit = ext2fs_cpu_to_le64(m->dqb_isoftlimit); + d->dqb_bhardlimit = ext2fs_cpu_to_le64(m->dqb_bhardlimit); + d->dqb_bsoftlimit = ext2fs_cpu_to_le64(m->dqb_bsoftlimit); + d->dqb_curinodes = ext2fs_cpu_to_le64(m->dqb_curinodes); + d->dqb_curspace = ext2fs_cpu_to_le64(m->dqb_curspace); + d->dqb_itime = ext2fs_cpu_to_le64(m->dqb_itime); + d->dqb_btime = ext2fs_cpu_to_le64(m->dqb_btime); + d->dqb_id = ext2fs_cpu_to_le32(dquot->dq_id); + if (qtree_entry_unused(&dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree, dp)) + d->dqb_itime = ext2fs_cpu_to_le64(1); +} + +static int v2r1_is_id(void *dp, struct dquot *dquot) +{ + struct v2r1_disk_dqblk *d = dp; + struct qtree_mem_dqinfo *info = + &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree; + + if (qtree_entry_unused(info, dp)) + return 0; + return ext2fs_le32_to_cpu(d->dqb_id) == dquot->dq_id; +} + +static struct qtree_fmt_operations v2r1_fmt_ops = { + .mem2disk_dqblk = v2r1_mem2diskdqblk, + .disk2mem_dqblk = v2r1_disk2memdqblk, + .is_id = v2r1_is_id, +}; + +/* + * Copy dqinfo from disk to memory + */ +static inline void v2_disk2memdqinfo(struct util_dqinfo *m, + struct v2_disk_dqinfo *d) +{ + m->dqi_bgrace = ext2fs_le32_to_cpu(d->dqi_bgrace); + m->dqi_igrace = ext2fs_le32_to_cpu(d->dqi_igrace); + m->u.v2_mdqi.dqi_flags = ext2fs_le32_to_cpu(d->dqi_flags) & V2_DQF_MASK; + m->u.v2_mdqi.dqi_qtree.dqi_blocks = ext2fs_le32_to_cpu(d->dqi_blocks); + m->u.v2_mdqi.dqi_qtree.dqi_free_blk = + ext2fs_le32_to_cpu(d->dqi_free_blk); + m->u.v2_mdqi.dqi_qtree.dqi_free_entry = + ext2fs_le32_to_cpu(d->dqi_free_entry); +} + +/* + * Copy dqinfo from memory to disk + */ +static inline void v2_mem2diskdqinfo(struct v2_disk_dqinfo *d, + struct util_dqinfo *m) +{ + d->dqi_bgrace = ext2fs_cpu_to_le32(m->dqi_bgrace); + d->dqi_igrace = ext2fs_cpu_to_le32(m->dqi_igrace); + d->dqi_flags = ext2fs_cpu_to_le32(m->u.v2_mdqi.dqi_flags & V2_DQF_MASK); + d->dqi_blocks = ext2fs_cpu_to_le32(m->u.v2_mdqi.dqi_qtree.dqi_blocks); + d->dqi_free_blk = + ext2fs_cpu_to_le32(m->u.v2_mdqi.dqi_qtree.dqi_free_blk); + d->dqi_free_entry = + ext2fs_cpu_to_le32(m->u.v2_mdqi.dqi_qtree.dqi_free_entry); +} + +static int v2_read_header(struct quota_handle *h, struct v2_disk_dqheader *dqh) +{ + if (h->e2fs_read(&h->qh_qf, 0, dqh, sizeof(struct v2_disk_dqheader)) != + sizeof(struct v2_disk_dqheader)) + return 0; + + return 1; +} + +/* + * Check whether given quota file is in our format + */ +static int v2_check_file(struct quota_handle *h, int type, int fmt) +{ + struct v2_disk_dqheader dqh; + int file_magics[] = INITQMAGICS; + int be_magic; + + if (fmt != QFMT_VFS_V1) + return 0; + + if (!v2_read_header(h, &dqh)) + return 0; + + be_magic = ext2fs_be32_to_cpu((__force __be32)dqh.dqh_magic); + if (be_magic == file_magics[type]) { + log_err("Your quota file is stored in wrong endianness"); + return 0; + } + if (V2_VERSION_R0 != ext2fs_le32_to_cpu(dqh.dqh_version) && + V2_VERSION_R1 != ext2fs_le32_to_cpu(dqh.dqh_version)) + return 0; + return 1; +} + +/* + * Open quotafile + */ +static int v2_init_io(struct quota_handle *h) +{ + struct v2_disk_dqheader dqh; + struct v2_disk_dqinfo ddqinfo; + struct v2_mem_dqinfo *info; + __u64 filesize; + int version; + + if (!v2_read_header(h, &dqh)) + return -1; + version = ext2fs_le32_to_cpu(dqh.dqh_version); + + if (version == V2_VERSION_R0) { + h->qh_info.u.v2_mdqi.dqi_qtree.dqi_entry_size = + sizeof(struct v2r0_disk_dqblk); + h->qh_info.u.v2_mdqi.dqi_qtree.dqi_ops = &v2r0_fmt_ops; + } else { + h->qh_info.u.v2_mdqi.dqi_qtree.dqi_entry_size = + sizeof(struct v2r1_disk_dqblk); + h->qh_info.u.v2_mdqi.dqi_qtree.dqi_ops = &v2r1_fmt_ops; + } + + /* Read information about quotafile */ + if (h->e2fs_read(&h->qh_qf, V2_DQINFOOFF, &ddqinfo, + sizeof(ddqinfo)) != sizeof(ddqinfo)) + return -1; + v2_disk2memdqinfo(&h->qh_info, &ddqinfo); + + /* Check to make sure quota file info is sane */ + info = &h->qh_info.u.v2_mdqi; + if (ext2fs_file_get_lsize(h->qh_qf.e2_file, &filesize)) + return -1; + if ((filesize > (1U << 31)) || + (info->dqi_qtree.dqi_blocks > + (filesize + QT_BLKSIZE - 1) >> QT_BLKSIZE_BITS)) { + log_err("Quota inode %u corrupted: file size %llu; " + "dqi_blocks %u", h->qh_qf.ino, + (unsigned long long) filesize, + info->dqi_qtree.dqi_blocks); + return -1; + } + if (info->dqi_qtree.dqi_free_blk >= info->dqi_qtree.dqi_blocks) { + log_err("Quota inode %u corrupted: free_blk %u; dqi_blocks %u", + h->qh_qf.ino, info->dqi_qtree.dqi_free_blk, + info->dqi_qtree.dqi_blocks); + return -1; + } + if (info->dqi_qtree.dqi_free_entry >= info->dqi_qtree.dqi_blocks) { + log_err("Quota inode %u corrupted: free_entry %u; " + "dqi_blocks %u", h->qh_qf.ino, + info->dqi_qtree.dqi_free_entry, + info->dqi_qtree.dqi_blocks); + return -1; + } + return 0; +} + +/* + * Initialize new quotafile + */ +static int v2_new_io(struct quota_handle *h) +{ + int file_magics[] = INITQMAGICS; + struct v2_disk_dqheader ddqheader; + struct v2_disk_dqinfo ddqinfo; + + if (h->qh_fmt != QFMT_VFS_V1) + return -1; + + /* Write basic quota header */ + ddqheader.dqh_magic = ext2fs_cpu_to_le32(file_magics[h->qh_type]); + ddqheader.dqh_version = ext2fs_cpu_to_le32(V2_VERSION_R1); + if (h->e2fs_write(&h->qh_qf, 0, &ddqheader, sizeof(ddqheader)) != + sizeof(ddqheader)) + return -1; + + /* Write information about quotafile */ + h->qh_info.dqi_bgrace = MAX_DQ_TIME; + h->qh_info.dqi_igrace = MAX_IQ_TIME; + h->qh_info.u.v2_mdqi.dqi_flags = 0; + h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks = QT_TREEOFF + 1; + h->qh_info.u.v2_mdqi.dqi_qtree.dqi_free_blk = 0; + h->qh_info.u.v2_mdqi.dqi_qtree.dqi_free_entry = 0; + h->qh_info.u.v2_mdqi.dqi_qtree.dqi_entry_size = + sizeof(struct v2r1_disk_dqblk); + h->qh_info.u.v2_mdqi.dqi_qtree.dqi_ops = &v2r1_fmt_ops; + v2_mem2diskdqinfo(&ddqinfo, &h->qh_info); + if (h->e2fs_write(&h->qh_qf, V2_DQINFOOFF, &ddqinfo, + sizeof(ddqinfo)) != + sizeof(ddqinfo)) + return -1; + + return 0; +} + +/* + * Write information (grace times to file) + */ +static int v2_write_info(struct quota_handle *h) +{ + struct v2_disk_dqinfo ddqinfo; + + v2_mem2diskdqinfo(&ddqinfo, &h->qh_info); + if (h->e2fs_write(&h->qh_qf, V2_DQINFOOFF, &ddqinfo, sizeof(ddqinfo)) != + sizeof(ddqinfo)) + return -1; + + return 0; +} + +/* + * Read dquot from disk + */ +static struct dquot *v2_read_dquot(struct quota_handle *h, qid_t id) +{ + return qtree_read_dquot(h, id); +} + +/* + * Commit changes of dquot to disk - it might also mean deleting it when quota + * became fake one and user has no blocks. + * User can process use 'errno' to detect errstr. + */ +static int v2_commit_dquot(struct dquot *dquot) +{ + struct util_dqblk *b = &dquot->dq_dqb; + + if (!b->dqb_curspace && !b->dqb_curinodes && !b->dqb_bsoftlimit && + !b->dqb_isoftlimit && !b->dqb_bhardlimit && !b->dqb_ihardlimit) + qtree_delete_dquot(dquot); + else + qtree_write_dquot(dquot); + return 0; +} + +static int v2_scan_dquots(struct quota_handle *h, + int (*process_dquot) (struct dquot *, void *), + void *data) +{ + return qtree_scan_dquots(h, process_dquot, data); +} + +/* Report information about quotafile. + * TODO: Not used right now, but we should be able to use this when we add + * support to debugfs to read quota files. + */ +static int v2_report(struct quota_handle *h EXT2FS_ATTR((unused)), + int verbose EXT2FS_ATTR((unused))) +{ + log_err("Not Implemented."); + return -1; +} diff --git a/lib/support/quotaio_v2.h b/lib/support/quotaio_v2.h new file mode 100644 index 0000000..35054ca --- /dev/null +++ b/lib/support/quotaio_v2.h @@ -0,0 +1,69 @@ +/* + * + * Header file for disk format of new quotafile format + * + */ + +#ifndef GUARD_QUOTAIO_V2_H +#define GUARD_QUOTAIO_V2_H + +#include +#include "quotaio.h" + +/* Offset of info header in file */ +#define V2_DQINFOOFF sizeof(struct v2_disk_dqheader) +/* Supported version of quota-tree format */ +#define V2_VERSION_R1 1 +#define V2_VERSION_R0 0 + +struct v2_disk_dqheader { + __le32 dqh_magic; /* Magic number identifying file */ + __le32 dqh_version; /* File version */ +} __attribute__ ((packed)); + +/* Flags for version specific files */ +#define V2_DQF_MASK 0x0000 /* Mask for all valid ondisk flags */ + +/* Header with type and version specific information */ +struct v2_disk_dqinfo { + __le32 dqi_bgrace; /* Time before block soft limit becomes + * hard limit */ + __le32 dqi_igrace; /* Time before inode soft limit becomes + * hard limit */ + __le32 dqi_flags; /* Flags for quotafile (DQF_*) */ + __le32 dqi_blocks; /* Number of blocks in file */ + __le32 dqi_free_blk; /* Number of first free block in the list */ + __le32 dqi_free_entry; /* Number of block with at least one + * free entry */ +} __attribute__ ((packed)); + +struct v2r0_disk_dqblk { + __le32 dqb_id; /* id this quota applies to */ + __le32 dqb_ihardlimit; /* absolute limit on allocated inodes */ + __le32 dqb_isoftlimit; /* preferred inode limit */ + __le32 dqb_curinodes; /* current # allocated inodes */ + __le32 dqb_bhardlimit; /* absolute limit on disk space + * (in QUOTABLOCK_SIZE) */ + __le32 dqb_bsoftlimit; /* preferred limit on disk space + * (in QUOTABLOCK_SIZE) */ + __le64 dqb_curspace; /* current space occupied (in bytes) */ + __le64 dqb_btime; /* time limit for excessive disk use */ + __le64 dqb_itime; /* time limit for excessive inode use */ +} __attribute__ ((packed)); + +struct v2r1_disk_dqblk { + __le32 dqb_id; /* id this quota applies to */ + __le32 dqb_pad; + __le64 dqb_ihardlimit; /* absolute limit on allocated inodes */ + __le64 dqb_isoftlimit; /* preferred inode limit */ + __le64 dqb_curinodes; /* current # allocated inodes */ + __le64 dqb_bhardlimit; /* absolute limit on disk space + * (in QUOTABLOCK_SIZE) */ + __le64 dqb_bsoftlimit; /* preferred limit on disk space + * (in QUOTABLOCK_SIZE) */ + __le64 dqb_curspace; /* current space occupied (in bytes) */ + __le64 dqb_btime; /* time limit for excessive disk use */ + __le64 dqb_itime; /* time limit for excessive inode use */ +} __attribute__ ((packed)); + +#endif diff --git a/lib/support/sort_r.h b/lib/support/sort_r.h new file mode 100644 index 0000000..8473ca8 --- /dev/null +++ b/lib/support/sort_r.h @@ -0,0 +1,325 @@ +/* Isaac Turner 29 April 2014 Public Domain */ +#ifndef SORT_R_H_ +#define SORT_R_H_ + +#include +#include + +/* + +sort_r function to be exported. + +Parameters: + base is the array to be sorted + nel is the number of elements in the array + width is the size in bytes of each element of the array + compar is the comparison function + arg is a pointer to be passed to the comparison function + +void sort_r(void *base, size_t nel, size_t width, + int (*compar)(const void *_a, const void *_b, void *_arg), + void *arg); + +*/ + +#define _SORT_R_INLINE inline + +#if (defined HAVE_GNU_QSORT_R) +# define _SORT_R_GNU +#elif (defined HAVE_BSD_QSORT_R) +# define _SORT_R_BSD +#elif (defined __gnu_hurd__ || defined __GNU__ || \ + defined __MINGW32__ || defined __GLIBC__) +# define _SORT_R_GNU +#elif (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || \ + defined __FreeBSD__ || defined __DragonFly__) +# define _SORT_R_BSD +#elif (defined _WIN32 || defined _WIN64 || defined __WINDOWS__) +# define _SORT_R_WINDOWS +# undef _SORT_R_INLINE +# define _SORT_R_INLINE __inline +#else + /* Using our own recursive quicksort sort_r_simple() */ +#endif + +#if (defined NESTED_QSORT && NESTED_QSORT == 0) +# undef NESTED_QSORT +#endif + +#define SORT_R_SWAP(a,b,tmp) ((tmp) = (a), (a) = (b), (b) = (tmp)) + +/* swap a and b */ +/* a and b must not be equal! */ +static _SORT_R_INLINE void sort_r_swap(char *__restrict a, char *__restrict b, + size_t w) +{ + char tmp, *end = a+w; + for(; a < end; a++, b++) { SORT_R_SWAP(*a, *b, tmp); } +} + +/* swap a, b iff a>b */ +/* a and b must not be equal! */ +/* __restrict is same as restrict but better support on old machines */ +static _SORT_R_INLINE int sort_r_cmpswap(char *__restrict a, + char *__restrict b, size_t w, + int (*compar)(const void *_a, + const void *_b, + void *_arg), + void *arg) +{ + if(compar(a, b, arg) > 0) { + sort_r_swap(a, b, w); + return 1; + } + return 0; +} + +/* +Swap consecutive blocks of bytes of size na and nb starting at memory addr ptr, +with the smallest swap so that the blocks are in the opposite order. Blocks may +be internally re-ordered e.g. + + 12345ab -> ab34512 + 123abc -> abc123 + 12abcde -> deabc12 +*/ +static _SORT_R_INLINE void sort_r_swap_blocks(char *ptr, size_t na, size_t nb) +{ + if(na > 0 && nb > 0) { + if(na > nb) { sort_r_swap(ptr, ptr+na, nb); } + else { sort_r_swap(ptr, ptr+nb, na); } + } +} + +/* Implement recursive quicksort ourselves */ +/* Note: quicksort is not stable, equivalent values may be swapped */ +static _SORT_R_INLINE void sort_r_simple(void *base, size_t nel, size_t w, + int (*compar)(const void *_a, + const void *_b, + void *_arg), + void *arg) +{ + char *b = (char *)base, *end = b + nel*w; + + /* for(size_t i=0; i b && sort_r_cmpswap(pj-w,pj,w,compar,arg); pj -= w) {} + } + } + else + { + /* nel > 6; Quicksort */ + + int cmp; + char *pl, *ple, *pr, *pre, *pivot; + char *last = b+w*(nel-1), *tmp; + + /* + Use median of second, middle and second-last items as pivot. + First and last may have been swapped with pivot and therefore be extreme + */ + char *l[3]; + l[0] = b + w; + l[1] = b+w*(nel/2); + l[2] = last - w; + + /* printf("pivots: %i, %i, %i\n", *(int*)l[0], *(int*)l[1], *(int*)l[2]); */ + + if(compar(l[0],l[1],arg) > 0) { SORT_R_SWAP(l[0], l[1], tmp); } + if(compar(l[1],l[2],arg) > 0) { + SORT_R_SWAP(l[1], l[2], tmp); + if(compar(l[0],l[1],arg) > 0) { SORT_R_SWAP(l[0], l[1], tmp); } + } + + /* swap mid value (l[1]), and last element to put pivot as last element */ + if(l[1] != last) { sort_r_swap(l[1], last, w); } + + /* + pl is the next item on the left to be compared to the pivot + pr is the last item on the right that was compared to the pivot + ple is the left position to put the next item that equals the pivot + ple is the last right position where we put an item that equals the pivot + + v- end (beyond the array) + EEEEEELLLLLLLLuuuuuuuuGGGGGGGEEEEEEEE. + ^- b ^- ple ^- pl ^- pr ^- pre ^- last (where the pivot is) + + Pivot comparison key: + E = equal, L = less than, u = unknown, G = greater than, E = equal + */ + pivot = last; + ple = pl = b; + pre = pr = last; + + /* + Strategy: + Loop into the list from the left and right at the same time to find: + - an item on the left that is greater than the pivot + - an item on the right that is less than the pivot + Once found, they are swapped and the loop continues. + Meanwhile items that are equal to the pivot are moved to the edges of the + array. + */ + while(pl < pr) { + /* Move left hand items which are equal to the pivot to the far left. + break when we find an item that is greater than the pivot */ + for(; pl < pr; pl += w) { + cmp = compar(pl, pivot, arg); + if(cmp > 0) { break; } + else if(cmp == 0) { + if(ple < pl) { sort_r_swap(ple, pl, w); } + ple += w; + } + } + /* break if last batch of left hand items were equal to pivot */ + if(pl >= pr) { break; } + /* Move right hand items which are equal to the pivot to the far right. + break when we find an item that is less than the pivot */ + for(; pl < pr; ) { + pr -= w; /* Move right pointer onto an unprocessed item */ + cmp = compar(pr, pivot, arg); + if(cmp == 0) { + pre -= w; + if(pr < pre) { sort_r_swap(pr, pre, w); } + } + else if(cmp < 0) { + if(pl < pr) { sort_r_swap(pl, pr, w); } + pl += w; + break; + } + } + } + + pl = pr; /* pr may have gone below pl */ + + /* + Now we need to go from: EEELLLGGGGEEEE + to: LLLEEEEEEEGGGG + + Pivot comparison key: + E = equal, L = less than, u = unknown, G = greater than, E = equal + */ + sort_r_swap_blocks(b, ple-b, pl-ple); + sort_r_swap_blocks(pr, pre-pr, end-pre); + + /*for(size_t i=0; icompar)(a, b, ss->arg); + } + + #endif + + #if defined _SORT_R_GNU + + typedef int(* __compar_d_fn_t)(const void *, const void *, void *); + extern void qsort_r(void *base, size_t nel, size_t width, + __compar_d_fn_t __compar, void *arg) + __attribute__((nonnull (1, 4))); + + #endif + + /* implementation */ + + static _SORT_R_INLINE void sort_r(void *base, size_t nel, size_t width, + int (*compar)(const void *_a, + const void *_b, void *_arg), + void *arg) + { + #if defined _SORT_R_GNU + + #if defined __GLIBC__ && ((__GLIBC__ < 2) || (__GLIBC__ == 2 && __GLIBC_MINOR__ < 8)) + + /* no qsort_r in glibc before 2.8, need to use nested qsort */ + sort_r_simple(base, nel, width, compar, arg); + + #else + + qsort_r(base, nel, width, compar, arg); + + #endif + + #elif defined _SORT_R_BSD + + struct sort_r_data tmp; + tmp.arg = arg; + tmp.compar = compar; + qsort_r(base, nel, width, &tmp, sort_r_arg_swap); + + #elif defined _SORT_R_WINDOWS + + struct sort_r_data tmp; + tmp.arg = arg; + tmp.compar = compar; + qsort_s(base, nel, width, sort_r_arg_swap, &tmp); + + #else + + /* Fall back to our own quicksort implementation */ + sort_r_simple(base, nel, width, compar, arg); + + #endif + } + +#endif /* !NESTED_QSORT */ + +#undef _SORT_R_INLINE +#undef _SORT_R_WINDOWS +#undef _SORT_R_GNU +#undef _SORT_R_BSD + +#endif /* SORT_R_H_ */ -- cgit v1.2.3