usr/src/lib/libbe/common/be_list.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
 */

/*
 * Copyright 2013 Nexenta Systems, Inc. All rights reserved.
 * Copyright 2015 Toomas Soome <tsoome@me.com>
 * Copyright 2015 Gary Mills
 * Copyright (c) 2016 Martin Matuska. All rights reserved.
 * Copyright 2018 OmniOS Community Edition (OmniOSce) Association.
 */

#include <assert.h>
#include <libintl.h>
#include <libnvpair.h>
#include <libzfs.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <errno.h>

#include <libbe.h>
#include <libbe_priv.h>

/*
 * Callback data used for zfs_iter calls.
 */
typedef struct list_callback_data {
	char *zpool_name;
	char *be_name;
	be_node_list_t *be_nodes_head;
	be_node_list_t *be_nodes;
	be_dataset_list_t **be_datasets_tail;
	be_snapshot_list_t **be_snapshots_tail;
	char current_be[MAXPATHLEN];
	struct be_defaults be_defaults;
	uint64_t flags;
} list_callback_data_t;

/*
 * Private function prototypes
 */
static int be_add_children_callback(zfs_handle_t *zhp, void *data);
static int be_get_list_callback(zpool_handle_t *, void *);
static int be_get_node_data(zfs_handle_t *, be_node_list_t *, char *,
    const char *, char *, char *);
static int be_get_zone_node_data(be_node_list_t *, char *);
static int be_get_ds_data(zfs_handle_t *, char *, be_dataset_list_t *,
    be_node_list_t *);
static int be_get_ss_data(zfs_handle_t *, char *, be_snapshot_list_t *,
    be_node_list_t *);
static int be_sort_list(be_node_list_t **,
    int (*)(const void *, const void *));
static int be_qsort_compare_BEs_name(const void *, const void *);
static int be_qsort_compare_BEs_name_rev(const void *, const void *);
static int be_qsort_compare_BEs_date(const void *, const void *);
static int be_qsort_compare_BEs_date_rev(const void *, const void *);
static int be_qsort_compare_BEs_space(const void *, const void *);
static int be_qsort_compare_BEs_space_rev(const void *, const void *);
static int be_qsort_compare_snapshots(const void *x, const void *y);
static int be_qsort_compare_datasets(const void *x, const void *y);
static void *be_list_alloc(int *, size_t);
static int be_allocate_callback_nodes(list_callback_data_t *);

/*
 * Private data.
 */
static char be_container_ds[MAXPATHLEN];
static boolean_t zone_be = B_FALSE;

/* ******************************************************************** */
/*			Public Functions				*/
/* ******************************************************************** */

/*
 * Function:	be_list
 * Description:	Calls _be_list which finds all the BEs on the system and
 *		returns the datasets and snapshots belonging to each BE.
 *		Also data, such as dataset and snapshot properties,
 *		for each BE and their snapshots and datasets is
 *		returned. The data returned is as described in the
 *		be_dataset_list_t, be_snapshot_list_t and be_node_list_t
 *		structures.
 * Parameters:
 *		be_name - The name of the BE to look up.
 *			  If NULL a list of all BEs will be returned.
 *		be_nodes - A reference pointer to the list of BEs. The list
 *			   structure will be allocated by _be_list and must
 *			   be freed by a call to be_free_list. If there are no
 *			   BEs found on the system this reference will be
 *			   set to NULL.
 * Return:
 *		BE_SUCCESS - Success
 *		be_errno_t - Failure
 * Scope:
 *		Public
 */
int
be_list(char *be_name, be_node_list_t **be_nodes, uint64_t flags)
{
	int	ret = BE_SUCCESS;

	/* Initialize libzfs handle */
	if (!be_zfs_init())
		return (BE_ERR_INIT);

	/* Validate be_name if its not NULL */
	if (be_name != NULL) {
		if (!be_valid_be_name(be_name)) {
			be_print_err(gettext("be_list: "
			    "invalid BE name %s\n"), be_name);
			return (BE_ERR_INVAL);
		}
	}

	ret = _be_list(be_name, be_nodes, flags);

	be_zfs_fini();

	return (ret);
}

/*
 * Function:	be_sort
 * Description:	Sort BE node list
 * Parameters:
 *		pointer to address of list head
 *		sort order type
 * Return:
 *              BE_SUCCESS - Success
 *              be_errno_t - Failure
 * Side effect:
 *		node list sorted by name
 * Scope:
 *		Public
 */
int
be_sort(be_node_list_t **be_nodes, int order)
{
	int (*compar)(const void *, const void *) = be_qsort_compare_BEs_date;

	if (be_nodes == NULL)
		return (BE_ERR_INVAL);

	switch (order) {
	case BE_SORT_UNSPECIFIED:
	case BE_SORT_DATE:
		compar = be_qsort_compare_BEs_date;
		break;
	case BE_SORT_DATE_REV:
		compar = be_qsort_compare_BEs_date_rev;
		break;
	case BE_SORT_NAME:
		compar = be_qsort_compare_BEs_name;
		break;
	case BE_SORT_NAME_REV:
		compar = be_qsort_compare_BEs_name_rev;
		break;
	case BE_SORT_SPACE:
		compar = be_qsort_compare_BEs_space;
		break;
	case BE_SORT_SPACE_REV:
		compar = be_qsort_compare_BEs_space_rev;
		break;
	default:
		be_print_err(gettext("be_sort: invalid sort order %d\n"),
		    order);
		return (BE_ERR_INVAL);
	}

	return (be_sort_list(be_nodes, compar));
}

/* ******************************************************************** */
/*			Semi-Private Functions				*/
/* ******************************************************************** */

