From b3d0b45debb162aa74320d10fdbb5d47724c5ed1 Mon Sep 17 00:00:00 2001 From: yangsheng Date: Fri, 21 Nov 2008 15:27:42 +0000 Subject: [PATCH] Branch b1_6 b=16208 i=adilger, johann Add utility for showing mounted hosts --- lustre/doc/Makefile.am | 2 +- lustre/doc/lshowmount.8 | 43 + lustre/utils/Makefile.am | 5 +- lustre/utils/hash.c | 446 ++++++++ lustre/utils/hash.h | 177 +++ lustre/utils/hostlist.c | 2687 +++++++++++++++++++++++++++++++++++++++++++++ lustre/utils/hostlist.h | 417 +++++++ lustre/utils/lshowmount.c | 411 +++++++ lustre/utils/lshowmount.h | 17 + lustre/utils/thread.c | 50 + lustre/utils/thread.h | 106 ++ 11 files changed, 4359 insertions(+), 2 deletions(-) create mode 100644 lustre/doc/lshowmount.8 create mode 100644 lustre/utils/hash.c create mode 100644 lustre/utils/hash.h create mode 100644 lustre/utils/hostlist.c create mode 100644 lustre/utils/hostlist.h create mode 100644 lustre/utils/lshowmount.c create mode 100644 lustre/utils/lshowmount.h create mode 100644 lustre/utils/thread.c create mode 100644 lustre/utils/thread.h diff --git a/lustre/doc/Makefile.am b/lustre/doc/Makefile.am index 21d0603..0b87c5f 100644 --- a/lustre/doc/Makefile.am +++ b/lustre/doc/Makefile.am @@ -48,7 +48,7 @@ SUFFIXES = .lin .lyx .pdf .ps .sgml .html .txt .tex .fig .eps .dvi MANFILES = lustre.7 lfs.1 mount.lustre.8 mkfs.lustre.8 tunefs.lustre.8 lctl.8 \ llverdev.8 llbackup.8 llapi_quotactl.3 llobdstat.8 llstat.8 plot-llstat.8 \ - l_getgroups.8 lst.8 routerstat.8 + l_getgroups.8 lst.8 routerstat.8 lshowmount.8 if UTILS man_MANS = $(MANFILES) endif diff --git a/lustre/doc/lshowmount.8 b/lustre/doc/lshowmount.8 new file mode 100644 index 0000000..a2ad08e --- /dev/null +++ b/lustre/doc/lshowmount.8 @@ -0,0 +1,43 @@ +.TH LSHOWMOUNT 8 Lustre LLNL LSHOWMOUNT +.SH NAME +lshowmount \- show lustre exports +.SH SYNOPSIS +.B "lshowmount [-ehlv]" +.br +.SH DESCRIPTION +.B lshowmount +Utility to show the hosts that have lustre currently mounted to a server. +Ths utility looks for any exports from the mgs, mds, and obdfilter. +.SH OPTIONS +.B lshowmount +accepts the following options: +.TP +.I "-e | --enumerate" +causes +.B lshowmount +to list each client mounted on a separate line instead of trying +to compress the list of clients into a hostrange string. +.TP +.I "-h | --help" +causes +.B lshowmount +to print out a usage message. +.TP +.I "-l | --lookup" +causes +.B lshowmount +to try to lookup the hostname for nids that look like IP addresses. +.TP +.I "-v | --verbose" +causes +.B lshowmount +to output export information for each service instead of only displaying +the aggregate information for all Lustre services on the server. +.SH FILES +/proc/fs/lustre/mgs//exports//nid +.br +/proc/fs/lustre/mds//exports//nid +.br +/proc/fs/lustre/obdfilter//exports//nid +.SH AUTHOR +Herb Wartens diff --git a/lustre/utils/Makefile.am b/lustre/utils/Makefile.am index ca52aec4..709a7e5 100644 --- a/lustre/utils/Makefile.am +++ b/lustre/utils/Makefile.am @@ -16,7 +16,7 @@ EXTRA_PROGRAMS = wirecheck rootsbin_PROGRAMS = mount.lustre sbin_PROGRAMS = mkfs.lustre tunefs.lustre lctl wiretest \ l_getgroups llverfs llverdev llog_reader ll_recover_lost_found_objs \ - lr_reader ltrack_stats + lr_reader ltrack_stats lshowmount if LIBPTHREAD sbin_PROGRAMS += loadgen endif @@ -39,6 +39,9 @@ loadgen_SOURCES = loadgen.c lustre_cfg.c obd.c loadgen_LDADD := $(LIBREADLINE) $(LIBPTLCTL) $(PTHREAD_LIBS) loadgen_DEPENDENCIES := $(LIBPTLCTL) +lshowmount_SOURCES = lshowmount.h lshowmount.c hash.c hash.h \ + thread.c thread.h hostlist.c hostlist.h + if EXT2FS_DEVEL EXT2FSLIB = -lext2fs E2PLIB = -le2p diff --git a/lustre/utils/hash.c b/lustre/utils/hash.c new file mode 100644 index 0000000..0717176 --- /dev/null +++ b/lustre/utils/hash.c @@ -0,0 +1,446 @@ +/***************************************************************************** + * $Id: hash.c,v 1.1.2.1 2008/11/21 15:27:33 yangsheng Exp $ + ***************************************************************************** + * Copyright (C) 2003-2005 The Regents of the University of California. + * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER). + * Written by Chris Dunlap . + * + * This file is from LSD-Tools, the LLNL Software Development Toolbox. + * + * This is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * for more details. + * + * You should have received a copy of the GNU General Public License; + * if not, write to the Free Software Foundation, Inc., 51 Franklin Street, + * Fifth Floor, Boston, MA 02110-1301 USA. + ***************************************************************************** + * Refer to "hash.h" for documentation on public functions. + *****************************************************************************/ + + +#if HAVE_CONFIG_H +# include "config.h" +#endif /* HAVE_CONFIG_H */ + +#include +#include +#include +#include + +#include "thread.h" +#include "hash.h" + + +/***************************************************************************** + * Constants + *****************************************************************************/ + +#define HASH_ALLOC 1024 +#define HASH_DEF_SIZE 1213 +#define HASH_MAGIC 0xDEADBEEF + + +/***************************************************************************** + * Data Types + *****************************************************************************/ + +struct hash_node { + struct hash_node *next; /* next node in list */ + void *data; /* ptr to hashed item */ + const void *hkey; /* ptr to hashed item's key */ +}; + +struct hash { + int count; /* number of items in hash table */ + int size; /* num slots allocated in hash table */ + struct hash_node **table; /* hash table array of node ptrs */ + hash_cmp_f cmp_f; /* key comparison function */ + hash_del_f del_f; /* item deletion function */ + hash_key_f key_f; /* key hash function */ +#if WITH_PTHREADS + pthread_mutex_t mutex; /* mutex to protect access to hash */ +#endif /* WITH_PTHREADS */ +#ifndef NDEBUG + unsigned int magic; /* sentinel for asserting validity */ +#endif /* NDEBUG */ +}; + + +/***************************************************************************** + * Prototypes + *****************************************************************************/ + +static struct hash_node * hash_node_alloc (void); + +static void hash_node_free (struct hash_node *node); + + +/***************************************************************************** + * Variables + *****************************************************************************/ + +#if 0 +static struct hash_node *hash_free_list = NULL; +#endif + +#if WITH_PTHREADS +static pthread_mutex_t hash_free_lock = PTHREAD_MUTEX_INITIALIZER; +#endif /* WITH_PTHREADS */ + + +/***************************************************************************** + * Macros + *****************************************************************************/ + +#ifdef WITH_LSD_FATAL_ERROR_FUNC +# undef lsd_fatal_error + extern void lsd_fatal_error (char *file, int line, char *mesg); +#else /* !WITH_LSD_FATAL_ERROR_FUNC */ +# ifndef lsd_fatal_error +# define lsd_fatal_error(file, line, mesg) (abort ()) +# endif /* !lsd_fatal_error */ +#endif /* !WITH_LSD_FATAL_ERROR_FUNC */ + +#ifdef WITH_LSD_NOMEM_ERROR_FUNC +# undef lsd_nomem_error + extern void * lsd_nomem_error (char *file, int line, char *mesg); +#else /* !WITH_LSD_NOMEM_ERROR_FUNC */ +# ifndef lsd_nomem_error +# define lsd_nomem_error(file, line, mesg) (NULL) +# endif /* !lsd_nomem_error */ +#endif /* !WITH_LSD_NOMEM_ERROR_FUNC */ + + +/***************************************************************************** + * Functions + *****************************************************************************/ + +hash_t +hash_create (int size, hash_key_f key_f, hash_cmp_f cmp_f, hash_del_f del_f) +{ + hash_t h; + + if (!cmp_f || !key_f) { + errno = EINVAL; + return (NULL); + } + if (size <= 0) { + size = HASH_DEF_SIZE; + } + if (!(h = malloc (sizeof (*h)))) { + return (lsd_nomem_error (__FILE__, __LINE__, "hash_create")); + } + if (!(h->table = calloc (size, sizeof (struct hash_node *)))) { + free (h); + return (lsd_nomem_error (__FILE__, __LINE__, "hash_create")); + } + h->count = 0; + h->size = size; + h->cmp_f = cmp_f; + h->del_f = del_f; + h->key_f = key_f; + lsd_mutex_init (&h->mutex); + assert (h->magic = HASH_MAGIC); /* set magic via assert abuse */ + return (h); +} + + +void +hash_destroy (hash_t h) +{ + int i; + struct hash_node *p, *q; + + if (!h) { + errno = EINVAL; + return; + } + lsd_mutex_lock (&h->mutex); + assert (h->magic == HASH_MAGIC); + for (i = 0; i < h->size; i++) { + for (p = h->table[i]; p != NULL; p = q) { + q = p->next; + if (h->del_f) + h->del_f (p->data); + hash_node_free (p); + } + } + assert (h->magic = ~HASH_MAGIC); /* clear magic via assert abuse */ + lsd_mutex_unlock (&h->mutex); + lsd_mutex_destroy (&h->mutex); + free (h->table); + free (h); + return; +} + + +int +hash_is_empty (hash_t h) +{ + int n; + + if (!h) { + errno = EINVAL; + return (0); + } + lsd_mutex_lock (&h->mutex); + assert (h->magic == HASH_MAGIC); + n = h->count; + lsd_mutex_unlock (&h->mutex); + return (n == 0); +} + + +int +hash_count (hash_t h) +{ + int n; + + if (!h) { + errno = EINVAL; + return (0); + } + lsd_mutex_lock (&h->mutex); + assert (h->magic == HASH_MAGIC); + n = h->count; + lsd_mutex_unlock (&h->mutex); + return (n); +} + + +void * +hash_find (hash_t h, const void *key) +{ + unsigned int slot; + struct hash_node *p; + void *data = NULL; + + if (!h || !key) { + errno = EINVAL; + return (NULL); + } + errno = 0; + lsd_mutex_lock (&h->mutex); + assert (h->magic == HASH_MAGIC); + slot = h->key_f (key) % h->size; + for (p = h->table[slot]; p != NULL; p = p->next) { + if (!h->cmp_f (p->hkey, key)) { + data = p->data; + break; + } + } + lsd_mutex_unlock (&h->mutex); + return (data); +} + + +void * +hash_insert (hash_t h, const void *key, void *data) +{ + struct hash_node *p; + unsigned int slot; + + if (!h || !key || !data) { + errno = EINVAL; + return (NULL); + } + lsd_mutex_lock (&h->mutex); + assert (h->magic == HASH_MAGIC); + slot = h->key_f (key) % h->size; + for (p = h->table[slot]; p != NULL; p = p->next) { + if (!h->cmp_f (p->hkey, key)) { + errno = EEXIST; + data = NULL; + goto end; + } + } + if (!(p = hash_node_alloc ())) { + data = lsd_nomem_error (__FILE__, __LINE__, "hash_insert"); + goto end; + } + p->hkey = key; + p->data = data; + p->next = h->table[slot]; + h->table[slot] = p; + h->count++; + +end: + lsd_mutex_unlock (&h->mutex); + return (data); +} + + +void * +hash_remove (hash_t h, const void *key) +{ + struct hash_node **pp; + struct hash_node *p; + unsigned int slot; + void *data = NULL; + + if (!h || !key) { + errno = EINVAL; + return (NULL); + } + errno = 0; + lsd_mutex_lock (&h->mutex); + assert (h->magic == HASH_MAGIC); + slot = h->key_f (key) % h->size; + for (pp = &(h->table[slot]); (p = *pp) != NULL; pp = &((*pp)->next)) { + if (!h->cmp_f (p->hkey, key)) { + data = p->data; + *pp = p->next; + hash_node_free (p); + h->count--; + break; + } + } + lsd_mutex_unlock (&h->mutex); + return (data); +} + + +int +hash_delete_if (hash_t h, hash_arg_f arg_f, void *arg) +{ + int i; + struct hash_node **pp; + struct hash_node *p; + int n = 0; + + if (!h || !arg_f) { + errno = EINVAL; + return (-1); + } + lsd_mutex_lock (&h->mutex); + assert (h->magic == HASH_MAGIC); + for (i = 0; i < h->size; i++) { + pp = &(h->table[i]); + while ((p = *pp) != NULL) { + if (arg_f (p->data, p->hkey, arg) > 0) { + if (h->del_f) + h->del_f (p->data); + *pp = p->next; + hash_node_free (p); + h->count--; + n++; + } + else { + pp = &(p->next); + } + } + } + lsd_mutex_unlock (&h->mutex); + return (n); +} + + +int +hash_for_each (hash_t h, hash_arg_f arg_f, void *arg) +{ + int i; + struct hash_node *p; + int n = 0; + + if (!h || !arg_f) { + errno = EINVAL; + return (-1); + } + lsd_mutex_lock (&h->mutex); + assert (h->magic == HASH_MAGIC); + for (i = 0; i < h->size; i++) { + for (p = h->table[i]; p != NULL; p = p->next) { + if (arg_f (p->data, p->hkey, arg) > 0) { + n++; + } + } + } + lsd_mutex_unlock (&h->mutex); + return (n); +} + + +/***************************************************************************** + * Hash Functions + *****************************************************************************/ + +unsigned int +hash_key_string (const char *str) +{ + unsigned char *p; + unsigned int hval = 0; + const unsigned int multiplier = 31; + + for (p = (unsigned char *) str; *p != '\0'; p++) { + hval += (multiplier * hval) + *p; + } + return (hval); +} + + +/***************************************************************************** + * Internal Functions + *****************************************************************************/ + +static struct hash_node * +hash_node_alloc (void) +{ +/* Allocates a hash node from the freelist. + * Memory is allocated in chunks of HASH_ALLOC. + * Returns a ptr to the object, or NULL if memory allocation fails. + */ +#if 0 + int i; +#endif + struct hash_node *p = NULL; + + assert (HASH_ALLOC > 0); + lsd_mutex_lock (&hash_free_lock); +#if 0 + if (!hash_free_list) { + if ((hash_free_list = malloc (HASH_ALLOC * sizeof (*p)))) { + for (i = 0; i < HASH_ALLOC - 1; i++) + hash_free_list[i].next = &hash_free_list[i+1]; + hash_free_list[i].next = NULL; + } + } + if (hash_free_list) { + p = hash_free_list; + hash_free_list = p->next; + } + else { + errno = ENOMEM; + } +#else + if (!(p = malloc (sizeof(*p)))) + errno = ENOMEM; +#endif + lsd_mutex_unlock (&hash_free_lock); + return (p); +} + + +static void +hash_node_free (struct hash_node *node) +{ +/* De-allocates the object [node], returning it to the freelist. + */ + assert (node != NULL); + memset (node, 0, sizeof (*node)); + lsd_mutex_lock (&hash_free_lock); +#if 0 + node->next = hash_free_list; + hash_free_list = node; +#else + free (node); +#endif + lsd_mutex_unlock (&hash_free_lock); + return; +} diff --git a/lustre/utils/hash.h b/lustre/utils/hash.h new file mode 100644 index 0000000..9926c4a --- /dev/null +++ b/lustre/utils/hash.h @@ -0,0 +1,177 @@ +/***************************************************************************** + * $Id: hash.h,v 1.1.2.1 2008/11/21 15:27:33 yangsheng Exp $ + ***************************************************************************** + * Copyright (C) 2003-2005 The Regents of the University of California. + * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER). + * Written by Chris Dunlap . + * + * This file is from LSD-Tools, the LLNL Software Development Toolbox. + * + * This is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * for more details. + * + * You should have received a copy of the GNU General Public License; + * if not, write to the Free Software Foundation, Inc., 51 Franklin Street, + * Fifth Floor, Boston, MA 02110-1301 USA. + *****************************************************************************/ + + +#ifndef LSD_HASH_H +#define LSD_HASH_H + + +/***************************************************************************** + * Notes + *****************************************************************************/ +/* + * If an item's key is modified after insertion, the hash will be unable to + * locate it if the new key should hash to a different slot in the table. + * + * If NDEBUG is not defined, internal debug code will be enabled; this is + * intended for development use only. Production code should define NDEBUG. + * + * If WITH_LSD_FATAL_ERROR_FUNC is defined, the linker will expect to + * find an external lsd_fatal_error(file,line,mesg) function. By default, + * lsd_fatal_error(file,line,mesg) is a macro definition that aborts. + * This macro may be redefined to invoke another routine instead. + * + * If WITH_LSD_NOMEM_ERROR_FUNC is defined, the linker will expect to + * find an external lsd_nomem_error(file,line,mesg) function. By default, + * lsd_nomem_error(file,line,mesg) is a macro definition that returns NULL. + * This macro may be redefined to invoke another routine instead. + * + * If WITH_PTHREADS is defined, these routines will be thread-safe. + */ + + +/***************************************************************************** + * Data Types + *****************************************************************************/ + +typedef struct hash * hash_t; +/* + * Hash table opaque data type. + */ + +typedef unsigned int (*hash_key_f) (const void *key); +/* + * Function prototype for the hash function responsible for converting + * the data's [key] into an unsigned integer hash value. + */ + +typedef int (*hash_cmp_f) (const void *key1, const void *key2); +/* + * Function prototype for comparing two keys. + * Returns zero if both keys are equal; o/w, returns nonzero. + */ + +typedef void (*hash_del_f) (void *data); +/* + * Function prototype for de-allocating a data item stored within a hash. + * This function is responsible for freeing all memory associated with + * the [data] item, including any subordinate items. + */ + +typedef int (*hash_arg_f) (void *data, const void *key, void *arg); +/* + * Function prototype for operating on each element in the hash table. + * The function will be invoked once for each [data] item in the hash, + * with the item's [key] and the specified [arg] being passed in as args. + */ + + +/***************************************************************************** + * Functions + *****************************************************************************/ + +hash_t hash_create (int size, + hash_key_f key_f, hash_cmp_f cmp_f, hash_del_f del_f); +/* + * Creates and returns a new hash table on success. + * Returns lsd_nomem_error() with errno=ENOMEM if memory allocation fails. + * Returns NULL with errno=EINVAL if [keyf] or [cmpf] is not specified. + * The [size] is the number of slots in the table; a larger table requires + * more memory, but generally provide quicker access times. If set <= 0, + * the default size is used. + * The [keyf] function converts a key into a hash value. + * The [cmpf] function determines whether two keys are equal. + * The [delf] function de-allocates memory used by items in the hash; + * if set to NULL, memory associated with these items will not be freed + * when the hash is destroyed. + */ + +void hash_destroy (hash_t h); +/* + * Destroys hash table [h]. If a deletion function was specified when the + * hash was created, it will be called for each item contained within. + * Abadoning a hash without calling hash_destroy() will cause a memory leak. + */ + +int hash_is_empty (hash_t h); +/* + * Returns non-zero if hash table [h] is empty; o/w, returns zero. + */ + +int hash_count (hash_t h); +/* + * Returns the number of items in hash table [h]. + */ + +void * hash_find (hash_t h, const void *key); +/* + * Searches for the item corresponding to [key] in hash table [h]. + * Returns a ptr to the found item's data on success. + * Returns NULL with errno=0 if no matching item is found. + * Returns NULL with errno=EINVAL if [key] is not specified. + */ + +void * hash_insert (hash_t h, const void *key, void *data); +/* + * Inserts [data] with the corresponding [key] into hash table [h]; + * note that it is permissible for [key] to be set equal to [data]. + * Returns a ptr to the inserted item's data on success. + * Returns NULL with errno=EEXIST if [key] already exists in the hash. + * Returns NULL with errno=EINVAL if [key] or [data] is not specified. + * Returns lsd_nomem_error() with errno=ENOMEM if memory allocation fails. + */ + +void * hash_remove (hash_t h, const void *key); +/* + * Removes the item corresponding to [key] from hash table [h]. + * Returns a ptr to the removed item's data on success. + * Returns NULL with errno=0 if no matching item is found. + * Returns NULL with errno=EINVAL if [key] is not specified. + */ + +int hash_delete_if (hash_t h, hash_arg_f argf, void *arg); +/* + * Conditionally deletes (and de-allocates) items from hash table [h]. + * The [argf] function is invoked once for each item in the hash, with + * [arg] being passed in as an argument. Items for which [argf] returns + * greater-than-zero are deleted. + * Returns the number of items deleted. + * Returns -1 with errno=EINVAL if [argf] is not specified. + */ + +int hash_for_each (hash_t h, hash_arg_f argf, void *arg); +/* + * Invokes the [argf] function once for each item in hash table [h], + * with [arg] being passed in as an argument. + * Returns the number of items for which [argf] returns greater-than-zero. + * Returns -1 with errno=EINVAL if [argf] is not specified. + */ + +unsigned int hash_key_string (const char *str); +/* + * A hash_key_f function that hashes the string [str]. + */ + + +#endif /* !LSD_HASH_H */ diff --git a/lustre/utils/hostlist.c b/lustre/utils/hostlist.c new file mode 100644 index 0000000..cbddfd2 --- /dev/null +++ b/lustre/utils/hostlist.c @@ -0,0 +1,2687 @@ +/*****************************************************************************\ + * $Id: hostlist.c,v 1.1.2.1 2008/11/21 15:27:33 yangsheng Exp $ + ***************************************************************************** + * Copyright (C) 2002 The Regents of the University of California. + * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER). + * Written by Mark Grondona + * UCRL-CODE-2002-040. + * + * This file is part of SLURM, a resource management program. + * For details, see . + * + * SLURM is free software; you can redistribute it and/or modify it under + * the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. + * + * SLURM is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more + * details. + * + * You should have received a copy of the GNU General Public License along + * with SLURM; if not, write to the Free Software Foundation, Inc., + * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. +\*****************************************************************************/ + +#ifdef HAVE_CONFIG_H +# include "config.h" +# if HAVE_STRING_H +# include +# endif +# if HAVE_PTHREAD_H +# include +# endif +#else /* !HAVE_CONFIG_H */ +# include +# include +#endif /* HAVE_CONFIG_H */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "hostlist.h" + +/* + * lsd_fatal_error : fatal error macro + */ +#ifdef WITH_LSD_FATAL_ERROR_FUNC +# undef lsd_fatal_error + extern void lsd_fatal_error(char *file, int line, char *mesg); +#else /* !WITH_LSD_FATAL_ERROR_FUNC */ +# ifndef lsd_fatal_error +# define lsd_fatal_error(file, line, mesg) \ + do { \ + fprintf(stderr, "ERROR: [%s:%d] %s: %s\n", \ + file, line, mesg, strerror(errno)); \ + } while (0) +# endif /* !lsd_fatal_error */ +#endif /* !WITH_LSD_FATAL_ERROR_FUNC */ + +/* + * lsd_nonmem_error + */ +#ifdef WITH_LSD_NOMEM_ERROR_FUNC +# undef lsd_nomem_error + extern void * lsd_nomem_error(char *file, int line, char *mesg); +#else /* !WITH_LSD_NOMEM_ERROR_FUNC */ +# ifndef lsd_nomem_error +# define lsd_nomem_error(file, line, mesg) (NULL) +# endif /* !lsd_nomem_error */ +#endif /* !WITH_LSD_NOMEM_ERROR_FUNC */ + +/* + * OOM helper function + * Automatically call lsd_nomem_error with appropriate args + * and set errno to ENOMEM + */ +#define out_of_memory(mesg) \ + do { \ + errno = ENOMEM; \ + return(lsd_nomem_error(__FILE__, __LINE__, mesg)); \ + } while (0) + +/* + * Some constants and tunables: + */ + +/* number of elements to allocate when extending the hostlist array */ +#define HOSTLIST_CHUNK 16 + +/* max host range: anything larger will be assumed to be an error */ +#define MAX_RANGE 16384 /* 16K Hosts */ + +/* max host suffix value */ +#define MAX_HOST_SUFFIX 1<<25 + +/* max number of ranges that will be processed between brackets */ +#define MAX_RANGES 10240 /* 10K Ranges */ + +/* size of internal hostname buffer (+ some slop), hostnames will probably + * be truncated if longer than MAXHOSTNAMELEN */ +#ifndef MAXHOSTNAMELEN +#define MAXHOSTNAMELEN 64 +#endif + +/* max size of internal hostrange buffer */ +#define MAXHOSTRANGELEN 1024 + +/* ----[ Internal Data Structures ]---- */ + +/* hostname type: A convenience structure used in parsing single hostnames */ +struct hostname_components { + char *hostname; /* cache of initialized hostname */ + char *prefix; /* hostname prefix */ + unsigned long num; /* numeric suffix */ + + /* string representation of numeric suffix + * points into `hostname' */ + char *suffix; +}; + +typedef struct hostname_components *hostname_t; + +/* hostrange type: A single prefix with `hi' and `lo' numeric suffix values */ +struct hostrange_components { + char *prefix; /* alphanumeric prefix: */ + + /* beginning (lo) and end (hi) of suffix range */ + unsigned long lo, hi; + + /* width of numeric output format + * (pad with zeros up to this width) */ + int width; + + /* If singlehost is 1, `lo' and `hi' are invalid */ + unsigned singlehost:1; +}; + +typedef struct hostrange_components *hostrange_t; + +/* The hostlist type: An array based list of hostrange_t's */ +struct hostlist { +#ifndef NDEBUG +#define HOSTLIST_MAGIC 57005 + int magic; +#endif +#if WITH_PTHREADS + pthread_mutex_t mutex; +#endif /* WITH_PTHREADS */ + + /* current number of elements available in array */ + int size; + + /* current number of ranges stored in array */ + int nranges; + + /* current number of hosts stored in hostlist */ + int nhosts; + + /* pointer to hostrange array */ + hostrange_t *hr; + + /* list of iterators */ + struct hostlist_iterator *ilist; + +}; + + +/* a hostset is a wrapper around a hostlist */ +struct hostset { + hostlist_t hl; +}; + +struct hostlist_iterator { +#ifndef NDEBUG + int magic; +#endif + /* hostlist we are traversing */ + hostlist_t hl; + + /* current index of iterator in hl->hr[] */ + int idx; + + /* current hostrange object in list hl, i.e. hl->hr[idx] */ + hostrange_t hr; + + /* current depth we've traversed into range hr */ + int depth; + + /* next ptr for lists of iterators */ + struct hostlist_iterator *next; +}; + + +/* ---- ---- */ + +/* ------[ static function prototypes ]------ */ + +static void _error(char *file, int line, char *mesg, ...); +static char * _next_tok(char *, char **); +static int _zero_padded(unsigned long, int); +static int _width_equiv(unsigned long, int *, unsigned long, int *); + +static int host_prefix_end(const char *); +static hostname_t hostname_create(const char *); +static void hostname_destroy(hostname_t); +static int hostname_suffix_is_valid(hostname_t); +static int hostname_suffix_width(hostname_t); + +static hostrange_t hostrange_new(void); +static hostrange_t hostrange_create_single(const char *); +static hostrange_t hostrange_create(char *, unsigned long, unsigned long, int); +static unsigned long hostrange_count(hostrange_t); +static hostrange_t hostrange_copy(hostrange_t); +static void hostrange_destroy(hostrange_t); +static hostrange_t hostrange_delete_host(hostrange_t, unsigned long); +static int hostrange_cmp(hostrange_t, hostrange_t); +static int hostrange_prefix_cmp(hostrange_t, hostrange_t); +static int hostrange_within_range(hostrange_t, hostrange_t); +static int hostrange_width_combine(hostrange_t, hostrange_t); +static int hostrange_empty(hostrange_t); +static char * hostrange_pop(hostrange_t); +static char * hostrange_shift(hostrange_t); +static int hostrange_join(hostrange_t, hostrange_t); +static hostrange_t hostrange_intersect(hostrange_t, hostrange_t); +static int hostrange_hn_within(hostrange_t, hostname_t); +static size_t hostrange_to_string(hostrange_t hr, size_t, char *, char *); +static size_t hostrange_numstr(hostrange_t, size_t, char *); + +static hostlist_t hostlist_new(void); +static hostlist_t _hostlist_create_bracketed(const char *, char *, char *); +static int hostlist_resize(hostlist_t, size_t); +static int hostlist_expand(hostlist_t); +static int hostlist_push_range(hostlist_t, hostrange_t); +static int hostlist_push_hr(hostlist_t, char *, unsigned long, + unsigned long, int); +static int hostlist_insert_range(hostlist_t, hostrange_t, int); +static void hostlist_delete_range(hostlist_t, int n); +static void hostlist_coalesce(hostlist_t hl); +static void hostlist_collapse(hostlist_t hl); +static hostlist_t _hostlist_create(const char *, char *, char *); +static void hostlist_shift_iterators(hostlist_t, int, int, int); +static int _attempt_range_join(hostlist_t, int); +static int _is_bracket_needed(hostlist_t, int); + +static hostlist_iterator_t hostlist_iterator_new(void); +static void _iterator_advance(hostlist_iterator_t); +static void _iterator_advance_range(hostlist_iterator_t); + +static int hostset_find_host(hostset_t, const char *); + +/* ------[ macros ]------ */ + +#ifdef WITH_PTHREADS +# define mutex_init(mutex) \ + do { \ + int e = pthread_mutex_init(mutex, NULL); \ + if (e) { \ + errno = e; \ + lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex init:"); \ + abort(); \ + } \ + } while (0) + +# define mutex_lock(mutex) \ + do { \ + int e = pthread_mutex_lock(mutex); \ + if (e) { \ + errno = e; \ + lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex lock:"); \ + abort(); \ + } \ + } while (0) + +# define mutex_unlock(mutex) \ + do { \ + int e = pthread_mutex_unlock(mutex); \ + if (e) { \ + errno = e; \ + lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex unlock:"); \ + abort(); \ + } \ + } while (0) + +# define mutex_destroy(mutex) \ + do { \ + int e = pthread_mutex_destroy(mutex); \ + if (e) { \ + errno = e; \ + lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex destroy:"); \ + abort(); \ + } \ + } while (0) + +#else /* !WITH_PTHREADS */ + +# define mutex_init(mutex) +# define mutex_lock(mutex) +# define mutex_unlock(mutex) +# define mutex_destroy(mutex) + +#endif /* WITH_PTHREADS */ + +#define LOCK_HOSTLIST(_hl) \ + do { \ + assert(_hl != NULL); \ + mutex_lock(&(_hl)->mutex); \ + assert((_hl)->magic == HOSTLIST_MAGIC); \ + } while (0) + +#define UNLOCK_HOSTLIST(_hl) \ + do { \ + mutex_unlock(&(_hl)->mutex); \ + } while (0) + +#define seterrno_ret(_errno, _rc) \ + do { \ + errno = _errno; \ + return _rc; \ + } while (0) + +/* ------[ Function Definitions ]------ */ + +/* ----[ general utility functions ]---- */ + + +/* + * Varargs capable error reporting via lsd_fatal_error() + */ +static void _error(char *file, int line, char *msg, ...) +{ + va_list ap; + char buf[1024]; + int len = 0; + va_start(ap, msg); + + len = vsnprintf(buf, 1024, msg, ap); + if ((len < 0) || (len > 1024)) + buf[1023] = '\0'; + + lsd_fatal_error(file, line, buf); + + va_end(ap); + return; +} + +static int _advance_past_brackets (char *tok, char **str) +{ + /* if _single_ opening bracket exists b/w tok and str, push str + * past first closing bracket to next seperator */ + if ( memchr(tok, '[', *str - tok) != NULL + && memchr(tok, ']', *str - tok) == NULL ) { + char *q = strchr(*str, ']'); + if (q && memchr(*str, '[', q - *str) == NULL) { + *str = q + 1; + return (1); + } + } + + return 0; +} + +/* + * Helper function for host list string parsing routines + * Returns a pointer to the next token; additionally advance *str + * to the next separator. + * + * next_tok was taken directly from pdsh courtesy of Jim Garlick. + * (with modifications to support bracketed hostlists, i.e.: + * xxx[xx,xx,xx] is a single token) + * + */ +static char * _next_tok(char *sep, char **str) +{ + char *tok; + + /* push str past any leading separators */ + while (**str != '\0' && strchr(sep, **str) != '\0') + (*str)++; + + if (**str == '\0') + return NULL; + + /* assign token ptr */ + tok = *str; + + /* + * Advance str past any separators, but if a separator occurs between + * brackets, e.g. foo[0-3,5], then advance str past closing brackets and + * try again. + */ + do { + /* push str past token and leave pointing to first separator */ + while (**str != '\0' && strchr(sep, **str) == '\0') + (*str)++; + } while (_advance_past_brackets (tok, str)); + + /* nullify consecutive separators and push str beyond them */ + while (**str != '\0' && strchr(sep, **str) != '\0') + *(*str)++ = '\0'; + + return tok; +} + + +/* return the number of zeros needed to pad "num" to "width" + */ +static int _zero_padded(unsigned long num, int width) +{ + int n = 1; + while (num /= 10L) + n++; + return width > n ? width - n : 0; +} + +/* test whether two format `width' parameters are "equivalent" + * The width arguments "wn" and "wm" for integers "n" and "m" + * are equivalent if: + * + * o wn == wm OR + * + * o applying the same format width (either wn or wm) to both of + * 'n' and 'm' will not change the zero padding of *either* 'm' nor 'n'. + * + * If this function returns 1 (or true), the appropriate width value + * (either 'wm' or 'wn') will have been adjusted such that both format + * widths are equivalent. + */ +static int _width_equiv(unsigned long n, int *wn, unsigned long m, int *wm) +{ + int npad, nmpad, mpad, mnpad; + + if (wn == wm) + return 1; + + npad = _zero_padded(n, *wn); + nmpad = _zero_padded(n, *wm); + mpad = _zero_padded(m, *wm); + mnpad = _zero_padded(m, *wn); + + if (npad != nmpad && mpad != mnpad) + return 0; + + if (npad != nmpad) { + if (mpad == mnpad) { + *wm = *wn; + return 1; + } else + return 0; + } else { /* mpad != mnpad */ + if (npad == nmpad) { + *wn = *wm; + return 1; + } else + return 0; + } + + /* not reached */ +} + + +/* ----[ hostname_t functions ]---- */ + +/* + * return the location of the last char in the hostname prefix + */ +static int host_prefix_end(const char *hostname) +{ + int idx = strlen(hostname) - 1; + + while (idx >= 0 && isdigit((char) hostname[idx])) + idx--; + return idx; +} + +/* + * create a hostname_t object from a string hostname + */ +static hostname_t hostname_create(const char *hostname) +{ + hostname_t hn = NULL; + char *p = '\0'; + int idx = 0; + + assert(hostname != NULL); + + if (!(hn = (hostname_t) malloc(sizeof(*hn)))) + out_of_memory("hostname create"); + + idx = host_prefix_end(hostname); + + if (!(hn->hostname = strdup(hostname))) { + free(hn); + out_of_memory("hostname create"); + } + + hn->num = 0; + hn->prefix = NULL; + hn->suffix = NULL; + + if (idx == strlen(hostname) - 1) { + if ((hn->prefix = strdup(hostname)) == NULL) { + hostname_destroy(hn); + out_of_memory("hostname prefix create"); + } + return hn; + } + + hn->suffix = hn->hostname + idx + 1; + hn->num = strtoul(hn->suffix, &p, 10); + + if ((*p == '\0') && (hn->num <= MAX_HOST_SUFFIX)) { + if (!(hn->prefix = malloc((idx + 2) * sizeof(char)))) { + hostname_destroy(hn); + out_of_memory("hostname prefix create"); + } + memcpy(hn->prefix, hostname, idx + 1); + hn->prefix[idx + 1] = '\0'; + } else { + if (!(hn->prefix = strdup(hostname))) { + hostname_destroy(hn); + out_of_memory("hostname prefix create"); + } + hn->suffix = NULL; + } + + return hn; +} + +/* free a hostname object + */ +static void hostname_destroy(hostname_t hn) +{ + if (hn == NULL) + return; + hn->suffix = NULL; + if (hn->hostname) + free(hn->hostname); + if (hn->prefix) + free(hn->prefix); + free(hn); +} + +/* return true if the hostname has a valid numeric suffix + */ +static int hostname_suffix_is_valid(hostname_t hn) +{ + return hn->suffix != NULL; +} + +/* return the width (in characters) of the numeric part of the hostname + */ +static int hostname_suffix_width(hostname_t hn) +{ + assert(hn->suffix != NULL); + return (int) strlen(hn->suffix); +} + + +/* ----[ hostrange_t functions ]---- */ + +/* allocate a new hostrange object + */ +static hostrange_t hostrange_new(void) +{ + hostrange_t new = (hostrange_t) malloc(sizeof(*new)); + if (!new) + out_of_memory("hostrange create"); + return new; +} + +/* Create a hostrange_t containing a single host without a valid suffix + * hr->prefix will represent the entire hostname. + */ +static hostrange_t hostrange_create_single(const char *prefix) +{ + hostrange_t new; + + assert(prefix != NULL); + + if ((new = hostrange_new()) == NULL) + goto error1; + + if ((new->prefix = strdup(prefix)) == NULL) + goto error2; + + new->singlehost = 1; + new->lo = 0L; + new->hi = 0L; + new->width = 0; + + return new; + + error2: + free(new); + error1: + out_of_memory("hostrange create single"); +} + + +/* Create a hostrange object with a prefix, hi, lo, and format width + */ +static hostrange_t +hostrange_create(char *prefix, unsigned long lo, unsigned long hi, int width) +{ + hostrange_t new; + + assert(prefix != NULL); + + if ((new = hostrange_new()) == NULL) + goto error1; + + if ((new->prefix = strdup(prefix)) == NULL) + goto error2; + + new->lo = lo; + new->hi = hi; + new->width = width; + + new->singlehost = 0; + + return new; + + error2: + free(new); + error1: + out_of_memory("hostrange create"); +} + + +/* Return the number of hosts stored in the hostrange object + */ +static unsigned long hostrange_count(hostrange_t hr) +{ + assert(hr != NULL); + if (hr->singlehost) + return 1; + else + return hr->hi - hr->lo + 1; +} + +/* Copy a hostrange object + */ +static hostrange_t hostrange_copy(hostrange_t hr) +{ + assert(hr != NULL); + + if (hr->singlehost) + return hostrange_create_single(hr->prefix); + else + return hostrange_create(hr->prefix, hr->lo, hr->hi, + hr->width); +} + + +/* free memory allocated by the hostrange object + */ +static void hostrange_destroy(hostrange_t hr) +{ + if (hr == NULL) + return; + if (hr->prefix) + free(hr->prefix); + free(hr); +} + +/* hostrange_delete_host() deletes a specific host from the range. + * If the range is split into two, the greater range is returned, + * and `hi' of the lesser range is adjusted accordingly. If the + * highest or lowest host is deleted from a range, NULL is returned + * and the hostrange hr is adjusted properly. + */ +static hostrange_t hostrange_delete_host(hostrange_t hr, unsigned long n) +{ + hostrange_t new = NULL; + + assert(hr != NULL); + assert(n >= hr->lo && n <= hr->hi); + + if (n == hr->lo) + hr->lo++; + else if (n == hr->hi) + hr->hi--; + else { + if (!(new = hostrange_copy(hr))) + out_of_memory("hostrange copy"); + hr->hi = n - 1; + new->lo = n + 1; + } + + return new; +} + +/* hostrange_cmp() is used to sort hostrange objects. It will + * sort based on the following (in order): + * o result of strcmp on prefixes + * o if widths are compatible, then: + * sort based on lowest suffix in range + * else + * sort based on width */ +static int hostrange_cmp(hostrange_t h1, hostrange_t h2) +{ + int retval; + + assert(h1 != NULL); + assert(h2 != NULL); + + if ((retval = hostrange_prefix_cmp(h1, h2)) == 0) + retval = hostrange_width_combine(h1, h2) ? + h1->lo - h2->lo : h1->width - h2->width; + + return retval; +} + + +/* compare the prefixes of two hostrange objects. + * returns: + * < 0 if h1 prefix is less than h2 OR h1 == NULL. + * + * 0 if h1's prefix and h2's prefix match, + * UNLESS, either h1 or h2 (NOT both) do not have a valid suffix. + * + * > 0 if h1's prefix is greater than h2's OR h2 == NULL. */ +static int hostrange_prefix_cmp(hostrange_t h1, hostrange_t h2) +{ + int retval; + if (h1 == NULL) + return 1; + if (h2 == NULL) + return -1; + + retval = strcmp(h1->prefix, h2->prefix); + return retval == 0 ? h2->singlehost - h1->singlehost : retval; +} + +/* returns true if h1 and h2 would be included in the same bracketed hostlist. + * h1 and h2 will be in the same bracketed list iff: + * + * 1. h1 and h2 have same prefix + * 2. neither h1 nor h2 are singlet hosts (i.e. invalid suffix) + * + * (XXX: Should incompatible widths be placed in the same bracketed list? + * There's no good reason not to, except maybe aesthetics) + */ +static int hostrange_within_range(hostrange_t h1, hostrange_t h2) +{ + if (hostrange_prefix_cmp(h1, h2) == 0) + return h1->singlehost || h2->singlehost ? 0 : 1; + else + return 0; +} + + +/* compare two hostrange objects to determine if they are width + * compatible, returns: + * 1 if widths can safely be combined + * 0 if widths cannot be safely combined + */ +static int hostrange_width_combine(hostrange_t h0, hostrange_t h1) +{ + assert(h0 != NULL); + assert(h1 != NULL); + + return _width_equiv(h0->lo, &h0->width, h1->lo, &h1->width); +} + + +/* Return true if hostrange hr contains no hosts, i.e. hi < lo + */ +static int hostrange_empty(hostrange_t hr) +{ + assert(hr != NULL); + return ((hr->hi < hr->lo) || (hr->hi == (unsigned long) -1)); +} + +/* return the string representation of the last host in hostrange hr + * and remove that host from the range (i.e. decrement hi if possible) + * + * Returns NULL if malloc fails OR there are no more hosts left + */ +static char *hostrange_pop(hostrange_t hr) +{ + size_t size = 0; + char *host = NULL; + + assert(hr != NULL); + + if (hr->singlehost) { + hr->lo++; /* effectively set count == 0 */ + host = strdup(hr->prefix); + } else if (hostrange_count(hr) > 0) { + size = strlen(hr->prefix) + hr->width + 16; + if (!(host = (char *) malloc(size * sizeof(char)))) + out_of_memory("hostrange pop"); + snprintf(host, size, "%s%0*lu", hr->prefix, + hr->width, hr->hi--); + } + + return host; +} + +/* Same as hostrange_pop(), but remove host from start of range */ +static char *hostrange_shift(hostrange_t hr) +{ + size_t size = 0; + char *host = NULL; + + assert(hr != NULL); + + if (hr->singlehost) { + hr->lo++; + if (!(host = strdup(hr->prefix))) + out_of_memory("hostrange shift"); + } else if (hostrange_count(hr) > 0) { + size = strlen(hr->prefix) + hr->width + 16; + if (!(host = (char *) malloc(size * sizeof(char)))) + out_of_memory("hostrange shift"); + snprintf(host, size, "%s%0*lu", hr->prefix, + hr->width, hr->lo++); + } + + return host; +} + + +/* join two hostrange objects. + * + * returns: + * + * -1 if ranges do not overlap (including incompatible zero padding) + * 0 if ranges join perfectly + * >0 number of hosts that were duplicated in h1 and h2 + * + * h2 will be coalesced into h1 if rc >= 0 + * + * it is assumed that h1->lo <= h2->lo, i.e. hr1 <= hr2 + * + */ +static int hostrange_join(hostrange_t h1, hostrange_t h2) +{ + int duplicated = -1; + + assert(h1 != NULL); + assert(h2 != NULL); + assert(hostrange_cmp(h1, h2) <= 0); + + if (hostrange_prefix_cmp(h1, h2) == 0 && + hostrange_width_combine(h1, h2)) { + + if (h1->singlehost && h2->singlehost) { /* matching singlets */ + duplicated = 1; + } else if (h1->hi == h2->lo - 1) { /* perfect join */ + h1->hi = h2->hi; + duplicated = 0; + } else if (h1->hi >= h2->lo) { /* some duplication */ + if (h1->hi < h2->hi) { + duplicated = h1->hi - h2->lo + 1; + h1->hi = h2->hi; + } else + duplicated = hostrange_count(h2); + } + } + + return duplicated; +} + +/* hostrange intersect returns the intersection (common hosts) + * of hostrange objects h1 and h2. If there is no intersection, + * NULL is returned. + * + * It is assumed that h1 <= h2 (i.e. h1->lo <= h2->lo) + */ +static hostrange_t hostrange_intersect(hostrange_t h1, hostrange_t h2) +{ + hostrange_t new = NULL; + + assert(h1 != NULL); + assert(h2 != NULL); + + if (h1->singlehost || h2->singlehost) + return NULL; + + assert(hostrange_cmp(h1, h2) <= 0); + + if ((hostrange_prefix_cmp(h1, h2) == 0) + && (h1->hi > h2->lo) + && (hostrange_width_combine(h1, h2))) { + + if (!(new = hostrange_copy(h1))) + return NULL; + new->lo = h2->lo; + new->hi = h2->hi < h1->hi ? h2->hi : h1->hi; + } + + return new; +} + +/* return 1 if hostname hn is within the hostrange hr + * 0 if not. + */ +static int hostrange_hn_within(hostrange_t hr, hostname_t hn) +{ + int retval = 0; + + if (hr->singlehost && (strcmp(hn->hostname, hr->prefix) == 0)) + return 1; + + if (strcmp(hr->prefix, hn->prefix) == 0) { + if (!hostname_suffix_is_valid(hn)) { + if (hr->singlehost) + retval = 1; + } else if (hn->num <= hr->hi && hn->num >= hr->lo) { + int width = hostname_suffix_width(hn); + int num = hn->num; + retval = _width_equiv(hr->lo, &hr->width, num, &width); + } + } + return retval; +} + + +/* copy a string representation of the hostrange hr into buffer buf, + * writing at most n chars including NUL termination + */ +static size_t +hostrange_to_string(hostrange_t hr, size_t n, char *buf, char *separator) +{ + unsigned long i; + int truncated = 0; + int len = 0; + char sep = separator == NULL ? ',' : separator[0]; + + if (n == 0) + return 0; + + if (hr->singlehost) + return snprintf(buf, n, "%s", hr->prefix); + + for (i = hr->lo; i <= hr->hi; i++) { + size_t m = (n - len) <= n ? n - len : 0; /* check for < 0 */ + int ret = snprintf(buf + len, m, "%s%0*lu", + hr->prefix, hr->width, i); + if (ret < 0 || ret >= m) { + len = n; + truncated = 1; + break; + } + len+=ret; + buf[len++] = sep; + } + + if (truncated) { + buf[n-1] = '\0'; + return -1; + } else { + /* back up over final separator */ + buf[--len] = '\0'; + return len; + } +} + +/* Place the string representation of the numeric part of hostrange into buf + * writing at most n chars including NUL termination. + */ +static size_t hostrange_numstr(hostrange_t hr, size_t n, char *buf) +{ + int len = 0; + + assert(buf != NULL); + + if (hr->singlehost || n == 0) + return 0; + + len = snprintf(buf, n, "%0*lu", hr->width, hr->lo); + + if ((len >= 0) && (len < n) && (hr->lo < hr->hi)) { + int len2 = snprintf(buf+len, n-len, "-%0*lu", hr->width, hr->hi); + if (len2 < 0) + len = -1; + else + len += len2; + } + + return len; +} + + +/* ----[ hostlist functions ]---- */ + +/* Create a new hostlist object. + * Returns an empty hostlist, or NULL if memory allocation fails. + */ +static hostlist_t hostlist_new(void) +{ + int i; + hostlist_t new = (hostlist_t) malloc(sizeof(*new)); + if (!new) + goto fail1; + + assert(new->magic = HOSTLIST_MAGIC); + mutex_init(&new->mutex); + + new->hr = (hostrange_t *) malloc(HOSTLIST_CHUNK * sizeof(hostrange_t)); + if (!new->hr) + goto fail2; + + /* set entries in hostrange array to NULL */ + for (i = 0; i < HOSTLIST_CHUNK; i++) + new->hr[i] = NULL; + + new->size = HOSTLIST_CHUNK; + new->nranges = 0; + new->nhosts = 0; + new->ilist = NULL; + return new; + + fail2: + free(new); + fail1: + out_of_memory("hostlist_create"); +} + + +/* Resize the internal array used to store the list of hostrange objects. + * + * returns 1 for a successful resize, + * 0 if call to _realloc fails + * + * It is assumed that the caller has the hostlist hl locked + */ +static int hostlist_resize(hostlist_t hl, size_t newsize) +{ + int i; + size_t oldsize; + assert(hl != NULL); + assert(hl->magic == HOSTLIST_MAGIC); + oldsize = hl->size; + hl->size = newsize; + hl->hr = realloc((void *) hl->hr, hl->size*sizeof(hostrange_t)); + if (!(hl->hr)) + return 0; + + for (i = oldsize; i < newsize; i++) + hl->hr[i] = NULL; + + return 1; +} + +/* Resize hostlist by one HOSTLIST_CHUNK + * Assumes that hostlist hl is locked by caller + */ +static int hostlist_expand(hostlist_t hl) +{ + if (!hostlist_resize(hl, hl->size + HOSTLIST_CHUNK)) + return 0; + else + return 1; +} + +/* Push a hostrange object onto hostlist hl + * Returns the number of hosts successfully pushed onto hl + * or -1 if there was an error allocating memory + */ +static int hostlist_push_range(hostlist_t hl, hostrange_t hr) +{ + hostrange_t tail; + int retval; + + assert(hr != NULL); + LOCK_HOSTLIST(hl); + + tail = (hl->nranges > 0) ? hl->hr[hl->nranges-1] : hl->hr[0]; + + if (hl->size == hl->nranges && !hostlist_expand(hl)) + goto error; + + if (hl->nranges > 0 + && hostrange_prefix_cmp(tail, hr) == 0 + && tail->hi == hr->lo - 1 + && hostrange_width_combine(tail, hr)) { + tail->hi = hr->hi; + } else { + if ((hl->hr[hl->nranges++] = hostrange_copy(hr)) == NULL) + goto error; + } + + retval = hl->nhosts += hostrange_count(hr); + + UNLOCK_HOSTLIST(hl); + + return retval; + + error: + UNLOCK_HOSTLIST(hl); + return -1; +} + + + +/* Same as hostlist_push_range() above, but prefix, lo, hi, and width + * are passed as args + */ +static int +hostlist_push_hr(hostlist_t hl, char *prefix, unsigned long lo, + unsigned long hi, int width) +{ + hostrange_t hr = hostrange_create(prefix, lo, hi, width); + int retval = hostlist_push_range(hl, hr); + hostrange_destroy(hr); + return retval; +} + +/* Insert a range object hr into position n of the hostlist hl + * Assumes that hl->mutex is already held by calling process + */ +static int hostlist_insert_range(hostlist_t hl, hostrange_t hr, int n) +{ + int i; + hostrange_t tmp; + hostlist_iterator_t hli; + + assert(hl != NULL); + assert(hl->magic == HOSTLIST_MAGIC); + assert(hr != NULL); + + if (n > hl->nranges) + return 0; + + if (hl->size == hl->nranges && !hostlist_expand(hl)) + return 0; + + /* copy new hostrange into slot "n" in array */ + tmp = hl->hr[n]; + hl->hr[n] = hostrange_copy(hr); + + /* push remaining hostrange entries up */ + for (i = n + 1; i < hl->nranges + 1; i++) { + hostrange_t last = hl->hr[i]; + hl->hr[i] = tmp; + tmp = last; + } + hl->nranges++; + + /* adjust hostlist iterators if needed */ + for (hli = hl->ilist; hli; hli = hli->next) { + if (hli->idx >= n) + hli->hr = hli->hl->hr[++hli->idx]; + } + + return 1; +} + +/* Delete the range at position n in the range array + * Assumes the hostlist lock is already held. + */ +static void hostlist_delete_range(hostlist_t hl, int n) +{ + int i; + hostrange_t old; + + assert(hl != NULL); + assert(hl->magic == HOSTLIST_MAGIC); + assert(n < hl->nranges && n >= 0); + + old = hl->hr[n]; + for (i = n; i < hl->nranges - 1; i++) + hl->hr[i] = hl->hr[i + 1]; + hl->nranges--; + hl->hr[hl->nranges] = NULL; + hostlist_shift_iterators(hl, n, 0, 1); + + /* XXX caller responsible for adjusting nhosts */ + /* hl->nhosts -= hostrange_count(old) */ + + hostrange_destroy(old); +} + +#if WANT_RECKLESS_HOSTRANGE_EXPANSION + +/* The reckless hostrange expansion function. + * See comment in hostlist.h:hostlist_create() for more info on + * the different choices for hostlist notation. + */ +hostlist_t _hostlist_create(const char *hostlist, char *sep, char *r_op) +{ + char *str, *orig; + char *tok, *cur; + int high, low, fmt = 0; + char prefix[256] = ""; + int pos = 0; + int error = 0; + char range_op = r_op[0];/* XXX support > 1 char range ops in future? */ + + hostlist_t new = hostlist_new(); + + orig = str = strdup(hostlist); + + /* return an empty list if an empty string was passed in */ + if (str == NULL || strlen(str) == 0) + goto done; + + /* Use hostlist_create_bracketed if we see "[" */ + if (strchr(str, '[') != NULL) + return _hostlist_create_bracketed(hostlist, sep, r_op); + + while ((tok = _next_tok(sep, &str)) != NULL) { + + /* save the current string for error messages */ + cur = tok; + + high = low = 0; + + /* find end of alpha part + * do this by finding last occurence of range_op in str */ + pos = strlen(tok) - 1; + if (strstr(tok, r_op) != '\0') { + while (pos >= 0 && (char) tok[pos] != range_op) + pos--; + } + + /* now back up past any digits */ + while (pos >= 0 && isdigit((char) tok[--pos])) {;} + + /* Check for valid x-y range (x must be a digit) + * Reset pos if the range is not valid */ + if (!isdigit((char) tok[++pos])) + pos = strlen(tok) - 1; + + /* create prefix string + * if prefix will be zero length, but prefix already exists + * use the previous prefix and fmt + */ + if ((pos > 0) || (prefix[0] == '\0')) { + memcpy(prefix, tok, (size_t) pos * sizeof(char)); + prefix[pos] = '\0'; + + /* push pointer past prefix */ + tok += pos; + + /* count number of digits for ouput fmt */ + for (fmt = 0; isdigit(tok[fmt]); ++fmt) {;} + + if (fmt == 0) + error = 1; + + } else + tok += pos; + + /* get lower bound */ + low = strtoul(tok, (char **) &tok, 10); + + if (*tok == range_op) { /* now get range upper bound */ + /* push pointer past range op */ + ++tok; + + /* find length of alpha part */ + for (pos = 0; tok[pos] && !isdigit(tok[pos]); ++pos) {;} + + /* alpha part must match prefix or error + * this could mean we've got something like "rtr1-a2" + * so just record an error + */ + if (pos > 0) { + if (pos != strlen(prefix) || + strncmp(prefix, tok, pos) != 0) + error = 1; + } + + if (*tok != '\0') + tok += pos; + + /* make sure we have digits to the end */ + for (pos = 0; tok[pos] && isdigit((char) tok[pos]); ++pos) {;} + + if (pos > 0) { /* we have digits to process */ + high = strtoul(tok, (char **) &tok, 10); + } else { /* bad boy, no digits */ + error = 1; + } + + if ((low > high) || (high - low > MAX_RANGE)) + error = 1; + + } else { /* single value */ + high = 0; /* special case, ugh. */ + } + + /* error if: + * 1. we are not at end of string + * 2. upper bound equals lower bound + */ + if (*tok != '\0' || high == low) + error = 1; + + if (error) { /* assume this is not a range on any error */ + hostlist_push_host(new, cur); + } else { + if (high < low) + high = low; + hostlist_push_hr(new, prefix, low, high, fmt); + } + + error = 0; + } + + done: + free(orig); + + return new; +} + +#else /* !WANT_RECKLESS_HOSTRANGE_EXPANSION */ + +hostlist_t _hostlist_create(const char *hostlist, char *sep, char *r_op) +{ + return _hostlist_create_bracketed(hostlist, sep, r_op); +} + +#endif /* WANT_RECKLESS_HOSTRANGE_EXPANSION */ + +struct _range { + unsigned long lo, hi; + int width; +}; + +/* Grab a single range from str + * returns 1 if str contained a valid number or range, + * 0 if conversion of str to a range failed. + */ +static int _parse_single_range(const char *str, struct _range *range) +{ + char *p, *q; + char *orig = strdup(str); + if (!orig) + seterrno_ret(ENOMEM, 0); + + if ((p = strchr(str, '-'))) { + *p++ = '\0'; + if (*p == '-') /* do NOT allow negative numbers */ + goto error; + } + range->lo = strtoul(str, &q, 10); + if (q == str) + goto error; + + range->hi = (p && *p) ? strtoul(p, &q, 10) : range->lo; + + if (q == p || *q != '\0') + goto error; + + if (range->lo > range->hi) + goto error; + + if (range->hi - range->lo + 1 > MAX_RANGE ) { + _error(__FILE__, __LINE__, "Too many hosts in range `%s'", orig); + free(orig); + seterrno_ret(ERANGE, 0); + } + + free(orig); + range->width = strlen(str); + return 1; + + error: + _error(__FILE__, __LINE__, "Invalid range: `%s'", orig); + free(orig); + seterrno_ret(EINVAL, 0); +} + + +/* + * Convert 'str' containing comma separated digits and ranges into an array + * of struct _range types (max 'len' elements). + * + * Return number of ranges created, or -1 on error. + */ +static int _parse_range_list(char *str, struct _range *ranges, int len) +{ + char *p; + int count = 0; + + while (str) { + if (count == len) + return -1; + if ((p = strchr(str, ','))) + *p++ = '\0'; + if (!_parse_single_range(str, &ranges[count++])) + return -1; + str = p; + } + return count; +} + +static void +_push_range_list(hostlist_t hl, char *pfx, struct _range *rng, + int n) +{ + int i; + for (i = 0; i < n; i++) { + hostlist_push_hr(hl, pfx, rng->lo, rng->hi, rng->width); + rng++; + } +} + +static void +_push_range_list_with_suffix(hostlist_t hl, char *pfx, char *sfx, + struct _range *rng, int n) +{ + int i; + unsigned long j; + for (i = 0; i < n; i++) { + for (j = rng->lo; j <= rng->hi; j++) { + char host[4096]; + hostrange_t hr; + snprintf (host, 4096, "%s%0*lu%s", pfx, rng->width, j, sfx); + hr = hostrange_create_single (host); + hostlist_push_range (hl, hr); + /* + * hr is copied in hostlist_push_range. Need to free here. + */ + hostrange_destroy (hr); + } + rng++; + } +} + +/* + * Create a hostlist from a string with brackets '[' ']' to aid + * detection of ranges and compressed lists + */ +static hostlist_t +_hostlist_create_bracketed(const char *hostlist, char *sep, char *r_op) +{ + hostlist_t new = hostlist_new(); + struct _range ranges[MAX_RANGES]; + int nr, err; + char *p, *tok, *str, *orig; + char cur_tok[1024]; + + if (hostlist == NULL) + return new; + + if (!(orig = str = strdup(hostlist))) { + hostlist_destroy(new); + return NULL; + } + + while ((tok = _next_tok(sep, &str)) != NULL) { + strncpy(cur_tok, tok, 1024); + + if ((p = strchr(tok, '[')) != NULL) { + char *q, *prefix = tok; + *p++ = '\0'; + + if ((q = strchr(p, ']'))) { + *q = '\0'; + nr = _parse_range_list(p, ranges, MAX_RANGES); + if (nr < 0) + goto error; + + if (*(++q) != '\0') + _push_range_list_with_suffix (new, prefix, q, ranges, nr); + else + _push_range_list(new, prefix, ranges, nr); + + + } else + hostlist_push_host(new, cur_tok); + + } else + hostlist_push_host(new, cur_tok); + } + + free(orig); + return new; + + error: + err = errno; + hostlist_destroy(new); + free(orig); + seterrno_ret(err, NULL); +} + + + +hostlist_t hostlist_create(const char *str) +{ + return _hostlist_create(str, "\t, ", "-"); +} + + +hostlist_t hostlist_copy(const hostlist_t hl) +{ + int i; + hostlist_t new; + + if (hl == NULL) + return NULL; + + LOCK_HOSTLIST(hl); + if (!(new = hostlist_new())) + goto done; + + new->nranges = hl->nranges; + new->nhosts = hl->nhosts; + if (new->nranges > new->size) + hostlist_resize(new, new->nranges); + + for (i = 0; i < hl->nranges; i++) + new->hr[i] = hostrange_copy(hl->hr[i]); + + done: + UNLOCK_HOSTLIST(hl); + return new; +} + + +void hostlist_destroy(hostlist_t hl) +{ + int i; + if (hl == NULL) + return; + LOCK_HOSTLIST(hl); + while (hl->ilist) { + mutex_unlock(&hl->mutex); + hostlist_iterator_destroy(hl->ilist); + mutex_lock(&hl->mutex); + } + for (i = 0; i < hl->nranges; i++) + hostrange_destroy(hl->hr[i]); + free(hl->hr); + assert(hl->magic = 0x1); + UNLOCK_HOSTLIST(hl); + mutex_destroy(&hl->mutex); + free(hl); +} + + +int hostlist_push(hostlist_t hl, const char *hosts) +{ + hostlist_t new; + int retval; + if (hosts == NULL) + return 0; + new = hostlist_create(hosts); + if (!new) + return 0; + mutex_lock(&new->mutex); + retval = new->nhosts; + mutex_unlock(&new->mutex); + hostlist_push_list(hl, new); + hostlist_destroy(new); + return retval; +} + +int hostlist_push_host(hostlist_t hl, const char *str) +{ + hostrange_t hr; + hostname_t hn; + + if (str == NULL) + return 0; + + hn = hostname_create(str); + + if (hostname_suffix_is_valid(hn)) { + hr = hostrange_create(hn->prefix, hn->num, hn->num, + hostname_suffix_width(hn)); + } else + hr = hostrange_create_single(str); + + hostlist_push_range(hl, hr); + + hostrange_destroy(hr); + hostname_destroy(hn); + + return 1; +} + +int hostlist_push_list(hostlist_t h1, hostlist_t h2) +{ + int i, n = 0; + + if (h2 == NULL) + return 0; + + LOCK_HOSTLIST(h2); + + for (i = 0; i < h2->nranges; i++) + n += hostlist_push_range(h1, h2->hr[i]); + + UNLOCK_HOSTLIST(h2); + + return n; +} + + +char *hostlist_pop(hostlist_t hl) +{ + char *host = NULL; + + LOCK_HOSTLIST(hl); + if (hl->nhosts > 0) { + hostrange_t hr = hl->hr[hl->nranges - 1]; + host = hostrange_pop(hr); + hl->nhosts--; + if (hostrange_empty(hr)) { + hostrange_destroy(hl->hr[--hl->nranges]); + hl->hr[hl->nranges] = NULL; + } + } + UNLOCK_HOSTLIST(hl); + return host; +} + +/* find all iterators affected by a shift (or deletion) at + * hl->hr[idx], depth, with the deletion of n ranges */ +static void +hostlist_shift_iterators(hostlist_t hl, int idx, int depth, int n) +{ + hostlist_iterator_t i; + for (i = hl->ilist; i; i = i->next) { + if (n == 0) { + if (i->idx == idx && i->depth >= depth) + i->depth = i->depth > -1 ? i->depth - 1 : -1; + } else { + if (i->idx >= idx) { + if ((i->idx -= n) >= 0) + i->hr = i->hl->hr[i->idx]; + else + hostlist_iterator_reset(i); + } + } + } +} + +char *hostlist_shift(hostlist_t hl) +{ + char *host = NULL; + + LOCK_HOSTLIST(hl); + + if (hl->nhosts > 0) { + hostrange_t hr = hl->hr[0]; + + host = hostrange_shift(hr); + hl->nhosts--; + + if (hostrange_empty(hr)) { + hostlist_delete_range(hl, 0); + /* hl->nranges--; */ + } else + hostlist_shift_iterators(hl, 0, 0, 0); + } + + UNLOCK_HOSTLIST(hl); + + return host; +} + + +char *hostlist_pop_range(hostlist_t hl) +{ + int i; + char buf[MAXHOSTRANGELEN + 1]; + hostlist_t hltmp; + hostrange_t tail; + + LOCK_HOSTLIST(hl); + if (hl->nranges < 1 || !(hltmp = hostlist_new())) { + UNLOCK_HOSTLIST(hl); + return NULL; + } + + i = hl->nranges - 2; + tail = hl->hr[hl->nranges - 1]; + while (i >= 0 && hostrange_within_range(tail, hl->hr[i])) + i--; + + for (i++; i < hl->nranges; i++) { + hostlist_push_range(hltmp, hl->hr[i]); + hostrange_destroy(hl->hr[i]); + hl->hr[i] = NULL; + } + hl->nhosts -= hltmp->nhosts; + hl->nranges -= hltmp->nranges; + + UNLOCK_HOSTLIST(hl); + hostlist_ranged_string(hltmp, MAXHOSTRANGELEN, buf); + hostlist_destroy(hltmp); + return strdup(buf); +} + + +char *hostlist_shift_range(hostlist_t hl) +{ + int i; + char buf[1024]; + hostlist_t hltmp = hostlist_new(); + if (!hltmp) + return NULL; + + LOCK_HOSTLIST(hl); + + if (hl->nranges == 0) { + hostlist_destroy(hltmp); + UNLOCK_HOSTLIST(hl); + return NULL; + } + + i = 0; + do { + hostlist_push_range(hltmp, hl->hr[i]); + hostrange_destroy(hl->hr[i]); + } while ( (++i < hl->nranges) + && hostrange_within_range(hltmp->hr[0], hl->hr[i]) ); + + hostlist_shift_iterators(hl, i, 0, hltmp->nranges); + + /* shift rest of ranges back in hl */ + for (; i < hl->nranges; i++) { + hl->hr[i - hltmp->nranges] = hl->hr[i]; + hl->hr[i] = NULL; + } + hl->nhosts -= hltmp->nhosts; + hl->nranges -= hltmp->nranges; + + UNLOCK_HOSTLIST(hl); + + hostlist_ranged_string(hltmp, 1024, buf); + hostlist_destroy(hltmp); + + return strdup(buf); +} + +/* XXX: Note: efficiency improvements needed */ +int hostlist_delete(hostlist_t hl, const char *hosts) +{ + int n = 0; + char *hostname = NULL; + hostlist_t hltmp; + + if (!(hltmp = hostlist_create(hosts))) + seterrno_ret(EINVAL, 0); + + while ((hostname = hostlist_pop(hltmp)) != NULL) { + n += hostlist_delete_host(hl, hostname); + free(hostname); + } + hostlist_destroy(hltmp); + + return n; +} + + +/* XXX watch out! poor implementation follows! (fix it at some point) */ +int hostlist_delete_host(hostlist_t hl, const char *hostname) +{ + int n = hostlist_find(hl, hostname); + if (n >= 0) + hostlist_delete_nth(hl, n); + return n >= 0 ? 1 : 0; +} + + +static char * +_hostrange_string(hostrange_t hr, int depth) +{ + char buf[MAXHOSTNAMELEN + 16]; + int len = snprintf(buf, MAXHOSTNAMELEN + 15, "%s", hr->prefix); + + if (!hr->singlehost) + snprintf(buf+len, MAXHOSTNAMELEN+15 - len, "%0*lu", + hr->width, hr->lo + depth); + return strdup(buf); +} + +char * hostlist_nth(hostlist_t hl, int n) +{ + char *host = NULL; + int i, count; + + LOCK_HOSTLIST(hl); + count = 0; + for (i = 0; i < hl->nranges; i++) { + int num_in_range = hostrange_count(hl->hr[i]); + + if (n <= (num_in_range - 1 + count)) { + host = _hostrange_string(hl->hr[i], n - count); + break; + } else + count += num_in_range; + } + + UNLOCK_HOSTLIST(hl); + + return host; +} + + +int hostlist_delete_nth(hostlist_t hl, int n) +{ + int i, count; + + LOCK_HOSTLIST(hl); + assert(n >= 0 && n <= hl->nhosts); + + count = 0; + + for (i = 0; i < hl->nranges; i++) { + int num_in_range = hostrange_count(hl->hr[i]); + hostrange_t hr = hl->hr[i]; + + if (n <= (num_in_range - 1 + count)) { + unsigned long num = hr->lo + n - count; + hostrange_t new; + + if (hr->singlehost) { /* this wasn't a range */ + hostlist_delete_range(hl, i); + } else if ((new = hostrange_delete_host(hr, num))) { + hostlist_insert_range(hl, new, i + 1); + hostrange_destroy(new); + } else if (hostrange_empty(hr)) + hostlist_delete_range(hl, i); + + goto done; + } else + count += num_in_range; + + } + + done: + UNLOCK_HOSTLIST(hl); + hl->nhosts--; + return 1; +} + +int hostlist_count(hostlist_t hl) +{ + int retval; + LOCK_HOSTLIST(hl); + retval = hl->nhosts; + UNLOCK_HOSTLIST(hl); + return retval; +} + +int hostlist_find(hostlist_t hl, const char *hostname) +{ + int i, count, ret = -1; + hostname_t hn; + + if (!hostname) + return -1; + + hn = hostname_create(hostname); + + LOCK_HOSTLIST(hl); + + for (i = 0, count = 0; i < hl->nranges; i++) { + if (hostrange_hn_within(hl->hr[i], hn)) { + if (hostname_suffix_is_valid(hn) && !hl->hr[i]->singlehost) + ret = count + hn->num - hl->hr[i]->lo; + else + ret = count; + goto done; + } else + count += hostrange_count(hl->hr[i]); + } + + done: + UNLOCK_HOSTLIST(hl); + hostname_destroy(hn); + return ret; +} + +/* hostrange compare with void * arguments to allow use with + * libc qsort() + */ +int _cmp(const void *hr1, const void *hr2) +{ + hostrange_t *h1 = (hostrange_t *) hr1; + hostrange_t *h2 = (hostrange_t *) hr2; + return hostrange_cmp((hostrange_t) * h1, (hostrange_t) * h2); +} + + +void hostlist_sort(hostlist_t hl) +{ + hostlist_iterator_t i; + LOCK_HOSTLIST(hl); + + if (hl->nranges <= 1) { + UNLOCK_HOSTLIST(hl); + return; + } + + qsort(hl->hr, hl->nranges, sizeof(hostrange_t), &_cmp); + + /* reset all iterators */ + for (i = hl->ilist; i; i = i->next) + hostlist_iterator_reset(i); + + UNLOCK_HOSTLIST(hl); + + hostlist_coalesce(hl); + +} + + +/* search through hostlist for ranges that can be collapsed + * does =not= delete any hosts + */ +static void hostlist_collapse(hostlist_t hl) +{ + int i; + + LOCK_HOSTLIST(hl); + for (i = hl->nranges - 1; i > 0; i--) { + hostrange_t hprev = hl->hr[i - 1]; + hostrange_t hnext = hl->hr[i]; + + if (hostrange_prefix_cmp(hprev, hnext) == 0 && + hprev->hi == hnext->lo - 1 && + hostrange_width_combine(hprev, hnext)) { + hprev->hi = hnext->hi; + hostlist_delete_range(hl, i); + } + } + UNLOCK_HOSTLIST(hl); +} + +/* search through hostlist (hl) for intersecting ranges + * split up duplicates and coalesce ranges where possible + */ +static void hostlist_coalesce(hostlist_t hl) +{ + int i, j; + hostrange_t new; + + LOCK_HOSTLIST(hl); + + for (i = hl->nranges - 1; i > 0; i--) { + + new = hostrange_intersect(hl->hr[i - 1], hl->hr[i]); + + if (new) { + hostrange_t hprev = hl->hr[i - 1]; + hostrange_t hnext = hl->hr[i]; + j = i; + + if (new->hi < hprev->hi) + hnext->hi = hprev->hi; + + hprev->hi = new->lo; + hnext->lo = new->hi; + + if (hostrange_empty(hprev)) + hostlist_delete_range(hl, i); + + while (new->lo <= new->hi) { + hostrange_t hr = hostrange_create( new->prefix, + new->lo, new->lo, + new->width ); + + if (new->lo > hprev->hi) + hostlist_insert_range(hl, hr, j++); + + if (new->lo < hnext->lo) + hostlist_insert_range(hl, hr, j++); + + hostrange_destroy(hr); + + new->lo++; + } + i = hl->nranges; + hostrange_destroy(new); + } + } + UNLOCK_HOSTLIST(hl); + + hostlist_collapse(hl); + +} + +/* attempt to join ranges at loc and loc-1 in a hostlist */ +/* delete duplicates, return the number of hosts deleted */ +/* assumes that the hostlist hl has been locked by caller */ +/* returns -1 if no range join occurred */ +static int _attempt_range_join(hostlist_t hl, int loc) +{ + int ndup; + assert(hl != NULL); + assert(hl->magic == HOSTLIST_MAGIC); + assert(loc > 0); + assert(loc < hl->nranges); + ndup = hostrange_join(hl->hr[loc - 1], hl->hr[loc]); + if (ndup >= 0) { + hostlist_delete_range(hl, loc); + hl->nhosts -= ndup; + } + return ndup; +} + +void hostlist_uniq(hostlist_t hl) +{ + int i = 1; + hostlist_iterator_t hli; + LOCK_HOSTLIST(hl); + if (hl->nranges <= 1) { + UNLOCK_HOSTLIST(hl); + return; + } + qsort(hl->hr, hl->nranges, sizeof(hostrange_t), &_cmp); + + while (i < hl->nranges) { + if (_attempt_range_join(hl, i) < 0) /* No range join occurred */ + i++; + } + + /* reset all iterators */ + for (hli = hl->ilist; hli; hli = hli->next) + hostlist_iterator_reset(hli); + + UNLOCK_HOSTLIST(hl); +} + + +size_t hostlist_deranged_string(hostlist_t hl, size_t n, char *buf) +{ + int i; + int len = 0; + int truncated = 0; + + LOCK_HOSTLIST(hl); + for (i = 0; i < hl->nranges; i++) { + size_t m = (n - len) <= n ? n - len : 0; + int ret = hostrange_to_string(hl->hr[i], m, buf + len, ","); + if (ret < 0 || ret > m) { + len = n; + truncated = 1; + break; + } + len+=ret; + buf[len++] = ','; + } + UNLOCK_HOSTLIST(hl); + + buf[len > 0 ? --len : 0] = '\0'; + if (len == n) + truncated = 1; + + return truncated ? -1 : len; +} + +/* return true if a bracket is needed for the range at i in hostlist hl */ +static int _is_bracket_needed(hostlist_t hl, int i) +{ + hostrange_t h1 = hl->hr[i]; + hostrange_t h2 = i < hl->nranges - 1 ? hl->hr[i + 1] : NULL; + return hostrange_count(h1) > 1 || hostrange_within_range(h1, h2); +} + +/* write the next bracketed hostlist, i.e. prefix[n-m,k,...] + * into buf, writing at most n chars including the terminating '\0' + * + * leaves start pointing to one past last range object in bracketed list, + * and returns the number of bytes written into buf. + * + * Assumes hostlist is locked. + */ +static int +_get_bracketed_list(hostlist_t hl, int *start, const size_t n, char *buf) +{ + hostrange_t *hr = hl->hr; + int i = *start; + int m, len = 0; + int bracket_needed = _is_bracket_needed(hl, i); + + len = snprintf(buf, n, "%s", hr[i]->prefix); + + if ((len < 0) || (len > n)) + return n; /* truncated, buffer filled */ + + if (bracket_needed && len < n && len >= 0) + buf[len++] = '['; + + do { + m = (n - len) <= n ? n - len : 0; + len += hostrange_numstr(hr[i], m, buf + len); + if (len >= n) + break; + if (bracket_needed) /* Only need commas inside brackets */ + buf[len++] = ','; + } while (++i < hl->nranges && hostrange_within_range(hr[i], hr[i-1])); + + if (bracket_needed && len < n && len > 0) { + + /* Add trailing bracket (change trailing "," from above to "]" */ + buf[len - 1] = ']'; + + /* NUL terminate for safety, but do not add terminator to len */ + buf[len] = '\0'; + + } else if (len >= n) { + if (n > 0) + buf[n-1] = '\0'; + + } else { + /* If len is > 0, NUL terminate (but do not add to len) */ + buf[len > 0 ? len : 0] = '\0'; + } + + *start = i; + return len; +} + +size_t hostlist_ranged_string(hostlist_t hl, size_t n, char *buf) +{ + int i = 0; + int len = 0; + int truncated = 0; + + LOCK_HOSTLIST(hl); + while (i < hl->nranges && len < n) { + len += _get_bracketed_list(hl, &i, n - len, buf + len); + if ((len > 0) && (len < n) && (i < hl->nranges)) + buf[len++] = ','; + } + UNLOCK_HOSTLIST(hl); + + /* NUL terminate */ + if (len >= n) { + truncated = 1; + if (n > 0) + buf[n-1] = '\0'; + } else + buf[len > 0 ? len : 0] = '\0'; + + return truncated ? -1 : len; +} + +/* ----[ hostlist iterator functions ]---- */ + +static hostlist_iterator_t hostlist_iterator_new(void) +{ + hostlist_iterator_t i = (hostlist_iterator_t) malloc(sizeof(*i)); + if (!i) + return NULL; + i->hl = NULL; + i->hr = NULL; + i->idx = 0; + i->depth = -1; + i->next = i; + assert(i->magic = HOSTLIST_MAGIC); + return i; +} + +hostlist_iterator_t hostlist_iterator_create(hostlist_t hl) +{ + hostlist_iterator_t i; + + if (!(i = hostlist_iterator_new())) + out_of_memory("hostlist_iterator_create"); + + LOCK_HOSTLIST(hl); + i->hl = hl; + i->hr = hl->hr[0]; + i->next = hl->ilist; + hl->ilist = i; + UNLOCK_HOSTLIST(hl); + return i; +} + +hostlist_iterator_t hostset_iterator_create(hostset_t set) +{ + return hostlist_iterator_create(set->hl); +} + +void hostlist_iterator_reset(hostlist_iterator_t i) +{ + assert(i != NULL); + assert(i->magic == HOSTLIST_MAGIC); + i->idx = 0; + i->hr = i->hl->hr[0]; + i->depth = -1; + return; +} + +void hostlist_iterator_destroy(hostlist_iterator_t i) +{ + hostlist_iterator_t *pi; + if (i == NULL) + return; + assert(i != NULL); + assert(i->magic == HOSTLIST_MAGIC); + LOCK_HOSTLIST(i->hl); + for (pi = &i->hl->ilist; *pi; pi = &(*pi)->next) { + assert((*pi)->magic == HOSTLIST_MAGIC); + if (*pi == i) { + *pi = (*pi)->next; + break; + } + } + UNLOCK_HOSTLIST(i->hl); + assert(i->magic = 0x1); + free(i); +} + +static void _iterator_advance(hostlist_iterator_t i) +{ + assert(i != NULL); + assert(i->magic == HOSTLIST_MAGIC); + if (i->idx > i->hl->nranges - 1) + return; + if (++(i->depth) > (i->hr->hi - i->hr->lo)) { + i->depth = 0; + i->hr = i->hl->hr[++i->idx]; + } +} + +/* advance iterator to end of current range (meaning within "[" "]") + * i.e. advance iterator past all range objects that could be represented + * in on bracketed hostlist. + */ +static void _iterator_advance_range(hostlist_iterator_t i) +{ + int nr, j; + hostrange_t *hr; + assert(i != NULL); + assert(i->magic == HOSTLIST_MAGIC); + + nr = i->hl->nranges; + hr = i->hl->hr; + j = i->idx; + if (++i->depth > 0) { + while (++j < nr && hostrange_within_range(i->hr, hr[j])) {;} + i->idx = j; + i->hr = i->hl->hr[i->idx]; + i->depth = 0; + } +} + +char *hostlist_next(hostlist_iterator_t i) +{ + char *buf = NULL; + char suffix[16]; + int len = 0; + assert(i != NULL); + assert(i->magic == HOSTLIST_MAGIC); + LOCK_HOSTLIST(i->hl); + _iterator_advance(i); + + if (i->idx > i->hl->nranges - 1) { + UNLOCK_HOSTLIST(i->hl); + return NULL; + } + + suffix[0] = '\0'; + + if (!i->hr->singlehost) + snprintf (suffix, 15, "%0*lu", i->hr->width, i->hr->lo + i->depth); + + len = strlen (i->hr->prefix) + strlen (suffix) + 1; + if (!(buf = malloc (len))) + out_of_memory("hostlist_next"); + + buf[0] = '\0'; + strcat (buf, i->hr->prefix); + strcat (buf, suffix); + + UNLOCK_HOSTLIST(i->hl); + return (buf); +} + +char *hostlist_next_range(hostlist_iterator_t i) +{ + char buf[MAXHOSTRANGELEN + 1]; + int j; + + assert(i != NULL); + assert(i->magic == HOSTLIST_MAGIC); + LOCK_HOSTLIST(i->hl); + + _iterator_advance_range(i); + + if (i->idx > i->hl->nranges - 1) { + UNLOCK_HOSTLIST(i->hl); + return NULL; + } + + j = i->idx; + _get_bracketed_list(i->hl, &j, MAXHOSTRANGELEN, buf); + + UNLOCK_HOSTLIST(i->hl); + + return strdup(buf); +} + +int hostlist_remove(hostlist_iterator_t i) +{ + hostrange_t new; + assert(i != NULL); + assert(i->magic == HOSTLIST_MAGIC); + LOCK_HOSTLIST(i->hl); + new = hostrange_delete_host(i->hr, i->hr->lo + i->depth); + if (new) { + hostlist_insert_range(i->hl, new, i->idx + 1); + hostrange_destroy(new); + i->hr = i->hl->hr[++i->idx]; + i->depth = -1; + } else if (hostrange_empty(i->hr)) { + hostlist_delete_range(i->hl, i->idx); + } else + i->depth--; + + i->hl->nhosts--; + UNLOCK_HOSTLIST(i->hl); + + return 1; +} + +/* ----[ hostset functions ]---- */ + +hostset_t hostset_create(const char *hostlist) +{ + hostset_t new; + + if (!(new = (hostset_t) malloc(sizeof(*new)))) + goto error1; + + if (!(new->hl = hostlist_create(hostlist))) + goto error2; + + hostlist_uniq(new->hl); + return new; + + error2: + free(new); + error1: + return NULL; +} + +hostset_t hostset_copy(const hostset_t set) +{ + hostset_t new; + if (!(new = (hostset_t) malloc(sizeof(*new)))) + goto error1; + + if (!(new->hl = hostlist_copy(set->hl))) + goto error2; + + return new; + error2: + free(new); + error1: + return NULL; +} + +void hostset_destroy(hostset_t set) +{ + if (set == NULL) + return; + hostlist_destroy(set->hl); + free(set); +} + +/* inserts a single range object into a hostset + * Assumes that the set->hl lock is already held + * Updates hl->nhosts + */ +static int hostset_insert_range(hostset_t set, hostrange_t hr) +{ + int i = 0; + int inserted = 0; + int nhosts = 0; + int ndups = 0; + hostlist_t hl; + + hl = set->hl; + + if (hl->size == hl->nranges && !hostlist_expand(hl)) + return 0; + + nhosts = hostrange_count(hr); + + for (i = 0; i < hl->nranges; i++) { + if (hostrange_cmp(hr, hl->hr[i]) <= 0) { + + if ((ndups = hostrange_join(hr, hl->hr[i])) >= 0) + hostlist_delete_range(hl, i); + else if (ndups < 0) + ndups = 0; + + hostlist_insert_range(hl, hr, i); + + /* now attempt to join hr[i] and hr[i-1] */ + if (i > 0) { + int m; + if ((m = _attempt_range_join(hl, i)) > 0) + ndups += m; + } + hl->nhosts += nhosts - ndups; + inserted = 1; + break; + } + } + + if (inserted == 0) { + hl->hr[hl->nranges++] = hostrange_copy(hr); + hl->nhosts += nhosts; + if (hl->nranges > 1) { + if ((ndups = _attempt_range_join(hl, hl->nranges - 1)) <= 0) + ndups = 0; + } + } + + /* + * Return the number of unique hosts inserted + */ + return nhosts - ndups; +} + +int hostset_insert(hostset_t set, const char *hosts) +{ + int i, n = 0; + hostlist_t hl = hostlist_create(hosts); + if (!hl) + return 0; + + hostlist_uniq(hl); + LOCK_HOSTLIST(set->hl); + for (i = 0; i < hl->nranges; i++) + n += hostset_insert_range(set, hl->hr[i]); + UNLOCK_HOSTLIST(set->hl); + hostlist_destroy(hl); + return n; +} + + +/* linear search through N ranges for hostname "host" + * */ +static int hostset_find_host(hostset_t set, const char *host) +{ + int i; + int retval = 0; + hostname_t hn; + LOCK_HOSTLIST(set->hl); + hn = hostname_create(host); + for (i = 0; i < set->hl->nranges; i++) { + if (hostrange_hn_within(set->hl->hr[i], hn)) { + retval = 1; + goto done; + } + } + done: + UNLOCK_HOSTLIST(set->hl); + hostname_destroy(hn); + return retval; +} + +int hostset_within(hostset_t set, const char *hosts) +{ + int nhosts, nfound; + hostlist_t hl; + char *hostname; + + assert(set->hl->magic == HOSTLIST_MAGIC); + + hl = hostlist_create(hosts); + nhosts = hostlist_count(hl); + nfound = 0; + + while ((hostname = hostlist_pop(hl)) != NULL) { + nfound += hostset_find_host(set, hostname); + free(hostname); + } + + hostlist_destroy(hl); + + return (nhosts == nfound); +} + +int hostset_delete(hostset_t set, const char *hosts) +{ + return hostlist_delete(set->hl, hosts); +} + +int hostset_delete_host(hostset_t set, const char *hostname) +{ + return hostlist_delete_host(set->hl, hostname); +} + +char *hostset_shift(hostset_t set) +{ + return hostlist_shift(set->hl); +} + +char *hostset_pop(hostset_t set) +{ + return hostlist_pop(set->hl); +} + +char *hostset_shift_range(hostset_t set) +{ + return hostlist_shift_range(set->hl); +} + +char *hostset_pop_range(hostset_t set) +{ + return hostlist_pop_range(set->hl); +} + +int hostset_count(hostset_t set) +{ + return hostlist_count(set->hl); +} + +size_t hostset_ranged_string(hostset_t set, size_t n, char *buf) +{ + return hostlist_ranged_string(set->hl, n, buf); +} + +size_t hostset_deranged_string(hostset_t set, size_t n, char *buf) +{ + return hostlist_deranged_string(set->hl, n, buf); +} + +#if TEST_MAIN + +int hostlist_nranges(hostlist_t hl) +{ + return hl->nranges; +} + +int hostset_nranges(hostset_t set) +{ + return set->hl->nranges; +} + +/* test iterator functionality on the list of hosts represented + * by list + */ +int iterator_test(char *list) +{ + int j; + char buf[1024]; + hostlist_t hl = hostlist_create(list); + hostset_t set = hostset_create(list); + + hostlist_iterator_t i = hostlist_iterator_create(hl); + hostlist_iterator_t seti = hostset_iterator_create(set); + hostlist_iterator_t i2 = hostlist_iterator_create(hl); + char *host; + + + hostlist_ranged_string(hl, 1024, buf); + printf("iterator_test: hl = `%s' passed in `%s'\n", buf, list); + host = hostlist_next(i); + printf("first host in list hl = `%s'\n", host); + free(host); + + /* forge ahead three hosts with i2 */ + for (j = 0; j < 4; j++) { + host = hostlist_next(i2); + free(host); + } + + host = hostlist_shift(hl); + printf("result of shift(hl) = `%s'\n", host); + free(host); + host = hostlist_next(i); + printf("next host in list hl = `%s'\n", host); + free(host); + host = hostlist_next(i2); + printf("next host for i2 = `%s'\n", host); + free(host); + + hostlist_iterator_destroy(i); + + hostlist_destroy(hl); + hostset_destroy(set); + return 1; +} + +int main(int ac, char **av) +{ + char buf[1024000]; + int i; + char *str; + + hostlist_t hl1, hl2, hl3; + hostset_t set, set1; + hostlist_iterator_t iter, iter2; + + if (!(hl1 = hostlist_create(ac > 1 ? av[1] : NULL))) + perror("hostlist_create"); + if (!(set = hostset_create(ac > 1 ? av[1] : NULL))) + perror("hostlist_create"); + + hl3 = hostlist_create("f[0-5]"); + hostlist_delete(hl3, "f[1-3]"); + hostlist_ranged_string(hl3, 102400, buf); + printf("after delete = `%s'\n", buf); + hostlist_destroy(hl3); + + for (i = 2; i < ac; i++) { + hostlist_push(hl1, av[i]); + hostset_insert(set, av[i]); + } + + hostlist_ranged_string(hl1, 102400, buf); + printf("ranged = `%s'\n", buf); + + iterator_test(buf); + + hostlist_deranged_string(hl1, 10240, buf); + printf("deranged = `%s'\n", buf); + + hostset_ranged_string(set, 1024, buf); + printf("hostset = `%s'\n", buf); + + hostlist_sort(hl1); + hostlist_ranged_string(hl1, 1024, buf); + printf("sorted = `%s'\n", buf); + + hostlist_uniq(hl1); + hostlist_ranged_string(hl1, 1024, buf); + printf("uniqed = `%s'\n", buf); + + hl2 = hostlist_copy(hl1); + printf("pop_range: "); + while ((str = hostlist_pop_range(hl2))) { + printf("`%s' ", str); + free(str); + } + hostlist_destroy(hl2); + printf("\n"); + + hl2 = hostlist_copy(hl1); + printf("shift_range: "); + while ((str = hostlist_shift_range(hl2))) { + printf("`%s' ", str); + free(str); + } + hostlist_destroy(hl2); + printf("\n"); + + iter = hostset_iterator_create(set); + iter2 = hostset_iterator_create(set); + hostlist_iterator_destroy(iter2); + + printf("next: "); + while ((str = hostlist_next(iter))) { + printf("`%s' ", str); + free(str); + } + printf("\n"); + + hostlist_iterator_reset(iter); + printf("next_range: "); + while ((str = hostlist_next_range(iter))) { + printf("`%s' ", str); + free(str); + } + printf("\n"); + + printf("nranges = %d\n", hostset_nranges(set)); + + hostset_ranged_string(set, 1024, buf); + printf("set = %s\n", buf); + + hostset_destroy(set); + hostlist_destroy(hl1); + return 0; +} + +#endif /* TEST_MAIN */ + +/* + * vi: tabstop=4 shiftwidth=4 expandtab + */ diff --git a/lustre/utils/hostlist.h b/lustre/utils/hostlist.h new file mode 100644 index 0000000..abf599b --- /dev/null +++ b/lustre/utils/hostlist.h @@ -0,0 +1,417 @@ +/*****************************************************************************\ + * $Id: hostlist.h,v 1.1.2.1 2008/11/21 15:27:33 yangsheng Exp $ + ***************************************************************************** + * Copyright (C) 2002 The Regents of the University of California. + * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER). + * Written by Mark Grondona + * UCRL-CODE-2002-040. + * + * This file is part of SLURM, a resource management program. + * For details, see . + * + * SLURM is free software; you can redistribute it and/or modify it under + * the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. + * + * SLURM is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more + * details. + * + * You should have received a copy of the GNU General Public License along + * with SLURM; if not, write to the Free Software Foundation, Inc., + * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. +\*****************************************************************************/ + +#ifndef _HOSTLIST_H +#define _HOSTLIST_H + +/* Notes: + * + * If WITH_LSD_FATAL_ERROR_FUNC is defined, the linker will expect to + * find and external lsd_fatal_error(file,line,mesg) function. By default, + * lsd_fatal_error(file,line,mesg) is a macro definition that outputs an + * error message to stderr. This macro may be redefined to invoke another + * routine instead. e.g.: + * + * #define lsd_fatal_error(file,line,mesg) \ + * error("%s:%s %s\n",file,line,mesg); + * + * If WITH_LSD_NOMEM_ERROR_FUNC is defined, the linker will expect to + * find an external lsd_nomem_error(file,line,mesg) function. By default, + * lsd_nomem_error(file,line,mesg) is a macro definition that returns NULL. + * This macro may be redefined to invoke another routine instead. + * + * If WITH_PTHREADS is defined, these routines will be thread-safe. + * + */ + +/* The hostlist opaque data type + * + * A hostlist is a list of hostnames optimized for a prefixXXXX style + * naming convention, where XXXX is a decimal, numeric suffix. + */ +typedef struct hostlist * hostlist_t; + +/* A hostset is a special case of a hostlist. It: + * + * 1. never contains duplicates + * 2. is always sorted + * (Note: sort occurs first on alphanumeric prefix -- where prefix + * matches, numeric suffixes will be sorted *by value*) + */ +typedef struct hostset * hostset_t; + +/* The hostlist iterator type (may be used with a hostset as well) + * used for non-destructive access to hostlist members. + * + */ +typedef struct hostlist_iterator * hostlist_iterator_t; + +/* ----[ hostlist_t functions: ]---- */ + +/* ----[ hostlist creation and destruction ]---- */ + +/* + * hostlist_create(): + * + * Create a new hostlist from a string representation. + * + * The string representation (str) may contain one or more hostnames or + * bracketed hostlists separated by either `,' or whitespace. A bracketed + * hostlist is denoted by a common prefix followed by a list of numeric + * ranges contained within brackets: e.g. "tux[0-5,12,20-25]" + * + * Note: if this module is compiled with WANT_RECKLESS_HOSTRANGE_EXPANSION + * defined, a much more loose interpretation of host ranges is used. + * Reckless hostrange expansion allows all of the following (in addition to + * bracketed hostlists): + * + * o tux0-5,tux12,tux20-25 + * o tux0-tux5,tux12,tux20-tux25 + * o tux0-5,12,20-25 + * + * If str is NULL, and empty hostlist is created and returned. + * + * If the create fails, hostlist_create() returns NULL. + * + * The returned hostlist must be freed with hostlist_destroy() + * + */ +hostlist_t hostlist_create(const char *hostlist); + +/* hostlist_copy(): + * + * Allocate a copy of a hostlist object. Returned hostlist must be freed + * with hostlist_destroy. + */ +hostlist_t hostlist_copy(const hostlist_t hl); + +/* hostlist_destroy(): + * + * Destroy a hostlist object. Frees all memory allocated to the hostlist. + */ +void hostlist_destroy(hostlist_t hl); + + +/* ----[ hostlist list operations ]---- */ + +/* hostlist_push(): + * + * push a string representation of hostnames onto a hostlist. + * + * The hosts argument may take the same form as in hostlist_create() + * + * Returns the number of hostnames inserted into the list, + * or 0 on failure. + */ +int hostlist_push(hostlist_t hl, const char *hosts); + + +/* hostlist_push_host(): + * + * Push a single host onto the hostlist hl. + * This function is more efficient than hostlist_push() for a single + * hostname, since the argument does not need to be checked for ranges. + * + * return value is 1 for success, 0 for failure. + */ +int hostlist_push_host(hostlist_t hl, const char *host); + + +/* hostlist_push_list(): + * + * Push a hostlist (hl2) onto another list (hl1) + * + * Returns 1 for success, 0 for failure. + * + */ +int hostlist_push_list(hostlist_t hl1, hostlist_t hl2); + + +/* hostlist_pop(): + * + * Returns the string representation of the last host pushed onto the list + * or NULL if hostlist is empty or there was an error allocating memory. + * The host is removed from the hostlist. + * + * Note: Caller is responsible for freeing the returned memory. + */ +char * hostlist_pop(hostlist_t hl); + + +char * hostlist_nth(hostlist_t hl, int n); + +/* hostlist_shift(): + * + * Returns the string representation of the first host in the hostlist + * or NULL if the hostlist is empty or there was an error allocating memory. + * The host is removed from the hostlist. + * + * Note: Caller is responsible for freeing the returned memory. + */ +char * hostlist_shift(hostlist_t hl); + + +/* hostlist_pop_range(): + * + * Pop the last bracketed list of hosts of the hostlist hl. + * Returns the string representation in bracketed list form. + * All hosts associated with the returned list are removed + * from hl. + * + * Caller is responsible for freeing returned memory + */ +char * hostlist_pop_range(hostlist_t hl); + +/* hostlist_shift_range(): + * + * Shift the first bracketed hostlist (improperly: range) off the + * hostlist hl. Returns the string representation in bracketed list + * form. All hosts associated with the list are removed from the + * hostlist. + * + * Caller is responsible for freeing returned memory. + */ +char * hostlist_shift_range(hostlist_t hl); + + +/* hostlist_find(): + * + * Searches hostlist hl for the first host matching hostname + * and returns position in list if found. + * + * Returns -1 if host is not found. + * + */ +int hostlist_find(hostlist_t hl, const char *hostname); + +/* hostlist_delete(): + * + * Deletes all hosts in the list represented by `hosts' + * + * Returns the number of hosts successfully deleted + */ +int hostlist_delete(hostlist_t hl, const char *hosts); + + +/* hostlist_delete_host(): + * + * Deletes the first host that matches `hostname' from the hostlist hl. + * Note: "hostname" argument cannot contain a range of hosts + * (see hostlist_delete() for this functionality.) + * + * Returns 1 if successful, 0 if hostname is not found in list. + */ +int hostlist_delete_host(hostlist_t hl, const char *hostname); + + +/* hostlist_delete_nth(): + * + * Deletes the host from position n in the hostlist. + * + * Returns 1 if successful 0 on error. + * + */ +int hostlist_delete_nth(hostlist_t hl, int n); + + +/* hostlist_count(): + * + * Return the number of hosts in hostlist hl. + */ +int hostlist_count(hostlist_t hl); + +/* hostlist_is_empty(): return true if hostlist is empty. */ +#define hostlist_is_empty(__hl) ( hostlist_count(__hl) == 0 ) + +/* ----[ Other hostlist operations ]---- */ + +/* hostlist_sort(): + * + * Sort the hostlist hl. + * + */ +void hostlist_sort(hostlist_t hl); + +/* hostlist_uniq(): + * + * Sort the hostlist hl and remove duplicate entries. + * + */ +void hostlist_uniq(hostlist_t hl); + + +/* ----[ hostlist print functions ]---- */ + +/* hostlist_ranged_string(): + * + * Write the string representation of the hostlist hl into buf, + * writing at most n chars. Returns the number of bytes written, + * or -1 if truncation occurred. + * + * The result will be NULL terminated. + * + * hostlist_ranged_string() will write a bracketed hostlist representation + * where possible. + */ +size_t hostlist_ranged_string(hostlist_t hl, size_t n, char *buf); +size_t hostset_ranged_string(hostset_t hs, size_t n, char *buf); + +/* hostlist_deranged_string(): + * + * Writes the string representation of the hostlist hl into buf, + * writing at most n chars. Returns the number of bytes written, + * or -1 if truncation occurred. + * + * hostlist_deranged_string() will not attempt to write a bracketed + * hostlist representation. Every hostname will be explicitly written. + */ +size_t hostlist_deranged_string(hostlist_t hl, size_t n, char *buf); +size_t hostset_deranged_string(hostset_t hs, size_t n, char *buf); + + +/* ----[ hostlist utility functions ]---- */ + + +/* hostlist_nranges(): + * + * Return the number of ranges currently held in hostlist hl. + */ +int hostlist_nranges(hostlist_t hl); + + +/* ----[ hostlist iterator functions ]---- */ + +/* hostlist_iterator_create(): + * + * Creates and returns a hostlist iterator used for non destructive + * access to a hostlist or hostset. Returns NULL on failure. + */ +hostlist_iterator_t hostlist_iterator_create(hostlist_t hl); + +/* hostset_iterator_create(): + * + * Same as hostlist_iterator_create(), but creates a hostlist_iterator + * from a hostset. + */ +hostlist_iterator_t hostset_iterator_create(hostset_t set); + +/* hostlist_iterator_destroy(): + * + * Destroys a hostlist iterator. + */ +void hostlist_iterator_destroy(hostlist_iterator_t i); + +/* hostlist_iterator_reset(): + * + * Reset an iterator to the beginning of the list. + */ +void hostlist_iterator_reset(hostlist_iterator_t i); + +/* hostlist_next(): + * + * Returns a pointer to the next hostname on the hostlist + * or NULL at the end of the list + * + * The caller is responsible for freeing the returned memory. + */ +char * hostlist_next(hostlist_iterator_t i); + + +/* hostlist_next_range(): + * + * Returns the next bracketed hostlist or NULL if the iterator i is + * at the end of the list. + * + * The caller is responsible for freeing the returned memory. + * + */ +char * hostlist_next_range(hostlist_iterator_t i); + + +/* hostlist_remove(): + * Removes the last host returned by hostlist iterator i + * + * Returns 1 for success, 0 for failure. + */ +int hostlist_remove(hostlist_iterator_t i); + + +/* ----[ hostset operations ]---- */ + +/* hostset_create(): + * + * Create a new hostset object from a string representation of a list of + * hosts. See hostlist_create() for valid hostlist forms. + */ +hostset_t hostset_create(const char *hostlist); + +/* hostset_copy(): + * + * Copy a hostset object. Returned set must be freed with hostset_destroy(). + */ +hostset_t hostset_copy(hostset_t set); + +/* hostset_destroy(): + */ +void hostset_destroy(hostset_t set); + +/* hostset_insert(): + * Add a host or list of hosts into hostset "set." + * + * Returns number of hosts successfully added to "set" + * (insertion of a duplicate is not considered successful) + */ +int hostset_insert(hostset_t set, const char *hosts); + +/* hostset_delete(): + * Delete a host or list of hosts from hostset "set." + * Returns number of hosts deleted from set. + */ +int hostset_delete(hostset_t set, const char *hosts); + +/* hostset_within(): + * Return 1 if all hosts specified by "hosts" are within the hostset "set" + * Retrun 0 if every host in "hosts" is not in the hostset "set" + */ +int hostset_within(hostset_t set, const char *hosts); + +/* hostset_shift(): + * hostset equivalent to hostlist_shift() + */ +char * hostset_shift(hostset_t set); + +/* hostset_shift_range(): + * hostset eqivalent to hostlist_shift_range() + */ +char * hostset_shift_range(hostset_t set); + +/* hostset_count(): + * Count the number of hosts currently in hostset + */ +int hostset_count(hostset_t set); + + +#endif /* !_HOSTLIST_H */ diff --git a/lustre/utils/lshowmount.c b/lustre/utils/lshowmount.c new file mode 100644 index 0000000..4b2675f --- /dev/null +++ b/lustre/utils/lshowmount.c @@ -0,0 +1,411 @@ +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "lshowmount.h" +#include "hash.h" +#include "hostlist.h" + +#define PROGNAME "lshowmount" + +extern int errno; +static int enumerate = 0; +static int lookup = 0; +static int verbose = 0; + +static int totalexports = 0; +static int totalfailures = 0; + +static struct option long_options[] = { + {"enumerate", 0, 0, 'e'}, + {"help", 0, 0, 'h'}, + {"lookup", 0, 0, 'l'}, + {"verbose", 0, 0, 'v'}, + {0, 0, 0, 0} +}; + +inline int +lshowmount_hash_strcmp(const void *key1, const void *key2) +{ + return strcmp((char *) key1, (char *) key2); +} + +inline void +lshowmount_hash_hostlist_freeitem(void *data) +{ + hostlist_t hl = NULL; + + if (data == NULL) { + return; + } + + hl = (hostlist_t) data; + hostlist_destroy(hl); +} + +inline int +is_ipaddress(const char *str) +{ + int rc = 0; + int quad[4]; + + rc = sscanf(str, "%d.%d.%d.%d", &quad[0], &quad[1], &quad[2], &quad[3]); + if (rc == 4) { + return 1; + } + return 0; +} + +inline void +lshowmount_gethostname(const char *src, char *dst, int dstsize) +{ + struct hostent *hostptr = NULL; + char tmpsrc[4]; + int rc = 0; + + memset(dst, 0, sizeof(char) * dstsize); + if (lookup && is_ipaddress(src)) { + rc = inet_pton(AF_INET, src, tmpsrc); + + if (rc <= 0) { + strncpy(dst, src, dstsize); + return; + } + else { + hostptr = gethostbyaddr(tmpsrc, 4, AF_INET); + if (hostptr == NULL) { + strncpy(dst, src, dstsize); + return; + } + else { + strncpy(dst, hostptr->h_name, dstsize); + return; + } + } + } + strncpy(dst, src, dstsize); +} + +void +lshowmount_print_hosts(char** network, + hash_t network_hash) +{ + hostlist_t hl = NULL; + hostlist_iterator_t itr = NULL; + char *hosts = NULL; + int numnets = 0, numhosts = 0, i = 0; + + if (network == NULL || network_hash == NULL) { + return; + } + + numnets = hash_count(network_hash); + for (i = 0; i < numnets; i++) { + errno = 0; + hl = hash_remove(network_hash, network[i]); + if (hl == NULL) { + continue; + } + hostlist_uniq(hl); + numhosts = hostlist_count(hl); + + if (numhosts > 0) { + if (enumerate) { + itr = hostlist_iterator_create(hl); + + /* setup argument */ + while ((hosts = hostlist_next(itr)) != NULL) { + printf(" %s@%s\n", hosts, network[i]); + } + hostlist_iterator_destroy(itr); + } + else { + hosts = malloc(sizeof(char) * (numhosts) * (NID_MAX+1)); + if (hosts == NULL) { + fprintf(stderr, "warning: could not allocate buffer " + "to print hostrange\n"); + return; + } + hostlist_ranged_string(hl, sizeof(char) * + numhosts * + (NID_MAX+1), hosts); + printf(" %s@%s\n", hosts, network[i]); + free(hosts); + hosts = NULL; + } + } + memset(network[i], 0, sizeof(char) * (LNET_NETWORK_TYPE_MAX+1)); + lshowmount_hash_hostlist_freeitem(hl); + } +} + +void usage(void) +{ + fprintf(stderr, "usage: %s [-e] [-h] [-l] [-v]\n", PROGNAME); +} + +int getclients(char* procpath, + char** network, + hash_t network_hash) +{ + DIR *dirp, *dirp2; + struct dirent *dp, *dp2; + char path[PATH_MAX+1]; + char nid[NID_MAX+1], addr[NID_MAX+1]; + int size = PATH_MAX+1, sizeleft, sizeleft2; + int tmplen, tmplen2, idx, rc = 0; + char *tmp, *tmp2; + hostlist_t hl; + + if (procpath == NULL) { + return -1; + } + + /* It is not an error if we cannot open + * procpath since we are not sure if this + * node is an mgs, mds, and/or oss */ + errno = 0; + dirp = opendir(procpath); + if (dirp == NULL) { + return 0; + } + + do { + errno = 0; + dp = readdir(dirp); + if (dp != NULL) { + if (dp->d_type != DT_DIR || + strncmp(dp->d_name, ".", 2) == 0 || + strncmp(dp->d_name, "..", 3) == 0) { + continue; + } + + sizeleft = size; + tmp = path; + memset(tmp, 0, sizeof(char) * sizeleft); + + strncpy(tmp, procpath, sizeleft); + tmplen = strnlen(tmp, sizeleft); + sizeleft -= tmplen; + tmp += tmplen; + + strncpy(tmp, "/", sizeleft); + tmplen = strnlen(tmp, sizeleft); + sizeleft -= tmplen; + tmp += tmplen; + + strncpy(tmp, dp->d_name, sizeleft); + tmplen = strnlen(tmp, sizeleft); + sizeleft -= tmplen; + tmp += tmplen; + + strncpy(tmp, "/", sizeleft); + tmplen = strnlen(tmp, sizeleft); + sizeleft -= tmplen; + tmp += tmplen; + + strncpy(tmp, PROC_EXPORTS, sizeleft); + tmplen = strnlen(tmp, sizeleft); + sizeleft -= tmplen; + tmp += tmplen; + + errno = 0; + dirp2 = opendir(path); + if (dirp2 == NULL) { + fprintf(stderr, "error: could not open: %s\n", path); + rc = errno; + continue; + } + + do { + errno = 0; + dp2 = readdir(dirp2); + if (dp2 != NULL) { + if (strncmp(dp2->d_name, ".", 2) == 0 || + strncmp(dp2->d_name, "..", 3) == 0 || + dp2->d_type != DT_DIR) { + continue; + } + totalexports++; + + sizeleft2 = sizeleft; + tmp2 = tmp; + memset(tmp2, 0, sizeof(char) * sizeleft2); + + strncpy(tmp2, "/", sizeleft2); + tmplen2 = strnlen(tmp2, sizeleft2); + sizeleft2 -= tmplen2; + tmp2 += tmplen2; + + strncpy(tmp2, dp2->d_name, sizeleft2); + tmplen2 = strnlen(tmp2, sizeleft2); + sizeleft2 -= tmplen2; + tmp2 += tmplen2; + + memset(nid, 0, sizeof(char) * (NID_MAX+1)); + strncpy(nid, basename(path), sizeof(char) * (NID_MAX+1)); + tmp2 = strrchr(nid, '@'); + if (tmp2 == NULL) { + totalfailures++; + continue; + } + *tmp2 = '\0'; + tmp2++; + /* Note that tmp2 should now hold the lnet network */ + + /* Check to see if this lnet network already has a hostset + * associated with it */ + errno = 0; + hl = hash_find(network_hash, tmp2); + if (hl == NULL) { + if (hash_count(network_hash) >= NETWORK_MAX) { + (void)closedir(dirp2); + return EINVAL; + } + + /* Create a new hostset for this hash table and + * insert the first part of the nid into it */ + idx = hash_count(network_hash); + strncpy(network[idx], tmp2, LNET_NETWORK_TYPE_MAX); + lshowmount_gethostname(nid, addr, NID_MAX+1); + hl = hostlist_create(addr); + hash_insert(network_hash, network[idx], hl); + } + else { + lshowmount_gethostname(nid, addr, NID_MAX+1); + hostlist_push_host(hl, addr); + } + } + } while (dp2 != NULL); + (void) closedir(dirp2); + + /* If the verbose option is set we want to print + * out the hostlist for each mgs, mds, obdfilter */ + if (verbose) { + printf("%s:\n", dp->d_name); + if (totalfailures > 0) { + fprintf(stderr, "failures %d of %d exports\n", + totalfailures, totalexports); + } + + if (!rc && totalfailures > 0) { + rc = 1; + } + + totalexports = totalfailures = 0; + lshowmount_print_hosts(network, network_hash); + } + } + } while (dp != NULL); + (void) closedir(dirp); + + if (!rc && totalfailures > 0) { + rc = 1; + } + + return rc; +} + +int main(int argc, char **argv) +{ + int opt = 0; + int optidx = 0; + int i = 0, rc = 0, rc2 = 0, rc3 = 0; + hash_t network_hash = NULL; + char** network = NULL; + + while ((opt = getopt_long(argc, argv, "ehlv",long_options, &optidx)) != -1) { + switch (opt) { + case 'e': + enumerate = 1; + break; + case 'h': + usage(); + goto finish; + break; + case 'l': + lookup = 1; + break; + case 'v': + verbose = 1; + break; + default: + usage(); + rc = -1; + goto finish; + break; + } + } + + /* Allocate memory for NETWORK_MAX total possible + * lnet networks. Each network will have its own + * hash table so that we can possibly create a ranged + * string for it */ + network = malloc(sizeof(char *) * NETWORK_MAX); + if (network == NULL) { + rc = ENOMEM; + goto finish; + } + memset(network, 0, sizeof(char *) * NETWORK_MAX); + for (i = 0; i < NETWORK_MAX; i++) { + network[i] = malloc(sizeof(char) * (LNET_NETWORK_TYPE_MAX+1)); + if (network[i] == NULL) { + rc = ENOMEM; + goto finish; + } + memset(network[i], 0, sizeof(char) * (LNET_NETWORK_TYPE_MAX+1)); + } + + /* Initialize the network_hash. This hash table will map + * a particular network say elan1 or tcp2 to a hostset */ + network_hash = hash_create(0, + (hash_key_f) hash_key_string, + lshowmount_hash_strcmp, + lshowmount_hash_hostlist_freeitem); + + rc = getclients(PROC_DIR_MGS, network, network_hash); + rc2 = getclients(PROC_DIR_MDS, network, network_hash); + rc3 = getclients(PROC_DIR_OST, network, network_hash); + if (rc || rc2 || rc3) { + rc = rc2 > rc ? rc2 : rc; + rc = rc3 > rc ? rc3 : rc; + } + + if (!verbose) { + if (totalfailures > 0) { + fprintf(stderr, "failures %d of %d exports\n", + totalfailures, totalexports); + } + lshowmount_print_hosts(network, network_hash); + } + +finish: + hash_destroy(network_hash); + if (network != NULL) { + for (i = 0; i < NETWORK_MAX; i++) { + if (network[i] != NULL) { + free(network[i]); + network[i] = NULL; + } + } + free(network); + network = NULL; + } + + return rc; +} + +/* + * vi:tabstop=4 shiftwidth=4 expandtab + */ diff --git a/lustre/utils/lshowmount.h b/lustre/utils/lshowmount.h new file mode 100644 index 0000000..06e1c5d --- /dev/null +++ b/lustre/utils/lshowmount.h @@ -0,0 +1,17 @@ +#ifndef __LSHOWMOUNT_H +#define __LSHOWMOUNT_H + +#define PROC_DIR_MGS "/proc/fs/lustre/mgs" +#define PROC_DIR_MDS "/proc/fs/lustre/mds" +#define PROC_DIR_OST "/proc/fs/lustre/obdfilter" +#define PROC_EXPORTS "exports" +#define PROC_NID "nid" +#define NID_MAX 1024 +#define LNET_NETWORK_TYPE_MAX 32 +#define NETWORK_MAX 128 + +#endif + +/* + * vi:tabstop=4 shiftwidth=4 expandtab + */ diff --git a/lustre/utils/thread.c b/lustre/utils/thread.c new file mode 100644 index 0000000..64701ec4 --- /dev/null +++ b/lustre/utils/thread.c @@ -0,0 +1,50 @@ +/***************************************************************************** + * $Id: thread.c,v 1.1.2.1 2008/11/21 15:27:33 yangsheng Exp $ + ***************************************************************************** + * Copyright (C) 2003 The Regents of the University of California. + * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER). + * Written by Chris Dunlap . + * + * This file is from LSD-Tools, the LLNL Software Development Toolbox. + * + * LSD-Tools is free software; you can redistribute it and/or modify it under + * the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. + * + * LSD-Tools is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along + * with LSD-Tools; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + *****************************************************************************/ + + +#if HAVE_CONFIG_H +# include "config.h" +#endif /* HAVE_CONFIG_H */ + +#include +#include +#include +#include "thread.h" + + +#if WITH_PTHREADS +#ifndef NDEBUG +int +lsd_mutex_is_locked (pthread_mutex_t *mutex) +{ +/* Returns true if the mutex is locked; o/w, returns false. + */ + int rc; + + assert (mutex != NULL); + rc = pthread_mutex_trylock (mutex); + return (rc == EBUSY ? 1 : 0); +} +#endif /* !NDEBUG */ +#endif /* WITH_PTHREADS */ diff --git a/lustre/utils/thread.h b/lustre/utils/thread.h new file mode 100644 index 0000000..35bdde9 --- /dev/null +++ b/lustre/utils/thread.h @@ -0,0 +1,106 @@ +/***************************************************************************** + * $Id: thread.h,v 1.1.2.1 2008/11/21 15:27:33 yangsheng Exp $ + ***************************************************************************** + * Copyright (C) 2003 The Regents of the University of California. + * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER). + * Written by Chris Dunlap . + * + * This file is from LSD-Tools, the LLNL Software Development Toolbox. + * + * LSD-Tools is free software; you can redistribute it and/or modify it under + * the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. + * + * LSD-Tools is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along + * with LSD-Tools; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + *****************************************************************************/ + + +#ifndef LSD_THREAD_H +#define LSD_THREAD_H + +#if WITH_PTHREADS +# include +# include +# include +#endif /* WITH_PTHREADS */ + + +/***************************************************************************** + * Macros + *****************************************************************************/ + +#if WITH_PTHREADS + +# ifdef WITH_LSD_FATAL_ERROR_FUNC +# undef lsd_fatal_error + extern void lsd_fatal_error (char *file, int line, char *mesg); +# else /* !WITH_LSD_FATAL_ERROR_FUNC */ +# ifndef lsd_fatal_error +# define lsd_fatal_error(file, line, mesg) (abort ()) +# endif /* !lsd_fatal_error */ +# endif /* !WITH_LSD_FATAL_ERROR_FUNC */ + +# define lsd_mutex_init(pmutex) \ + do { \ + int e = pthread_mutex_init (pmutex, NULL); \ + if (e != 0) { \ + errno = e; \ + lsd_fatal_error (__FILE__, __LINE__, "mutex_init"); \ + abort (); \ + } \ + } while (0) + +# define lsd_mutex_lock(pmutex) \ + do { \ + int e = pthread_mutex_lock (pmutex); \ + if (e != 0) { \ + errno = e; \ + lsd_fatal_error (__FILE__, __LINE__, "mutex_lock"); \ + abort (); \ + } \ + } while (0) + +# define lsd_mutex_unlock(pmutex) \ + do { \ + int e = pthread_mutex_unlock (pmutex); \ + if (e != 0) { \ + errno = e; \ + lsd_fatal_error (__FILE__, __LINE__, "mutex_unlock"); \ + abort (); \ + } \ + } while (0) + +# define lsd_mutex_destroy(pmutex) \ + do { \ + int e = pthread_mutex_destroy (pmutex); \ + if (e != 0) { \ + errno = e; \ + lsd_fatal_error (__FILE__, __LINE__, "mutex_destroy"); \ + abort (); \ + } \ + } while (0) + +# ifndef NDEBUG + int lsd_mutex_is_locked (pthread_mutex_t *pmutex); +# endif /* !NDEBUG */ + +#else /* !WITH_PTHREADS */ + +# define lsd_mutex_init(mutex) +# define lsd_mutex_lock(mutex) +# define lsd_mutex_unlock(mutex) +# define lsd_mutex_destroy(mutex) +# define lsd_mutex_is_locked(mutex) (1) + +#endif /* !WITH_PTHREADS */ + + +#endif /* !LSD_THREAD_H */ -- 1.8.3.1