lvm2/libdm/libdm-report.c

/*
 * Copyright (C) 2002-2004 Sistina Software, Inc. All rights reserved.
 * Copyright (C) 2004-2015 Red Hat, Inc. All rights reserved.
 *
 * This file is part of the device-mapper userspace tools.
 *
 * This copyrighted material is made available to anyone wishing to use,
 * modify, copy, or redistribute it subject to the terms and conditions
 * of the GNU Lesser General Public License v.2.1.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include "libdm/misc/dmlib.h"

#include <ctype.h>
#include <math.h>  /* fabs() */
#include <float.h> /* DBL_EPSILON */
#include <time.h>

/*
 * Internal flags
 */
#define RH_SORT_REQUIRED	0x00000100
#define RH_HEADINGS_PRINTED	0x00000200
#define RH_FIELD_CALC_NEEDED	0x00000400
#define RH_ALREADY_REPORTED	0x00000800

struct selection {
	struct dm_pool *mem;
	struct selection_node *selection_root;
	int add_new_fields;
};

struct report_group_item;

struct dm_report {
	struct dm_pool *mem;

	/**
	 * Cache the first row allocated so that all rows and fields
	 * can be disposed of in a single dm_pool_free() call.
	 */
	struct row *first_row;

	/* To report all available types */
#define REPORT_TYPES_ALL	UINT32_MAX
	uint32_t report_types;
	const char *output_field_name_prefix;
	const char *field_prefix;
	uint32_t flags;
	const char *separator;

	uint32_t keys_count;

	/* Ordered list of fields needed for this report */
	struct dm_list field_props;

	/* Rows of report data */
	struct dm_list rows;

	/* Array of field definitions */
	const struct dm_report_field_type *fields;
	const char **canonical_field_ids;
	const struct dm_report_object_type *types;

	/* To store caller private data */
	void *private;

	/* Selection handle */
	struct selection *selection;

	/* Null-terminated array of reserved values */
	const struct dm_report_reserved_value *reserved_values;
	struct dm_hash_table *value_cache;

	struct report_group_item *group_item;
};

struct dm_report_group {
	dm_report_group_type_t type;
	struct dm_pool *mem;
	struct dm_list items;
	int indent;
};

struct report_group_item {
	struct dm_list list;
	struct dm_report_group *group;
	struct dm_report *report;
	union store_u {
		uint32_t orig_report_flags;
		uint32_t finished_count;
	} store;
	struct report_group_item *parent;
	unsigned output_done:1;
	unsigned needs_closing:1;
	void *data;
};

/*
 * Internal per-field flags
 */
#define FLD_HIDDEN	0x00001000
#define FLD_SORT_KEY	0x00002000
#define FLD_ASCENDING	0x00004000
#define FLD_DESCENDING	0x00008000
#define FLD_COMPACTED	0x00010000
#define FLD_COMPACT_ONE 0x00020000

struct field_properties {
	struct dm_list list;
	uint32_t field_num;
	uint32_t sort_posn;
	int32_t initial_width;
	int32_t width; /* current width: adjusted by dm_report_object() */
	const struct dm_report_object_type *type;
	uint32_t flags;
	int implicit;
};

/*
 * Report selection
 */
struct op_def {
	const char *string;
	uint32_t flags;
	const char *desc;
};

#define FLD_CMP_MASK		0x0FF00000
#define FLD_CMP_UNCOMPARABLE	0x00100000
#define FLD_CMP_EQUAL		0x00200000
#define FLD_CMP_NOT		0x00400000
#define FLD_CMP_GT		0x00800000
#define FLD_CMP_LT		0x01000000
#define FLD_CMP_REGEX		0x02000000
#define FLD_CMP_NUMBER		0x04000000
#define FLD_CMP_TIME		0x08000000
/*
 * #define FLD_CMP_STRING 0x10000000
 * We could define FLD_CMP_STRING here for completeness here,
 * but it's not needed - we can check operator compatibility with
 * field type by using FLD_CMP_REGEX, FLD_CMP_NUMBER and
 * FLD_CMP_TIME flags only.
 */