/*
 * Function:	_be_list
 * Description:	This does the actual work described in be_list.
 * Parameters:
 *		be_name - The name of the BE to look up.
 *			  If NULL a list of all BEs will be returned.
 *		be_nodes - A reference pointer to the list of BEs. The list
 *			   structure will be allocated here and must
 *			   be freed by a call to be_free_list. If there are no
 *			   BEs found on the system this reference will be
 *			   set to NULL.
 * Return:
 *		BE_SUCCESS - Success
 *		be_errno_t - Failure
 * Scope:
 *		Semi-private (library wide use only)
 */
int
_be_list(char *be_name, be_node_list_t **be_nodes, uint64_t flags)
{
	list_callback_data_t cb = { 0 };
	be_transaction_data_t bt = { 0 };
	int ret = BE_SUCCESS;
	int sret;
	zpool_handle_t *zphp;
	char *rpool = NULL;

	if (be_nodes == NULL)
		return (BE_ERR_INVAL);

	be_get_defaults(&cb.be_defaults);
	cb.flags = flags;

	if (be_find_current_be(&bt) != BE_SUCCESS) {
		/*
		 * We were unable to find a currently booted BE which
		 * probably means that we're not booted in a BE envoronment.
		 * None of the BE's will be marked as the active BE.
		 */
		(void) strcpy(cb.current_be, "-");
	} else {
		(void) strncpy(cb.current_be, bt.obe_name,
		    sizeof (cb.current_be));
		rpool = bt.obe_zpool;
	}

	/*
	 * If be_name is NULL we'll look for all BE's on the system.
	 * If not then we will only return data for the specified BE.
	 */
	if (be_name != NULL)
		cb.be_name = strdup(be_name);

	if (cb.be_defaults.be_deflt_rpool_container && rpool != NULL) {
		if ((zphp = zpool_open(g_zfs, rpool)) == NULL) {
			be_print_err(gettext("be_list: failed to "
			    "open rpool (%s): %s\n"), rpool,
			    libzfs_error_description(g_zfs));
			free(cb.be_name);
			return (zfs_err_to_be_err(g_zfs));
		}

		ret = be_get_list_callback(zphp, &cb);
	} else {
		if ((zpool_iter(g_zfs, be_get_list_callback, &cb)) != 0) {
			if (cb.be_nodes_head != NULL) {
				be_free_list(cb.be_nodes_head);
				cb.be_nodes_head = NULL;
				cb.be_nodes = NULL;
			}
			ret = BE_ERR_BE_NOENT;
		}
	}

	if (cb.be_nodes_head == NULL) {
		if (be_name != NULL)
			be_print_err(gettext("be_list: BE (%s) does not "
			    "exist\n"), be_name);
		else
			be_print_err(gettext("be_list: No BE's found\n"));
		ret = BE_ERR_BE_NOENT;
	}

	*be_nodes = cb.be_nodes_head;

	free(cb.be_name);

	sret = be_sort(be_nodes, BE_SORT_DATE);

	return ((ret == BE_SUCCESS) ? sret : ret);
}

/*
 * Function:	be_free_list
 * Description:	Frees up all the data allocated for the list of BEs,
 *		datasets and snapshots returned by be_list.
 * Parameters:
 *		be_node - be_nodes_t structure returned from call to be_list.
 * Returns:
 *		none
 * Scope:
 *		Semi-private (library wide use only)
 */
void
be_free_list(be_node_list_t *be_nodes)
{
	be_node_list_t *temp_node = NULL;
	be_node_list_t *list = be_nodes;

	while (list != NULL) {
		be_dataset_list_t *datasets = list->be_node_datasets;
		be_snapshot_list_t *snapshots = list->be_node_snapshots;

		while (datasets != NULL) {
			be_dataset_list_t *temp_ds = datasets;
			datasets = datasets->be_next_dataset;
			free(temp_ds->be_dataset_name);
			free(temp_ds->be_ds_mntpt);
			free(temp_ds->be_ds_plcy_type);
			free(temp_ds);
		}

		while (snapshots != NULL) {
			be_snapshot_list_t *temp_ss = snapshots;
			snapshots = snapshots->be_next_snapshot;
			free(temp_ss->be_snapshot_name);
			free(temp_ss->be_snapshot_type);
			free(temp_ss);
		}

		temp_node = list;
		list = list->be_next_node;
		free(temp_node->be_node_name);
		free(temp_node->be_root_ds);
		free(temp_node->be_rpool);
		free(temp_node->be_mntpt);
		free(temp_node->be_policy_type);
		free(temp_node->be_uuid_str);
		free(temp_node);
	}
}

/*
 * Function:	be_get_zone_be_list
 * Description:	Finds all the BEs for this zone on the system.
 * Parameters:
 *		zone_be_name - The name of the BE to look up.
 *              zone_be_container_ds - The dataset for the zone.
 *		zbe_nodes - A reference pointer to the list of BEs. The list
 *			   structure will be allocated here and must
 *			   be freed by a call to be_free_list. If there are no
 *			   BEs found on the system this reference will be
 *			   set to NULL.
 * Return:
 *		BE_SUCCESS - Success
 *		be_errno_t - Failure
 * Scope:
 *		Semi-private (library wide use only)
 */
