summaryrefslogtreecommitdiffstats
path: root/lib/support
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--lib/support/Android.bp78
-rw-r--r--lib/support/Makefile.in184
-rw-r--r--lib/support/argv_parse.c168
-rw-r--r--lib/support/argv_parse.h43
-rw-r--r--lib/support/common.h36
-rw-r--r--lib/support/cstring.c162
-rw-r--r--lib/support/cstring.h6
-rw-r--r--lib/support/devname.c65
-rw-r--r--lib/support/devname.h19
-rw-r--r--lib/support/dict.c1542
-rw-r--r--lib/support/dict.h147
-rw-r--r--lib/support/dqblk_v2.h31
-rw-r--r--lib/support/mkquota.c707
-rw-r--r--lib/support/nls-enable.h21
-rw-r--r--lib/support/parse_qtype.c90
-rw-r--r--lib/support/plausible.c287
-rw-r--r--lib/support/plausible.h29
-rw-r--r--lib/support/print_fs_flags.c75
-rw-r--r--lib/support/print_fs_flags.h5
-rw-r--r--lib/support/prof_err.et66
-rw-r--r--lib/support/profile.c1910
-rw-r--r--lib/support/profile.h107
-rw-r--r--lib/support/profile_helpers.c317
-rw-r--r--lib/support/profile_helpers.h28
-rw-r--r--lib/support/quotaio.c412
-rw-r--r--lib/support/quotaio.h268
-rw-r--r--lib/support/quotaio_tree.c687
-rw-r--r--lib/support/quotaio_tree.h64
-rw-r--r--lib/support/quotaio_v2.c389
-rw-r--r--lib/support/quotaio_v2.h69
-rw-r--r--lib/support/sort_r.h325
31 files changed, 8337 insertions, 0 deletions
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 <stdlib.h>
+#endif
+#include <ctype.h>
+#include <string.h>
+#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 <stdio.h>
+
+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 <ext2fs/ext2_types.h>
+#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 <stdio.h>
+#include <stdlib.h>
+#include <ctype.h>
+#ifdef HAVE_GETOPT_H
+#include <getopt.h>
+#endif
+#include <string.h>
+
+#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 <lczerner@redhat.com>
+ *
+ * %Begin-Header%
+ * This file may be redistributed under the terms of the GNU Public
+ * License.
+ * %End-Header%
+ */
+
+#include <unistd.h>
+#include <string.h>
+#include <stdio.h>
+
+#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 <lczerner@redhat.com>
+ *
+ * %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 <kaz@ashi.footprints.net>
+ *
+ * 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 <stdlib.h>
+#include <stddef.h>
+#ifdef DICT_NODEBUG
+#define dict_assert(x)
+#else
+#include <assert.h>
+#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 <stdio.h>
+#include <string.h>
+#include <ctype.h>
+#include <stdarg.h>
+
+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 <key> <val> 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 <key> <val> add value to dictionary\n"
+ "d <key> delete value from dictionary\n"
+ "l <key> lookup value in dictionary\n"
+ "( <key> lookup lower bound\n"
+ ") <key> lookup upper bound\n"
+ "# <num> switch to alternate dictionary (0-9)\n"
+ "j <num> <num> 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 <kaz@ashi.footprints.net>
+ *
+ * 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 <limits.h>
+#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 <jack@suse.cz> - 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 <adityakali@google.com>
+ */
+#include "config.h"
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+#include <errno.h>
+#include <string.h>
+#include <fcntl.h>
+
+#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 <libintl.h>
+#include <locale.h>
+#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 <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+#include <errno.h>
+#include <string.h>
+#include <fcntl.h>
+
+#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 <fcntl.h>
+#include <time.h>
+#include <sys/types.h>
+#ifdef HAVE_SYS_STAT_H
+#include <sys/stat.h>
+#endif
+#ifdef HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+#ifdef HAVE_MAGIC_H
+#include <magic.h>
+#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 <dlfcn.h>
+
+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 <card@masi.ibp.fr>
+ * 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 <stdio.h>
+
+#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 <unistd.h>
+#endif
+#include <stdio.h>
+#ifdef HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+#include <time.h>
+#include <string.h>
+#include <strings.h>
+#include <errno.h>
+#include <ctype.h>
+#include <limits.h>
+#include <stddef.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <dirent.h>
+#ifdef HAVE_PWD_H
+#include <pwd.h>
+#endif
+
+#include <et/com_err.h>
+#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 = "<default>";
+
+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 "<default>". If
+ * the file "<default>" had previously been passed to profile_init(),
+ * then def_string parameter will be parsed and used as the profile
+ * information for the "<default>" 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 <stdlib.h>
+#include <string.h>
+#include <errno.h>
+
+#include <et/com_err.h>
+#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 <jack@suse.cz> - sponsored by SuSE CR
+ * Aditya Kali <adityakali@google.com> - Ported to e2fsprogs
+ */
+
+#include "config.h"
+#include <stdio.h>
+#include <errno.h>
+#include <string.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <time.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/file.h>
+#include <assert.h>
+
+#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 = &quotafile_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 = &quotafile_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 <adityakali@google.com>
+ * Header of IO operations for quota utilities
+ *
+ * Jan Kara <jack@suse.cz>
+ */
+
+#ifndef GUARD_QUOTAIO_H
+#define GUARD_QUOTAIO_H
+
+#include <limits.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+
+#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 <jack@suse.cz> - sponsored by SuSE CR
+ */
+
+#include "config.h"
+#include <sys/types.h>
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#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 <sys/types.h>
+
+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 <jack@suse.cz> - sponsored by SuSE CR
+ */
+
+#include "config.h"
+#include <sys/types.h>
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#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 <sys/types.h>
+#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 <stdlib.h>
+#include <string.h>
+
+/*
+
+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<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
+ printf("\n"); */
+
+ if(nel < 10) {
+ /* Insertion sort for arbitrarily small inputs */
+ char *pi, *pj;
+ for(pi = b+w; pi < end; pi += w) {
+ for(pj = pi; pj > 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; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
+ printf("\n");*/
+
+ sort_r_simple(b, (pl-ple)/w, w, compar, arg);
+ sort_r_simple(end-(pre-pr), (pre-pr)/w, w, compar, arg);
+ }
+}
+
+
+#if defined NESTED_QSORT
+
+ static _SORT_R_INLINE void sort_r(void *base, size_t nel, size_t width,
+ int (*compar)(const void *_a,
+ const void *_b,
+ void *aarg),
+ void *arg)
+ {
+ int nested_cmp(const void *a, const void *b)
+ {
+ return compar(a, b, arg);
+ }
+
+ qsort(base, nel, width, nested_cmp);
+ }
+
+#else /* !NESTED_QSORT */
+
+ /* Declare structs and functions */
+
+ #if defined _SORT_R_BSD
+
+ /* Ensure qsort_r is defined */
+ extern void qsort_r(void *base, size_t nel, size_t width, void *thunk,
+ int (*compar)(void *_thunk,
+ const void *_a, const void *_b));
+
+ #endif
+
+ #if defined _SORT_R_BSD || defined _SORT_R_WINDOWS
+
+ /* BSD (qsort_r), Windows (qsort_s) require argument swap */
+
+ struct sort_r_data
+ {
+ void *arg;
+ int (*compar)(const void *_a, const void *_b, void *_arg);
+ };
+
+ static _SORT_R_INLINE int sort_r_arg_swap(void *s,
+ const void *a, const void *b)
+ {
+ struct sort_r_data *ss = (struct sort_r_data*)s;
+ return (ss->compar)(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_ */