/*
 * When defining operators, always define longer one before
 * shorter one if one is a prefix of another!
 * (e.g. =~ comes before =)
*/
static const struct op_def _op_cmp[] = {
	{ "=~", FLD_CMP_REGEX, "Matching regular expression. [regex]" },
	{ "!~", FLD_CMP_REGEX|FLD_CMP_NOT, "Not matching regular expression. [regex]" },
	{ "=", FLD_CMP_EQUAL, "Equal to. [number, size, percent, string, string list, time]" },
	{ "!=", FLD_CMP_NOT|FLD_CMP_EQUAL, "Not equal to. [number, size, percent, string, string_list, time]" },
	{ ">=", FLD_CMP_NUMBER|FLD_CMP_TIME|FLD_CMP_GT|FLD_CMP_EQUAL, "Greater than or equal to. [number, size, percent, time]" },
	{ ">", FLD_CMP_NUMBER|FLD_CMP_TIME|FLD_CMP_GT, "Greater than. [number, size, percent, time]" },
	{ "<=", FLD_CMP_NUMBER|FLD_CMP_TIME|FLD_CMP_LT|FLD_CMP_EQUAL, "Less than or equal to. [number, size, percent, time]" },
	{ "<", FLD_CMP_NUMBER|FLD_CMP_TIME|FLD_CMP_LT, "Less than. [number, size, percent, time]" },
	{ "since", FLD_CMP_TIME|FLD_CMP_GT|FLD_CMP_EQUAL, "Since specified time (same as '>='). [time]" },
	{ "after", FLD_CMP_TIME|FLD_CMP_GT, "After specified time (same as '>'). [time]"},
	{ "until", FLD_CMP_TIME|FLD_CMP_LT|FLD_CMP_EQUAL, "Until specified time (same as '<='). [time]"},
	{ "before", FLD_CMP_TIME|FLD_CMP_LT, "Before specified time (same as '<'). [time]"},
	{ NULL, 0, NULL }
};

#define SEL_MASK		0x000000FF
#define SEL_ITEM		0x00000001
#define SEL_AND 		0x00000002
#define SEL_OR			0x00000004

#define SEL_MODIFIER_MASK	0x00000F00
#define SEL_MODIFIER_NOT	0x00000100

#define SEL_PRECEDENCE_MASK	0x0000F000
#define SEL_PRECEDENCE_PS	0x00001000
#define SEL_PRECEDENCE_PE	0x00002000

#define SEL_LIST_MASK		0x000F0000
#define SEL_LIST_LS		0x00010000
#define SEL_LIST_LE		0x00020000
#define SEL_LIST_SUBSET_LS	0x00040000
#define SEL_LIST_SUBSET_LE	0x00080000

static const struct op_def _op_log[] = {
	{ "&&", SEL_AND, "All fields must match" },
	{ ",", SEL_AND, "All fields must match" },
	{ "||", SEL_OR, "At least one field must match" },
	{ "#", SEL_OR, "At least one field must match" },
	{ "!", SEL_MODIFIER_NOT, "Logical negation" },
	{ "(", SEL_PRECEDENCE_PS, "Left parenthesis" },
	{ ")", SEL_PRECEDENCE_PE, "Right parenthesis" },
	{ "[", SEL_LIST_LS, "List start" },
	{ "]", SEL_LIST_LE, "List end"},
	{ "{", SEL_LIST_SUBSET_LS, "List subset start"},
	{ "}", SEL_LIST_SUBSET_LE, "List subset end"},
	{ NULL,  0, NULL},
};

struct selection_str_list {
	struct dm_str_list str_list;
	unsigned type;			/* either SEL_AND or SEL_OR */
};

struct field_selection_value {
	union value_u {
		const char *s;
		uint64_t i;
		time_t t;
		double d;
		struct dm_regex *r;
		struct selection_str_list *l;
	} v;
	struct field_selection_value *next;
};