int
/* LINTED */
be_get_zone_be_list(char *zone_be_name, char *zone_be_container_ds,
    be_node_list_t **zbe_nodes)
{
	zfs_handle_t *zhp = NULL;
	list_callback_data_t cb = { 0 };
	int ret = BE_SUCCESS;

	if (zbe_nodes == NULL)
		return (BE_ERR_INVAL);

	if (!zfs_dataset_exists(g_zfs, zone_be_container_ds,
	    ZFS_TYPE_FILESYSTEM)) {
		return (BE_ERR_BE_NOENT);
	}

	zone_be = B_TRUE;

	if ((zhp = zfs_open(g_zfs, zone_be_container_ds,
	    ZFS_TYPE_FILESYSTEM)) == NULL) {
		be_print_err(gettext("be_get_zone_be_list: failed to open "
		    "the zone BE dataset %s: %s\n"), zone_be_container_ds,
		    libzfs_error_description(g_zfs));
		ret = zfs_err_to_be_err(g_zfs);
		goto cleanup;
	}

	(void) strcpy(be_container_ds, zone_be_container_ds);

	if ((ret = be_allocate_callback_nodes(&cb)) != BE_SUCCESS) {
		ZFS_CLOSE(zhp);
		goto cleanup;
	}
	if (ret == 0) {
		be_get_defaults(&cb.be_defaults);
		ret = zfs_iter_filesystems(zhp, be_add_children_callback, &cb);
	}
	ZFS_CLOSE(zhp);

	*zbe_nodes = cb.be_nodes_head;

cleanup:
	zone_be = B_FALSE;

	return (ret);
}

/* ******************************************************************** */
/*			Private Functions				*/
/* ******************************************************************** */

/*
 * Function:	be_get_list_callback
 * Description:	Callback function used by zfs_iter to look through all
 *		the pools on the system looking for BEs. If a BE name was
 *		specified only that BE's information will be collected and
 *		returned.
 * Parameters:
 *		zlp - handle to the first zfs dataset. (provided by the
 *		      zfs_iter_* call)
 *		data - pointer to the callback data and where we'll pass
 *		       the BE information back.
 * Returns:
 *		0 - Success
 *		be_errno_t - Failure
 * Scope:
 *		Private
 */
static int
be_get_list_callback(zpool_handle_t *zlp, void *data)
{
	list_callback_data_t *cb = (list_callback_data_t *)data;
	char be_ds[MAXPATHLEN];
	char *open_ds = NULL;
	char *rpool = NULL;
	zfs_handle_t *zhp = NULL;
	int ret = 0;

	cb->zpool_name = rpool =  (char *)zpool_get_name(zlp);

	/*
	 * Generate string for the BE container dataset
	 */
	be_make_container_ds(rpool, be_container_ds,
	    sizeof (be_container_ds));

	/*
	 * If a BE name was specified we use it's root dataset in place of
	 * the container dataset. This is because we only want to collect
	 * the information for the specified BE.
	 */
	if (cb->be_name != NULL) {
		if (!be_valid_be_name(cb->be_name))
			return (BE_ERR_INVAL);
		/*
		 * Generate string for the BE root dataset
		 */
		be_make_root_ds(rpool, cb->be_name, be_ds, sizeof (be_ds));
		open_ds = be_ds;
	} else {
		open_ds = be_container_ds;
	}

	/*
	 * Check if the dataset exists
	 */
	if (!zfs_dataset_exists(g_zfs, open_ds,
	    ZFS_TYPE_FILESYSTEM)) {
		/*
		 * The specified dataset does not exist in this pool or
		 * there are no valid BE's in this pool. Try the next zpool.
		 */
		zpool_close(zlp);
		return (0);
	}

	if ((zhp = zfs_open(g_zfs, open_ds, ZFS_TYPE_FILESYSTEM)) == NULL) {
		be_print_err(gettext("be_get_list_callback: failed to open "
		    "the BE dataset %s: %s\n"), open_ds,
		    libzfs_error_description(g_zfs));
		ret = zfs_err_to_be_err(g_zfs);
		zpool_close(zlp);
		return (ret);
	}

	/*
	 * If a BE name was specified we iterate through the datasets
	 * and snapshots for this BE only. Otherwise we will iterate
	 * through the next level of datasets to find all the BE's
	 * within the pool
	 */
	if (cb->be_name != NULL) {
		if ((ret = be_allocate_callback_nodes(cb)) != BE_SUCCESS) {
			ZFS_CLOSE(zhp);
			zpool_close(zlp);
			return (ret);
		}

		if ((ret = be_get_node_data(zhp, cb->be_nodes, cb->be_name,
		    rpool, cb->current_be, be_ds)) != BE_SUCCESS) {
			ZFS_CLOSE(zhp);
			zpool_close(zlp);
			return (ret);
		}
		if (cb->flags & BE_LIST_SNAPSHOTS)
			ret = zfs_iter_snapshots(zhp, B_FALSE,
			    be_add_children_callback, cb);
	}

	if (ret == 0)
		ret = zfs_iter_filesystems(zhp, be_add_children_callback, cb);
	ZFS_CLOSE(zhp);

	zpool_close(zlp);
	return (ret);
}

/*
 * Function:	be_allocate_callback_nodes
 * Description:	Function to create the be_nodes list in the callback data
 *		structure, and set up tail pointers to the dataset and
 *		snapshot lists.
 * Parameters:
 *		data - pointer to the callback data.
 * Returns:
 *		0 - Success
 *		be_errno_t - Failure
 * Scope:
 *		Private
 */
static int
be_allocate_callback_nodes(list_callback_data_t *cb)
{
	int ret = BE_SUCCESS;

	if (cb->be_nodes_head != NULL)
		return (BE_SUCCESS);

	if ((cb->be_nodes_head = be_list_alloc(&ret, sizeof (be_node_list_t)))
	    == NULL)
		return (ret);

	cb->be_nodes = cb->be_nodes_head;
	cb->be_snapshots_tail = &cb->be_nodes->be_node_snapshots;
	cb->be_datasets_tail = &cb->be_nodes->be_node_datasets;

	return (BE_SUCCESS);
}

/*
 * Function:	be_add_children_callback
 * Description:	Callback function used by zfs_iter to look through all
 *		the datasets and snapshots for each BE and add them to
 *		the lists of information to be passed back.
 * Parameters:
 *		zhp - handle to the first zfs dataset. (provided by the
 *		      zfs_iter_* call)
 *		data - pointer to the callback data and where we'll pass
 *		       the BE information back.
 * Returns:
 *		0 - Success
 *		be_errno_t - Failure
 * Scope:
 *		Private
 */
static int
be_add_children_callback(zfs_handle_t *zhp, void *data)
{
	list_callback_data_t	*cb = (list_callback_data_t *)data;
	char			*str = NULL, *ds_path = NULL;
	int			ret = 0;

	ds_path = str = strdup(zfs_get_name(zhp));

	/*
	 * get past the end of the container dataset plus the trailing "/"
	 */
	str = str + (strlen(be_container_ds) + 1);
	if (cb->be_defaults.be_deflt_rpool_container) {
		/* just skip if invalid */
		if (!be_valid_be_name(str))
			return (BE_SUCCESS);
	}

	if (cb->be_nodes_head == NULL &&
	    (ret = be_allocate_callback_nodes(cb)) != BE_SUCCESS) {
		ZFS_CLOSE(zhp);
		return (ret);
	}

	if (zfs_get_type(zhp) == ZFS_TYPE_SNAPSHOT && !zone_be) {
		be_snapshot_list_t *snapshot;

		if ((snapshot = be_list_alloc(&ret,
		    sizeof (be_snapshot_list_t))) == NULL ||
		    ret != BE_SUCCESS) {
			ZFS_CLOSE(zhp);
			return (ret);
		}

		if ((ret = be_get_ss_data(zhp, str, snapshot,
		    cb->be_nodes)) != BE_SUCCESS) {
			free(snapshot);
			ZFS_CLOSE(zhp);
			return (ret);
		}

		snapshot->be_next_snapshot = NULL;
		*cb->be_snapshots_tail = snapshot;
		cb->be_snapshots_tail = &snapshot->be_next_snapshot;
	} else if (strchr(str, '/') == NULL) {
		if (cb->be_nodes->be_node_name != NULL) {
			if ((cb->be_nodes->be_next_node =
			    be_list_alloc(&ret, sizeof (be_node_list_t))) ==
			    NULL || ret != BE_SUCCESS) {
				ZFS_CLOSE(zhp);
				return (ret);
			}
			cb->be_nodes = cb->be_nodes->be_next_node;
			cb->be_nodes->be_next_node = NULL;
		}

		/*
		 * If this is a zone root dataset then we only need
		 * the name of the zone BE at this point. We grab that
		 * and return.
		 */
		if (zone_be) {
			ret = be_get_zone_node_data(cb->be_nodes, str);
			ZFS_CLOSE(zhp);
			return (ret);
		}

		if ((ret = be_get_node_data(zhp, cb->be_nodes, str,
		    cb->zpool_name, cb->current_be, ds_path)) != BE_SUCCESS) {
			ZFS_CLOSE(zhp);
			return (ret);
		}
	} else if (strchr(str, '/') != NULL && !zone_be) {
		be_dataset_list_t *dataset;

		if ((dataset = be_list_alloc(&ret,
		    sizeof (be_dataset_list_t))) == NULL ||
		    ret != BE_SUCCESS) {
			ZFS_CLOSE(zhp);
			return (ret);
		}

		if ((ret = be_get_ds_data(zhp, str,
		    dataset, cb->be_nodes)) != BE_SUCCESS) {
			free(dataset);
			ZFS_CLOSE(zhp);
			return (ret);
		}

		dataset->be_next_dataset = NULL;
		*cb->be_datasets_tail = dataset;
		cb->be_datasets_tail = &dataset->be_next_dataset;
	}
	if (cb->flags & BE_LIST_SNAPSHOTS)
		ret = zfs_iter_children(zhp, be_add_children_callback, cb);
	else
		ret = zfs_iter_filesystems(zhp, be_add_children_callback, cb);
	if (ret != 0) {
		be_print_err(gettext("be_add_children_callback: "
		    "encountered error: %s\n"),
		    libzfs_error_description(g_zfs));
		ret = zfs_err_to_be_err(g_zfs);
	}
	ZFS_CLOSE(zhp);
	return (ret);
}

/*
 * Function:	be_sort_list
 * Description:	Sort BE node list
 * Parameters:
 *		pointer to address of list head
 *		compare function
 * Return:
 *              BE_SUCCESS - Success
 *              be_errno_t - Failure
 * Side effect:
 *		node list sorted by name
 * Scope:
 *		Private
 */