struct field_selection {
	struct field_properties *fp;
	uint32_t flags;
	struct field_selection_value *value;
};

struct selection_node {
	struct dm_list list;
	uint32_t type;
	union selection_u {
		struct field_selection *item;
		struct dm_list set;
	} selection;
};

struct reserved_value_wrapper {
	const char *matched_name;
	const struct dm_report_reserved_value *reserved;
	const void *value;
};

/*
 * Report data field
 */
struct dm_report_field {
	struct dm_list list;
	struct field_properties *props;

	const char *report_string;	/* Formatted ready for display */
	const void *sort_value;		/* Raw value for sorting */
};

struct row {
	struct dm_list list;
	struct dm_report *rh;
	struct dm_list fields;			  /* Fields in display order */
	struct dm_report_field *(*sort_fields)[]; /* Fields in sort order */
	int selected;
	struct dm_report_field *field_sel_status;
};

/*
 * Implicit report types and fields.
 */
#define SPECIAL_REPORT_TYPE 0x80000000
#define SPECIAL_FIELD_SELECTED_ID "selected"
#define SPECIAL_FIELD_HELP_ID "help"
#define SPECIAL_FIELD_HELP_ALT_ID "?"

static void *_null_returning_fn(void *obj __attribute__((unused)))
{
	return NULL;
}

static int _no_report_fn(struct dm_report *rh __attribute__((unused)),
			 struct dm_pool *mem __attribute__((unused)),
			 struct dm_report_field *field __attribute__((unused)),
			 const void *data __attribute__((unused)),
			 void *private __attribute__((unused)))
{
	return 1;
}

static int _selected_disp(struct dm_report *rh,
			  struct dm_pool *mem __attribute__((unused)),
			  struct dm_report_field *field,
			  const void *data,
			  void *private __attribute__((unused)))
{
	const struct row *row = (const struct row *)data;
	return dm_report_field_int(rh, field, &row->selected);
}

static const struct dm_report_object_type _implicit_special_report_types[] = {
	{ SPECIAL_REPORT_TYPE, "Special", "special_", _null_returning_fn },
	{ 0, "", "", NULL }
};

static const struct dm_report_field_type _implicit_special_report_fields[] = {
	{ SPECIAL_REPORT_TYPE, DM_REPORT_FIELD_TYPE_NUMBER | FLD_CMP_UNCOMPARABLE , 0, 8, SPECIAL_FIELD_HELP_ID, "Help", _no_report_fn, "Show help." },
	{ SPECIAL_REPORT_TYPE, DM_REPORT_FIELD_TYPE_NUMBER | FLD_CMP_UNCOMPARABLE , 0, 8, SPECIAL_FIELD_HELP_ALT_ID, "Help", _no_report_fn, "Show help." },
	{ 0, 0, 0, 0, "", "", 0, 0}
};

static const struct dm_report_field_type _implicit_special_report_fields_with_selection[] = {
	{ SPECIAL_REPORT_TYPE, DM_REPORT_FIELD_TYPE_NUMBER, 0, 8, SPECIAL_FIELD_SELECTED_ID, "Selected", _selected_disp, "Set if item passes selection criteria." },
	{ SPECIAL_REPORT_TYPE, DM_REPORT_FIELD_TYPE_NUMBER | FLD_CMP_UNCOMPARABLE , 0, 8, SPECIAL_FIELD_HELP_ID, "Help", _no_report_fn, "Show help." },
	{ SPECIAL_REPORT_TYPE, DM_REPORT_FIELD_TYPE_NUMBER | FLD_CMP_UNCOMPARABLE , 0, 8, SPECIAL_FIELD_HELP_ALT_ID, "Help", _no_report_fn, "Show help." },
	{ 0, 0, 0, 0, "", "", 0, 0}
};

static const struct dm_report_object_type *_implicit_report_types = _implicit_special_report_types;
static const struct dm_report_field_type *_implicit_report_fields = _implicit_special_report_fields;