static int
be_sort_list(be_node_list_t **pstart, int (*compar)(const void *, const void *))
{
	int ret = BE_SUCCESS;
	size_t ibe, nbe;
	be_node_list_t *p = NULL;
	be_node_list_t **ptrlist = NULL;
	be_node_list_t **ptrtmp;

	if (pstart == NULL) /* Nothing to sort */
		return (BE_SUCCESS);
	/* build array of linked list BE struct pointers */
	for (p = *pstart, nbe = 0; p != NULL; nbe++, p = p->be_next_node) {
		ptrtmp = realloc(ptrlist,
		    sizeof (be_node_list_t *) * (nbe + 2));
		if (ptrtmp == NULL) { /* out of memory */
			be_print_err(gettext("be_sort_list: memory "
			    "allocation failed\n"));
			ret = BE_ERR_NOMEM;
			goto free;
		}
		ptrlist = ptrtmp;
		ptrlist[nbe] = p;
	}
	if (nbe == 0) /* Nothing to sort */
		return (BE_SUCCESS);
	/* in-place list quicksort using qsort(3C) */
	if (nbe > 1)	/* no sort if less than 2 BEs */
		qsort(ptrlist, nbe, sizeof (be_node_list_t *), compar);

	ptrlist[nbe] = NULL; /* add linked list terminator */
	*pstart = ptrlist[0]; /* set new linked list header */
	/* for each BE in list */
	for (ibe = 0; ibe < nbe; ibe++) {
		size_t k, ns;	/* subordinate index, count */

		/* rewrite list pointer chain, including terminator */
		ptrlist[ibe]->be_next_node = ptrlist[ibe + 1];
		/* sort subordinate snapshots */
		if (ptrlist[ibe]->be_node_num_snapshots > 1) {
			const size_t nmax = ptrlist[ibe]->be_node_num_snapshots;
			be_snapshot_list_t ** const slist =
			    malloc(sizeof (be_snapshot_list_t *) * (nmax + 1));
			be_snapshot_list_t *p;

			if (slist == NULL) {
				ret = BE_ERR_NOMEM;
				continue;
			}
			/* build array of linked list snapshot struct ptrs */
			for (ns = 0, p = ptrlist[ibe]->be_node_snapshots;
			    ns < nmax && p != NULL;
			    ns++, p = p->be_next_snapshot) {
				slist[ns] = p;
			}
			if (ns < 2)
				goto end_snapshot;
			slist[ns] = NULL; /* add terminator */
			/* in-place list quicksort using qsort(3C) */
			qsort(slist, ns, sizeof (be_snapshot_list_t *),
			    be_qsort_compare_snapshots);
			/* rewrite list pointer chain, including terminator */
			ptrlist[ibe]->be_node_snapshots = slist[0];
			for (k = 0; k < ns; k++)
				slist[k]->be_next_snapshot = slist[k + 1];
end_snapshot:
			free(slist);
		}
		/* sort subordinate datasets */
		if (ptrlist[ibe]->be_node_num_datasets > 1) {
			const size_t nmax = ptrlist[ibe]->be_node_num_datasets;
			be_dataset_list_t ** const slist =
			    malloc(sizeof (be_dataset_list_t *) * (nmax + 1));
			be_dataset_list_t *p;

			if (slist == NULL) {
				ret = BE_ERR_NOMEM;
				continue;
			}
			/* build array of linked list dataset struct ptrs */
			for (ns = 0, p = ptrlist[ibe]->be_node_datasets;
			    ns < nmax && p != NULL;
			    ns++, p = p->be_next_dataset) {
				slist[ns] = p;
			}
			if (ns < 2) /* subordinate datasets < 2 - no sort */
				goto end_dataset;
			slist[ns] = NULL; /* add terminator */
			/* in-place list quicksort using qsort(3C) */
			qsort(slist, ns, sizeof (be_dataset_list_t *),
			    be_qsort_compare_datasets);
			/* rewrite list pointer chain, including terminator */
			ptrlist[ibe]->be_node_datasets = slist[0];
			for (k = 0; k < ns; k++)
				slist[k]->be_next_dataset = slist[k + 1];
end_dataset:
			free(slist);
		}
	}
free:
	free(ptrlist);
	return (ret);
}

/*
 * Function:	be_qsort_compare_BEs_date
 * Description:	compare BE creation times for qsort(3C)
 *		will sort BE list from oldest to most recent
 * Parameters:
 *		x,y - BEs with names to compare
 * Returns:
 *		positive if x>y, negative if y>x, 0 if equal
 * Scope:
 *		Private
 */
static int
be_qsort_compare_BEs_date(const void *x, const void *y)
{
	be_node_list_t *p = *(be_node_list_t **)x;
	be_node_list_t *q = *(be_node_list_t **)y;

	assert(p != NULL);
	assert(q != NULL);

	if (p->be_node_creation > q->be_node_creation)
		return (1);
	if (p->be_node_creation < q->be_node_creation)
		return (-1);
	return (0);
}

/*
 * Function:	be_qsort_compare_BEs_date_rev
 * Description:	compare BE creation times for qsort(3C)
 *		will sort BE list from recent to oldest
 * Parameters:
 *		x,y - BEs with names to compare
 * Returns:
 *		positive if y>x, negative if x>y, 0 if equal
 * Scope:
 *		Private
 */
static int
be_qsort_compare_BEs_date_rev(const void *x, const void *y)
{
	return (be_qsort_compare_BEs_date(y, x));
}

/*
 * Function:	be_qsort_compare_BEs_name
 * Description:	lexical compare of BE names for qsort(3C)
 * Parameters:
 *		x,y - BEs with names to compare
 * Returns:
 *		positive if x>y, negative if y>x, 0 if equal
 * Scope:
 *		Private
 */
static int
be_qsort_compare_BEs_name(const void *x, const void *y)
{
	be_node_list_t *p = *(be_node_list_t **)x;
	be_node_list_t *q = *(be_node_list_t **)y;

	assert(p != NULL);
	assert(p->be_node_name != NULL);
	assert(q != NULL);
	assert(q->be_node_name != NULL);

	return (strcmp(p->be_node_name, q->be_node_name));
}

/*
 * Function:	be_qsort_compare_BEs_name_rev
 * Description:	reverse lexical compare of BE names for qsort(3C)
 * Parameters:
 *		x,y - BEs with names to compare
 * Returns:
 *		positive if y>x, negative if x>y, 0 if equal
 * Scope:
 *		Private
 */
static int
be_qsort_compare_BEs_name_rev(const void *x, const void *y)
{
	return (be_qsort_compare_BEs_name(y, x));
}

/*
 * Function:	be_qsort_compare_BEs_space
 * Description:	compare BE sizes for qsort(3C)
 *		will sort BE list in growing order
 * Parameters:
 *		x,y - BEs with names to compare
 * Returns:
 *		positive if x>y, negative if y>x, 0 if equal
 * Scope:
 *		Private
 */
static int
be_qsort_compare_BEs_space(const void *x, const void *y)
{
	be_node_list_t *p = *(be_node_list_t **)x;
	be_node_list_t *q = *(be_node_list_t **)y;

	assert(p != NULL);
	assert(q != NULL);

	if (p->be_space_used > q->be_space_used)
		return (1);
	if (p->be_space_used < q->be_space_used)
		return (-1);
	return (0);
}

/*
 * Function:	be_qsort_compare_BEs_space_rev
 * Description:	compare BE sizes for qsort(3C)
 *		will sort BE list in shrinking
 * Parameters:
 *		x,y - BEs with names to compare
 * Returns:
 *		positive if y>x, negative if x>y, 0 if equal
 * Scope:
 *		Private
 */
static int
be_qsort_compare_BEs_space_rev(const void *x, const void *y)
{
	return (be_qsort_compare_BEs_space(y, x));
}

/*
 * Function:	be_qsort_compare_snapshots
 * Description:	lexical compare of BE names for qsort(3C)
 * Parameters:
 *		x,y - BE snapshots with names to compare
 * Returns:
 *		positive if y>x, negative if x>y, 0 if equal
 * Scope:
 *		Private
 */
static int
be_qsort_compare_snapshots(const void *x, const void *y)
{
	be_snapshot_list_t *p = *(be_snapshot_list_t **)x;
	be_snapshot_list_t *q = *(be_snapshot_list_t **)y;

	if (p == NULL || p->be_snapshot_name == NULL)
		return (1);
	if (q == NULL || q->be_snapshot_name == NULL)
		return (-1);
	return (strcmp(p->be_snapshot_name, q->be_snapshot_name));
}

/*
 * Function:	be_qsort_compare_datasets
 * Description:	lexical compare of dataset names for qsort(3C)
 * Parameters:
 *		x,y - BE snapshots with names to compare
 * Returns:
 *		positive if y>x, negative if x>y, 0 if equal
 * Scope:
 *		Private
 */
static int
be_qsort_compare_datasets(const void *x, const void *y)
{
	be_dataset_list_t *p = *(be_dataset_list_t **)x;
	be_dataset_list_t *q = *(be_dataset_list_t **)y;

	if (p == NULL || p->be_dataset_name == NULL)
		return (1);
	if (q == NULL || q->be_dataset_name == NULL)
		return (-1);
	return (strcmp(p->be_dataset_name, q->be_dataset_name));
}

/*
 * Function:	be_get_node_data
 * Description:	Helper function used to collect all the information to fill
 *		in the be_node_list structure to be returned by be_list.
 * Parameters:
 *		zhp - Handle to the root dataset for the BE whose information
 *		      we're collecting.
 *		be_node - a pointer to the node structure we're filling in.
 *		be_name - The BE name of the node whose information we're
 *		          collecting.
 *		current_be - the name of the currently active BE.
 *		be_ds - The dataset name for the BE.
 *
 * Returns:
 *		BE_SUCCESS - Success
 *		be_errno_t - Failure
 * Scope:
 *		Private
 */