static const struct dm_report_object_type *_find_type(struct dm_report *rh,
						      uint32_t report_type)
{
	const struct dm_report_object_type *t;

	for (t = _implicit_report_types; t->data_fn; t++)
		if (t->id == report_type)
			return t;

	for (t = rh->types; t->data_fn; t++)
		if (t->id == report_type)
			return t;

	return NULL;
}

/*
 * Data-munging functions to prepare each data type for display and sorting
 */

int dm_report_field_string(struct dm_report *rh,
			   struct dm_report_field *field, const char *const *data)
{
	char *repstr;

	if (!(repstr = dm_pool_strdup(rh->mem, *data))) {
		log_error("dm_report_field_string: dm_pool_strdup failed");
		return 0;
	}

	field->report_string = repstr;
	field->sort_value = (const void *) field->report_string;

	return 1;
}

int dm_report_field_percent(struct dm_report *rh,
			    struct dm_report_field *field,
			    const dm_percent_t *data)
{
	char *repstr;
	uint64_t *sortval;

	if (!(sortval = dm_pool_alloc(rh->mem, sizeof(uint64_t)))) {
		log_error("dm_report_field_percent: dm_pool_alloc failed for sort_value.");
		return 0;
	}

	*sortval = (uint64_t)(*data);

	if (*data == DM_PERCENT_INVALID) {
		dm_report_field_set_value(field, "", sortval);
		return 1;
	}

	if (!(repstr = dm_pool_alloc(rh->mem, 8))) {
		dm_pool_free(rh->mem, sortval);
		log_error("dm_report_field_percent: dm_pool_alloc failed for percent report string.");
		return 0;
	}

	if (dm_snprintf(repstr, 7, "%.2f", dm_percent_to_round_float(*data, 2)) < 0) {
		dm_pool_free(rh->mem, sortval);
		log_error("dm_report_field_percent: percentage too large.");
		return 0;
	}

	dm_report_field_set_value(field, repstr, sortval);
	return 1;
}

struct pos_len {
	unsigned pos;
	size_t len;
};

struct str_pos_len {
	const char *str;
	struct pos_len item;
};

struct str_list_sort_value {
	const char *value;
	struct pos_len *items;
};

static int _str_sort_cmp(const void *a, const void *b)
{
	return strcmp(((const struct str_pos_len *) a)->str, ((const struct str_pos_len *) b)->str);
}

#define FIELD_STRING_LIST_DEFAULT_DELIMITER ","