static int
be_get_node_data(
	zfs_handle_t *zhp,
	be_node_list_t *be_node,
	char *be_name,
	const char *rpool,
	char *current_be,
	char *be_ds)
{
	char prop_buf[MAXPATHLEN];
	nvlist_t *userprops = NULL;
	nvlist_t *propval = NULL;
	nvlist_t *zone_propval = NULL;
	char *prop_str = NULL;
	char *zone_prop_str = NULL;
	char *grub_default_bootfs = NULL;
	zpool_handle_t *zphp = NULL;
	int err = 0;

	if (be_node == NULL || be_name == NULL || current_be == NULL ||
	    be_ds == NULL) {
		be_print_err(gettext("be_get_node_data: invalid arguments, "
		    "can not be NULL\n"));
		return (BE_ERR_INVAL);
	}

	errno = 0;

	be_node->be_root_ds = strdup(be_ds);
	if ((err = errno) != 0 || be_node->be_root_ds == NULL) {
		be_print_err(gettext("be_get_node_data: failed to "
		    "copy root dataset name\n"));
		return (errno_to_be_err(err));
	}

	be_node->be_node_name = strdup(be_name);
	if ((err = errno) != 0 || be_node->be_node_name == NULL) {
		be_print_err(gettext("be_get_node_data: failed to "
		    "copy BE name\n"));
		return (errno_to_be_err(err));
	}
	if (strncmp(be_name, current_be, MAXPATHLEN) == 0)
		be_node->be_active = B_TRUE;
	else
		be_node->be_active = B_FALSE;

	be_node->be_rpool = strdup(rpool);
	if (be_node->be_rpool == NULL || (err = errno) != 0) {
		be_print_err(gettext("be_get_node_data: failed to "
		    "copy root pool name\n"));
		return (errno_to_be_err(err));
	}

	be_node->be_space_used = zfs_prop_get_int(zhp, ZFS_PROP_USED);

	if (getzoneid() == GLOBAL_ZONEID) {
		if ((zphp = zpool_open(g_zfs, rpool)) == NULL) {
			be_print_err(gettext("be_get_node_data: failed to open "
			    "pool (%s): %s\n"), rpool,
			    libzfs_error_description(g_zfs));
			return (zfs_err_to_be_err(g_zfs));
		}

		(void) zpool_get_prop(zphp, ZPOOL_PROP_BOOTFS, prop_buf,
		    ZFS_MAXPROPLEN, NULL, B_FALSE);
		if (be_has_grub() && (be_default_grub_bootfs(rpool,
		    &grub_default_bootfs) == BE_SUCCESS) &&
		    grub_default_bootfs != NULL)
			if (strcmp(grub_default_bootfs, be_ds) == 0)
				be_node->be_active_on_boot = B_TRUE;
			else
				be_node->be_active_on_boot = B_FALSE;
		else if (strcmp(prop_buf, be_ds) == 0)
			be_node->be_active_on_boot = B_TRUE;
		else
			be_node->be_active_on_boot = B_FALSE;

		be_node->be_global_active = B_TRUE;

		free(grub_default_bootfs);
		zpool_close(zphp);
	} else {
		if (be_zone_compare_uuids(be_node->be_root_ds))
			be_node->be_global_active = B_TRUE;
		else
			be_node->be_global_active = B_FALSE;
	}

	/*
	 * If the dataset is mounted use the mount point
	 * returned from the zfs_is_mounted call. If the
	 * dataset is not mounted then pull the mount
	 * point information out of the zfs properties.
	 */
	be_node->be_mounted = zfs_is_mounted(zhp,
	    &(be_node->be_mntpt));
	if (!be_node->be_mounted) {
		if (zfs_prop_get(zhp, ZFS_PROP_MOUNTPOINT, prop_buf,
		    ZFS_MAXPROPLEN, NULL, NULL, 0, B_FALSE) == 0)
			be_node->be_mntpt = strdup(prop_buf);
		else
			return (zfs_err_to_be_err(g_zfs));
	}

	be_node->be_node_creation = (time_t)zfs_prop_get_int(zhp,
	    ZFS_PROP_CREATION);

	/* Get all user properties used for libbe */
	if ((userprops = zfs_get_user_props(zhp)) == NULL) {
		be_node->be_policy_type = strdup(be_default_policy());
	} else {
		if (getzoneid() != GLOBAL_ZONEID) {
			if (nvlist_lookup_nvlist(userprops,
			    BE_ZONE_ACTIVE_PROPERTY, &zone_propval) != 0 ||
			    zone_propval == NULL) {
				be_node->be_active_on_boot = B_FALSE;
			} else {
				verify(nvlist_lookup_string(zone_propval,
				    ZPROP_VALUE, &zone_prop_str) == 0);
				if (strcmp(zone_prop_str, "on") == 0) {
					be_node->be_active_on_boot = B_TRUE;
				} else {
					be_node->be_active_on_boot = B_FALSE;
				}
			}
		}

		if (nvlist_lookup_nvlist(userprops, BE_POLICY_PROPERTY,
		    &propval) != 0 || propval == NULL) {
			be_node->be_policy_type =
			    strdup(be_default_policy());
		} else {
			verify(nvlist_lookup_string(propval, ZPROP_VALUE,
			    &prop_str) == 0);
			if (prop_str == NULL || strcmp(prop_str, "-") == 0 ||
			    strcmp(prop_str, "") == 0)
				be_node->be_policy_type =
				    strdup(be_default_policy());
			else
				be_node->be_policy_type = strdup(prop_str);
		}
		if (getzoneid() != GLOBAL_ZONEID) {
			if (nvlist_lookup_nvlist(userprops,
			    BE_ZONE_PARENTBE_PROPERTY, &propval) != 0 &&
			    nvlist_lookup_string(propval, ZPROP_VALUE,
			    &prop_str) == 0) {
				be_node->be_uuid_str = strdup(prop_str);
			}
		} else {
			if (nvlist_lookup_nvlist(userprops, BE_UUID_PROPERTY,
			    &propval) == 0 && nvlist_lookup_string(propval,
			    ZPROP_VALUE, &prop_str) == 0) {
				be_node->be_uuid_str = strdup(prop_str);
			}
		}
	}

	/*
	 * Increment the dataset counter to include the root dataset
	 * of the BE.
	 */
	be_node->be_node_num_datasets++;

	return (BE_SUCCESS);
}

/*
 * Function:	be_get_ds_data
 * Description:	Helper function used by be_add_children_callback to collect
 *		the dataset related information that will be returned by
 *		be_list.
 * Parameters:
 *		zhp - Handle to the zfs dataset whose information we're
 *		      collecting.
 *		name - The name of the dataset we're processing.
 *		dataset - A pointer to the be_dataset_list structure
 *			  we're filling in.
 *		node - The node structure that this dataset belongs to.
 * Return:
 *		BE_SUCCESS - Success
 *		be_errno_t - Failure
 * Scope:
 *		Private
 */
static int
be_get_ds_data(
	zfs_handle_t *zfshp,
	char *name,
	be_dataset_list_t *dataset,
	be_node_list_t *node)
{
	char			prop_buf[ZFS_MAXPROPLEN];
	nvlist_t		*propval = NULL;
	nvlist_t		*userprops = NULL;
	char			*prop_str = NULL;
	int			err = 0;

	if (zfshp == NULL || name == NULL || dataset == NULL || node == NULL) {
		be_print_err(gettext("be_get_ds_data: invalid arguments, "
		    "can not be NULL\n"));
		return (BE_ERR_INVAL);
	}

	errno = 0;

	dataset->be_dataset_name = strdup(name);
	if ((err = errno) != 0) {
		be_print_err(gettext("be_get_ds_data: failed to copy "
		    "dataset name\n"));
		return (errno_to_be_err(err));
	}

	dataset->be_ds_space_used = zfs_prop_get_int(zfshp, ZFS_PROP_USED);

	/*
	 * If the dataset is mounted use the mount point
	 * returned from the zfs_is_mounted call. If the
	 * dataset is not mounted then pull the mount
	 * point information out of the zfs properties.
	 */
	if (!(dataset->be_ds_mounted = zfs_is_mounted(zfshp,
	    &(dataset->be_ds_mntpt)))) {
		if (zfs_prop_get(zfshp, ZFS_PROP_MOUNTPOINT,
		    prop_buf, ZFS_MAXPROPLEN, NULL, NULL, 0,
		    B_FALSE) == 0)
			dataset->be_ds_mntpt = strdup(prop_buf);
		else
			return (zfs_err_to_be_err(g_zfs));
	}
	dataset->be_ds_creation =
	    (time_t)zfs_prop_get_int(zfshp, ZFS_PROP_CREATION);

	/*
	 * Get the user property used for the libbe
	 * cleaup policy
	 */
	if ((userprops = zfs_get_user_props(zfshp)) == NULL) {
		dataset->be_ds_plcy_type =
		    strdup(node->be_policy_type);
	} else {
		if (nvlist_lookup_nvlist(userprops,
		    BE_POLICY_PROPERTY, &propval) != 0 ||
		    propval == NULL) {
			dataset->be_ds_plcy_type =
			    strdup(node->be_policy_type);
		} else {
			verify(nvlist_lookup_string(propval,
			    ZPROP_VALUE, &prop_str) == 0);
			if (prop_str == NULL ||
			    strcmp(prop_str, "-") == 0 ||
			    strcmp(prop_str, "") == 0)
				dataset->be_ds_plcy_type
				    = strdup(node->be_policy_type);
			else
				dataset->be_ds_plcy_type = strdup(prop_str);
		}
	}

	node->be_node_num_datasets++;
	return (BE_SUCCESS);
}

/*
 * Function:	be_get_ss_data
 * Description: Helper function used by be_add_children_callback to collect
 *		the dataset related information that will be returned by
 *		be_list.
 * Parameters:
 *		zhp - Handle to the zfs snapshot whose information we're
 *		      collecting.
 *		name - The name of the snapshot we're processing.
 *		shapshot - A pointer to the be_snapshot_list structure
 *			   we're filling in.
 *		node - The node structure that this snapshot belongs to.
 * Returns:
 *		BE_SUCCESS - Success
 *		be_errno_t - Failure
 * Scope:
 *		Private
 */
static int
be_get_ss_data(
	zfs_handle_t *zfshp,
	char *name,
	be_snapshot_list_t *snapshot,
	be_node_list_t *node)
{
	nvlist_t	*propval = NULL;
	nvlist_t	*userprops = NULL;
	char		*prop_str = NULL;
	int		err = 0;

	if (zfshp == NULL || name == NULL || snapshot == NULL || node == NULL) {
		be_print_err(gettext("be_get_ss_data: invalid arguments, "
		    "can not be NULL\n"));
		return (BE_ERR_INVAL);
	}

	errno = 0;

	snapshot->be_snapshot_name = strdup(name);
	if ((err = errno) != 0) {
		be_print_err(gettext("be_get_ss_data: failed to copy name\n"));
		return (errno_to_be_err(err));
	}

	snapshot->be_snapshot_creation = (time_t)zfs_prop_get_int(zfshp,
	    ZFS_PROP_CREATION);

	/*
	 * Try to get this snapshot's cleanup policy from its
	 * user properties first.  If not there, use default
	 * cleanup policy.
	 */
	if ((userprops = zfs_get_user_props(zfshp)) != NULL &&
	    nvlist_lookup_nvlist(userprops, BE_POLICY_PROPERTY,
	    &propval) == 0 && nvlist_lookup_string(propval,
	    ZPROP_VALUE, &prop_str) == 0) {
		snapshot->be_snapshot_type =
		    strdup(prop_str);
	} else {
		snapshot->be_snapshot_type =
		    strdup(be_default_policy());
	}

	snapshot->be_snapshot_space_used = zfs_prop_get_int(zfshp,
	    ZFS_PROP_USED);

	node->be_node_num_snapshots++;
	return (BE_SUCCESS);
}

/*
 * Function:	be_list_alloc
 * Description: Helper function used to allocate memory for the various
 *		sructures that make up a BE node.
 * Parameters:
 *		err - Used to return any errors encountered.
 *			BE_SUCCESS - Success
 *			BE_ERR_NOMEM - Allocation failure
 *		size - The size of memory to allocate.
 * Returns:
 *		Success - A pointer to the allocated memory
 *		Failure - NULL
 * Scope:
 *		Private
 */
static void*
be_list_alloc(int *err, size_t size)
{
	void *bep = NULL;

	bep = calloc(1, size);
	if (bep == NULL) {
		be_print_err(gettext("be_list_alloc: memory "
		    "allocation failed\n"));
		*err = BE_ERR_NOMEM;
	}
	*err = BE_SUCCESS;
	return (bep);
}

/*
 * Function:	be_get_zone_node_data
 * Description:	Helper function used to collect all the information to
 *		fill in the be_node_list structure to be returned by
 *              be_get_zone_list.
 * Parameters:
 *		be_node - a pointer to the node structure we're filling in.
 *		be_name - The BE name of the node whose information we're
 * Returns:
 *		BE_SUCCESS - Success
 *		be_errno_t - Failure
 * Scope:
 *		Private
 *
 * NOTE: This function currently only collects the zone BE name but when
 *       support for beadm/libbe in a zone is provided it will need to fill
 *       in the rest of the information needed for a zone BE.
 */
static int
be_get_zone_node_data(be_node_list_t *be_node, char *be_name)
{
	if ((be_node->be_node_name = strdup(be_name)) != NULL)
		return (BE_SUCCESS);
	return (BE_ERR_NOMEM);
}