static int _report_field_string_list(struct dm_report *rh,
				     struct dm_report_field *field,
				     const struct dm_list *data,
				     const char *delimiter,
				     int sort_repstr)
{
	static const char _error_msg_prefix[] = "_report_field_string_list: ";
	unsigned int list_size, i, pos;
	struct str_pos_len *arr = NULL;
	struct dm_str_list *sl;
	size_t delimiter_len, repstr_str_len, repstr_size;
	char *repstr = NULL;
	struct pos_len *repstr_extra;
	struct str_list_sort_value *sortval = NULL;
	int r = 0;

	/*
	 * The 'field->report_string' has 2 parts:
	 *
	 *    - string representing the whole string list
	 *      (terminated by '\0' at its end as usual)
	 *
	 *    - extra info beyond the end of the string representing
	 *      position and length of each list item within the
	 *      field->report_string (array of 'struct pos_len')
	 *
	 * We can use the extra info to unambiguously identify list items,
	 * the delimiter is not enough here as it's not assured it won't appear
	 * in list item itself. We will make use of this extra info in case
	 * we need to apply further formatting to the list in dm_report_output
	 * where the pure field->report_string is not enough for printout.
	 *
	 *
	 * The 'field->sort_value' contains a value of type 'struct
	 * str_list_sort_value' ('sortval'). This one has a pointer to the
	 * 'field->report_string' string ('sortval->value') and info
	 * about position and length of each list item within the string
	 * (array of 'struct pos_len').
	 *
	 *
	 * The 'field->report_string' is either in sorted or unsorted form,
	 * depending on 'sort_repstr' arg.
	 *
	 * The 'field->sort_value.items' is always in sorted form because
	 * we need that for effective sorting and selection.
	 *
	 * If 'field->report_string' is sorted, then field->report_string
	 * and field->sort_value.items share the same array of
	 * 'struct pos_len' (because they're both sorted the same way),
	 * otherwise, each one has its own array.
	 *
	 * The very first item in the array of 'struct pos_len' is always
	 * a pair denoting '[list_size,strlen(field->report_string)]'. The
	 * rest of items denote start and length of each item in the list.
         *
	 *
	 * For example, if we have a list with "abc", "xy", "defgh"
	 * as input and delimiter is ",", we end up with either:
	 *
	 *  A) if we don't want the report string sorted ('sort_repstr == 0'):
	 *
	 *    - field->report_string = repstr
	 *
	 *       repstr      repstr_extra
	 *         |             |
	 *         V             V
	 *         abc,xy,defgh\0{[3,12],[0,3],[4,2],[7,5]}
	 *         |____________||________________________|
	 *             string     array of struct pos_len
	 *                        |____||________________|
	 *                        #items      items
	 *
	 *    - field->sort_value = sortval
	 *
	 *       sortval->value = repstr
	 *       sortval->items = {[3,12],[0,3],[7,5],[4,2]}
	 *                         (that is 'abc,defgh,xy')
	 *
	 *
	 *  B) if we want the report string sorted ('sort_repstr == 1'):
	 *
	 *    - field->report_string = repstr
	 *
	 *       repstr     repstr_extra
	 *         |             |
	 *         V             V
	 *         abc,defgh,xy\0{[3,12],[0,3],[4,5],[10,2]}
	 *         |____________||________________________|
	 *             string     array of struct pos_len
	 *                        |____||________________|
	 *                        #items      items
	 *
	 *     - field->sort_value = sortval
	 *
	 *       sortval->value = repstr
	 *       sortval->items = repstr_extra
	 *                       (that is 'abc,defgh,xy')
	 */

	if (!delimiter)
		delimiter = FIELD_STRING_LIST_DEFAULT_DELIMITER;
	delimiter_len = strlen(delimiter);
	list_size = dm_list_size(data);

	if (!(sortval = dm_pool_alloc(rh->mem, sizeof(struct str_list_sort_value)))) {
		log_error("%s failed to allocate sort value structure", _error_msg_prefix);
		goto out;
	}

	/* zero items */
	if (list_size == 0) {
		field->report_string = sortval->value = "";
		sortval->items = NULL;
		field->sort_value = sortval;
		return 1;
	}

	/* one item */
	if (list_size == 1) {
		sl = (struct dm_str_list *) dm_list_first(data);

		repstr_str_len = strlen(sl->str);
		repstr_size = repstr_str_len + 1 + (2 * sizeof(struct pos_len));

		if (!(repstr = dm_pool_alloc(rh->mem, repstr_size))) {
			log_error("%s failed to allocate report string structure", _error_msg_prefix);
			goto out;
		}
		repstr_extra = (struct pos_len *) (repstr + repstr_str_len + 1);

		memcpy(repstr, sl->str, repstr_str_len + 1);
		memcpy(repstr_extra, &((struct pos_len) {.pos = 1, .len = repstr_str_len}), sizeof(struct pos_len));
		memcpy(repstr_extra + 1, &((struct pos_len) {.pos = 0, .len = repstr_str_len}), sizeof(struct pos_len));

		sortval->value = field->report_string = repstr;
		sortval->items = repstr_extra;
		field->sort_value = sortval;
		return 1;
	}

	/* more than one item - allocate temporary array for string list items for further processing */
	if (!(arr = dm_malloc(list_size * sizeof(struct str_pos_len)))) {
		log_error("%s failed to allocate temporary array for processing", _error_msg_prefix);
		goto out;
	}