summaryrefslogtreecommitdiffabout
authorSergey Poznyakoff <gray@gnu.org>2020-03-12 14:09:03 (GMT)
committer Sergey Poznyakoff <gray@gnu.org>2020-03-12 14:22:46 (GMT)
commit56a0f367dff140a1bbd2dc3680c7a645ecf85c18 (patch) (side-by-side diff)
treefadcaa30c932cad9e5bc26eb52109b1b63a2cb49
parent22416a1df87f93f611af1ef419f921ed358a8115 (diff)
downloadping903-56a0f367dff140a1bbd2dc3680c7a645ecf85c18.tar.gz
ping903-56a0f367dff140a1bbd2dc3680c7a645ecf85c18.tar.bz2
Use red-black trees to index the hostlist by the host name and IP address.
This speeds up searches and eliminates the possibility of duplicate host entries. * src/rbt.c: New file. * src/Makefile.am: Add new file. * src/config.c (file_read_ip_list): Update diagnostic output. * src/defs.h (LOCAL_IP_LIST_FILE): Rename to MUTABLE_IP_LIST_FILE. All uses changed. * src/ping903.c (ping903): Fix the shutting down diagnostic message. * src/ping903.h: RBT definitions and prototypes. * src/pinger.c (conf_hostping_tail): Rename to immutable_hostping_tail. (FOR_EACH_LOCAL_HOSTPING): Rename to FOR_EACH_MUTABLE_HOSTPING. (save_local_ip_list): Rename to save_mutable_ip_list. All uses changed. (host_name_tree, host_addr_tree): New statics. (pinger_setup): Initialize index trees. (check_host): Look up both the host name and its IP address. All uses changed. (pinger_rbt_insert, pinger_rbt_delete) (hostping_lookup_by_name, hostping_lookup_by_addr): New functions. (hostlist_index,hostlist_unindex): New functions. (pinger_host_add): Insert index entry for the new hostping structure. (get_hostname_stat): Rewrite using index tree lookup. (get_host_matches): Likewise. (hostlist_copy_stat): Likewise. (hostping_match): Remove. (p903_update_commit): Update index trees. (p903_init): Mark all configured hosts as immutable.
Diffstat (more/less context) (ignore whitespace changes)
-rw-r--r--NEWS7
-rw-r--r--configure.ac2
-rw-r--r--src/Makefile.am3
-rw-r--r--src/config.c18
-rw-r--r--src/defs.h2
-rw-r--r--src/ping903.c2
-rw-r--r--src/ping903.h105
-rw-r--r--src/pinger.c339
-rw-r--r--src/rbt.c457
9 files changed, 762 insertions, 173 deletions
diff --git a/NEWS b/NEWS
index 88f7c1c..81d03f5 100644
--- a/NEWS
+++ b/NEWS
@@ -1,8 +1,13 @@
-Ping903 -- history of user-visible changes. 2020-03-11
+Ping903 -- history of user-visible changes. 2020-03-12
See the end of file for copying conditions.
Please send Ping903 bug reports to <gray@gnu.org>
+Version 0.7.90 (Git)
+
+* Use red-black trees to index the IP list.
+
+
Version 0.7, 2020-03-11
* Fix memory leaks.
diff --git a/configure.ac b/configure.ac
index 59a2421..001c248 100644
--- a/configure.ac
+++ b/configure.ac
@@ -15,7 +15,7 @@
# along with Ping903. If not, see <http://www.gnu.org/licenses/>.
AC_PREREQ([2.69])
-AC_INIT([Ping903], [0.7], [gray@gnu.org],
+AC_INIT([Ping903], [0.7.90], [gray@gnu.org],
[ping903],
[https://puszcza.gnu.org.ua/projects/ping903/])
AC_CONFIG_SRCDIR([src/main.c])
diff --git a/src/Makefile.am b/src/Makefile.am
index 6dfd73a..f4fcae3 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -21,7 +21,8 @@ ping903_SOURCES=\
ping903.h\
pinger.c\
config.c\
- remoteip.c
+ remoteip.c\
+ rbt.c
if COND_TCPD
ping903_SOURCES += wrapacl.c
endif
diff --git a/src/config.c b/src/config.c
index 58841c9..26ec810 100644
--- a/src/config.c
+++ b/src/config.c
@@ -61,6 +61,12 @@ cf_ip_list_parse(union cf_callback_arg *arg, void *data)
return rc;
}
+char *rbt_insert_result_str[] = {
+ [RBT_LOOKUP_SUCCESS] = "hostname or IP address already exists",
+ [RBT_LOOKUP_NOENT] = "inserted successfully",
+ [RBT_LOOKUP_FAILURE] = "out of memory"
+};
+
int
file_read_ip_list(FILE *fp, char const *fname)
{
@@ -117,8 +123,9 @@ file_read_ip_list(FILE *fp, char const *fname)
}
rc = pinger_host_add(p, res->ai_addr, res->ai_addrlen);
freeaddrinfo(res);
- if (rc) {
- error("%s:%d: out of memory", fname, ln);
+ if (rc != RBT_LOOKUP_NOENT) {
+ error("%s:%d: %s", fname, ln,
+ rbt_insert_result_str[rc]);
ret = CF_RET_FAIL;
break;
}
@@ -173,9 +180,10 @@ cf_ip_list_heredoc(int mode, union cf_callback_arg *arg, void *data)
rc = pinger_host_add(arg->heredoc.val, res->ai_addr,
res->ai_addrlen);
freeaddrinfo(res);
- if (rc) {
- error("%s:%d: out of memory", arg->heredoc.file,
- arg->heredoc.line);
+ if (rc != RBT_LOOKUP_NOENT) {
+ error("%s:%d: %s",
+ arg->heredoc.file, arg->heredoc.line,
+ rbt_insert_result_str[rc]);
return CF_RET_FAIL;
}
}
diff --git a/src/defs.h b/src/defs.h
index 1f7c7f3..9fa0b20 100644
--- a/src/defs.h
+++ b/src/defs.h
@@ -33,7 +33,7 @@
# define PACKAGESTATEDIR LOCALSTATEDIR "/" PACKAGE
#endif
#define DEFAULT_CONFIG_FILE SYSCONFDIR "/" PACKAGE ".conf"
-#define LOCAL_IP_LIST_FILE PACKAGESTATEDIR "/ip-list"
+#define MUTABLE_IP_LIST_FILE PACKAGESTATEDIR "/ip-list"
#define CRED_FILE_NAME ".ping903.cred"
#define COPYLEFT "\
diff --git a/src/ping903.c b/src/ping903.c
index df1196b..4ae607b 100644
--- a/src/ping903.c
+++ b/src/ping903.c
@@ -1351,7 +1351,7 @@ ping903(void)
/* Wait for signal to arrive */
sigwait(&sigs, &i);
- info("shutting down on signal %s", strsignal(i));
+ info("shutting down on signal \"%s\"", strsignal(i));
MHD_stop_daemon(mhd);
p903_update_commit();
}
diff --git a/src/ping903.h b/src/ping903.h
index 06cf629..2555ddc 100644
--- a/src/ping903.h
+++ b/src/ping903.h
@@ -74,24 +74,7 @@ int cf_trusted_ip(int mode, union cf_callback_arg *arg, void *data);
int cf_trusted_ip_heredoc(int mode, union cf_callback_arg *arg, void *data);
int cf_syslog_facility(int mode, union cf_callback_arg *arg, void *data);
int cf_auth(int mode, union cf_callback_arg *arg, void *data);
-
-void pinger_setup(void);
-int pinger_host_add(char const *name, struct sockaddr *addr, socklen_t addrlen);
-
-/* Return codes for pinger update functions */
-enum {
- UPD_OK, /* Update successful. */
- UPD_NOMEM, /* Not enough memory. */
- UPD_EXISTS, /* When adding: such entry already exists. */
- /* When deleting: such entry does not exist. */
- UPD_NORESOLV /* Host name does not resolve */
-};
-
-int pinger_host_delete_by_name(char const *name);
-int pinger_host_add_name(char const *name);
-int pinger_hostlist_set(struct json_value *obj, char const **err_text,
- int *err_pos);
-
+
char *get_remote_ip(struct MHD_Connection *conn);
enum {
@@ -103,16 +86,16 @@ enum {
};
struct host_stat {
- int status;
- struct timeval start_tv;
- struct timeval stop_tv;
- unsigned long xmit_count;
- unsigned long recv_count;
- unsigned long dup_count;
+ int status; /* Host status: one of the above constants. */
+ struct timeval start_tv; /* Time when the first echo was sent. */
+ struct timeval stop_tv; /* Time when the last reply was received. */
+ unsigned long xmit_count;/* Number of echoes transmitted. */
+ unsigned long recv_count;/* Number of replies received. */
+ unsigned long dup_count; /* Number of duplicated replies. */
double tmin; /* minimum round trip time */
double tmax; /* maximum round trip time */
- double avg;
- double stddev;
+ double avg; /* average round trip time */
+ double stddev; /* standard deviation */
};
static inline int host_stat_is_valid(struct host_stat const *hs) {
@@ -120,31 +103,72 @@ static inline int host_stat_is_valid(struct host_stat const *hs) {
}
typedef struct hostping {
- char *name;
- struct sockaddr *addr;
- socklen_t addrlen;
-
+ char *name; /* Symbolic host name or IP address. */
+ struct sockaddr *addr; /* Host address. */
+ socklen_t addrlen; /* Address length. */
+ int immutable; /* Is this host entry immutable */
+
pthread_mutex_t mutex;
/* Current ping statistics */
- struct timeval start_tv;
- struct timeval xmit_tv;
- struct timeval recv_tv;
- unsigned long xmit_count;
- unsigned long recv_count;
- unsigned long dup_count;
- double tmin; /* minimum round trip time */
- double tmax; /* maximum round trip time */
- double tsum; /* sum of all times, for doing average */
- double tsumsq; /* sum of all times squared, for std. dev. */
+ struct timeval start_tv; /* Time when the first echo was sent. */
+ struct timeval xmit_tv; /* Time when the latest echo was sent. */
+ struct timeval recv_tv; /* Time when the last reply was received. */
+ unsigned long xmit_count; /* Number of echoes transmitted this far. */
+ unsigned long recv_count; /* Number of replies received. */
+ unsigned long dup_count; /* Number of duplicate replies. */
+ double tmin; /* minimum round trip time */
+ double tmax; /* maximum round trip time */
+ double tsum; /* sum of all times, for doing average */
+ double tsumsq; /* sum of all times squared, for stddev. */
/* Last probe statistics */
struct host_stat stat_last;
+ /* Pointers to the previous and next host in the list. */
struct hostping *prev, *next;
+
+ /* Reply counters for each echo request. Actual dimension is
+ * ping_count entries.
+ */
int nreply[1];
} HOSTPING;
+
+/* Red-black tree definitions and prototypes. */
+typedef struct rbt_tree RBT_TREE;
+RBT_TREE *rbt_tree_create(int (*cmp)(HOSTPING*, HOSTPING*));
+
+/* Return codes for rbt_lookup_or_insert_node and derived functions. */
+
+typedef enum {
+ RBT_LOOKUP_SUCCESS, /* Entry was found. */
+ RBT_LOOKUP_NOENT, /* Entry was not found (perhaps created). */
+ RBT_LOOKUP_FAILURE /* Memory allocation error. */
+} RBT_LOOKUP_RESULT;
+
+HOSTPING *rbt_lookup(RBT_TREE *tree, HOSTPING *key);
+RBT_LOOKUP_RESULT rbt_insert(RBT_TREE *tree, HOSTPING *host);
+void rbt_delete(RBT_TREE *tree, HOSTPING *host);
+
+void pinger_setup(void);
+RBT_LOOKUP_RESULT pinger_host_add(char const *name, struct sockaddr *addr,
+ socklen_t addrlen);
+
+/* Return codes for pinger update functions */
+enum {
+ UPD_OK, /* Update successful. */
+ UPD_NOMEM, /* Not enough memory. */
+ UPD_EXISTS, /* When adding: such entry already exists. */
+ /* When deleting: such entry does not exist. */
+ UPD_NORESOLV /* Host name does not resolve */
+};
+int pinger_host_delete_by_name(char const *name);
+int pinger_host_add_name(char const *name);
+int pinger_hostlist_set(struct json_value *obj, char const **err_text,
+ int *err_pos);
+
+
extern int verbose;
extern int fatal_signals[];
extern char *httpd_addr;
@@ -180,4 +204,3 @@ void p903_update_commit(void);
void *p903_sender(void *p);
void *p903_receiver(void *p);
void *p903_scheduler(void *p);
-
diff --git a/src/pinger.c b/src/pinger.c
index 370d5d1..0674747 100644
--- a/src/pinger.c
+++ b/src/pinger.c
@@ -228,7 +228,8 @@ hostlist_concat(HOSTLIST *a, HOSTLIST *b)
}
static HOSTLIST *hostlist;
-static HOSTPING *conf_hostping_tail;
+static HOSTPING *immutable_hostping_tail;
+static RBT_TREE *host_name_tree, *host_addr_tree;
static pthread_rwlock_t hostlist_rwlock = PTHREAD_RWLOCK_INITIALIZER;
typedef enum update_type {
@@ -238,33 +239,109 @@ typedef enum update_type {
} UPDATE_TYPE;
static pthread_mutex_t update_mutex = PTHREAD_MUTEX_INITIALIZER;
-static int check_host(char const *name);
+
+enum {
+ CHECK_HOST_NOT_FOUND,
+ CHECK_HOST_FOUND,
+ CHECK_HOST_IMMUTABLE
+};
+
+static int check_host(char const *name, struct sockaddr *addr, socklen_t len);
static int update_add(UPDATE_TYPE t, void *data);
+static int
+host_name_cmp(HOSTPING *a, HOSTPING *b)
+{
+ return strcmp(a->name, b->name);
+}
+
+static int
+host_addr_cmp(HOSTPING *a, HOSTPING *b)
+{
+ if (a->addrlen != b->addrlen)
+ return a->addrlen - b->addrlen;
+ return memcmp(a->addr, b->addr, b->addrlen);
+}
+
void
pinger_setup(void)
{
hostlist = hostlist_create();
if (!hostlist)
emalloc_die();
+ host_name_tree = rbt_tree_create(host_name_cmp);
+ if (!host_name_tree)
+ emalloc_die();
+ host_addr_tree = rbt_tree_create(host_addr_cmp);
+ if (!host_addr_tree)
+ emalloc_die();
}
-int
+RBT_LOOKUP_RESULT
+pinger_rbt_insert(HOSTPING *hp)
+{
+ RBT_LOOKUP_RESULT res;
+
+ res = rbt_insert(host_name_tree, hp);
+ if (res != RBT_LOOKUP_NOENT)
+ return res;
+ res = rbt_insert(host_addr_tree, hp);
+ if (res != RBT_LOOKUP_NOENT)
+ rbt_delete(host_name_tree, hp);
+ return res;
+}
+
+void
+pinger_rbt_delete(HOSTPING *hp)
+{
+ rbt_delete(host_name_tree, hp);
+ rbt_delete(host_addr_tree, hp);
+}
+
+static inline HOSTPING *
+hostping_lookup_by_name(char const *name)
+{
+ HOSTPING key;
+
+ key.name = (char*) name;
+ return rbt_lookup(host_name_tree, &key);
+}
+
+static inline HOSTPING *
+hostping_lookup_by_addr(struct sockaddr *addr, socklen_t addrlen)
+{
+ HOSTPING key;
+
+ if (!addr)
+ return NULL;
+ key.addr = addr;
+ key.addrlen = addrlen;
+ return rbt_lookup(host_addr_tree, &key);
+}
+
+RBT_LOOKUP_RESULT
pinger_host_add(char const *name, struct sockaddr *addr, socklen_t addrlen)
{
- HOSTPING *hp = hostping_create(name, addr, addrlen);
+ RBT_LOOKUP_RESULT res;
+ HOSTPING *hp;
+
+ hp = hostping_create(name, addr, addrlen);
if (!hp)
- return -1;
- hostlist_add(hostlist, hp);
- return 0;
+ return RBT_LOOKUP_FAILURE;
+ res = pinger_rbt_insert(hp);
+ if (res == RBT_LOOKUP_NOENT)
+ hostlist_add(hostlist, hp);
+ else
+ hostping_free(hp);
+ return res;
}
#define FOR_EACH_HOSTPING(hp) for (hp = hostlist->head; hp; hp = hp->next)
-#define FOR_EACH_LOCAL_HOSTPING(hp) \
- for (hp = conf_hostping_tail \
- ? conf_hostping_tail->next \
- : hostlist->head; \
- hp; \
+#define FOR_EACH_MUTABLE_HOSTPING(hp) \
+ for (hp = immutable_hostping_tail \
+ ? immutable_hostping_tail->next \
+ : hostlist->head; \
+ hp; \
hp = hp->next)
static void
@@ -455,12 +532,9 @@ get_hostname_stat(char const *name, struct json_value **retval)
*retval = NULL;
pthread_rwlock_rdlock(&hostlist_rwlock);
- FOR_EACH_HOSTPING(hp) {
- if (strcmp(hp->name, name) == 0) {
- rc = get_hostping_stat(hp, retval);
- break;
- }
- }
+ hp = hostping_lookup_by_name(name);
+ if (hp)
+ rc = get_hostping_stat(hp, retval);
pthread_rwlock_unlock(&hostlist_rwlock);
return rc;
}
@@ -526,22 +600,6 @@ get_all_hosts(struct json_value **retval)
return rc;
}
-static int
-hostping_match(HOSTPING const *hp, char const *name, struct addrinfo *res)
-{
- if (!hp)
- return 1;
- if (strcmp(hp->name, name) == 0)
- return 0;
- for (; res; res = res->ai_next) {
- if (hp->addrlen == res->ai_addrlen
- && memcmp(hp->addr, res->ai_addr, res->ai_addrlen) == 0) {
- return 0;
- }
- }
- return 1;
-}
-
int
get_host_matches(struct json_value *ar)
{
@@ -549,26 +607,23 @@ get_host_matches(struct json_value *ar)
char const *name;
struct addrinfo *res;
};
- struct addrinfo **aiv;
size_t count = json_array_length(ar);
size_t i;
struct addrinfo hints;
int errors = 0;
- aiv = calloc(count, sizeof(*aiv));
- if (!aiv)
- return -1;
-
memset(&hints, 0, sizeof(hints));
hints.ai_family = AF_INET;
hints.ai_protocol = IPPROTO_TCP;
- for (i = 0; i < count; i++) {
+ pthread_rwlock_rdlock(&hostlist_rwlock);
+ for (i = 0; !errors && i < count; i++) {
char const *name;
int rc;
- struct addrinfo *res;
- struct json_value *obj, *jv;
-
+ struct addrinfo *res, *rp;
+ struct json_value *obj, *jv, *var;
+ HOSTPING *hp;
+
json_array_get(ar, i, &obj);
json_object_get(obj, "name", &jv);
name = jv->v.s;
@@ -576,7 +631,6 @@ get_host_matches(struct json_value *ar)
rc = getaddrinfo(name, NULL, &hints, &res);
switch (rc) {
case 0:
- aiv[i] = res;
break;
case EAI_FAIL:
@@ -584,7 +638,6 @@ get_host_matches(struct json_value *ar)
case EAI_NODATA:
#endif
case EAI_NONAME:
- aiv[i] = NULL;
if (!(jv = json_new_string("Doesn't resolve"))
|| json_object_set(obj, "error", jv)) {
json_value_free(jv);
@@ -610,40 +663,33 @@ get_host_matches(struct json_value *ar)
}
if (errors)
break;
- }
- if (!errors) {
- HOSTPING *hp;
-
- pthread_rwlock_rdlock(&hostlist_rwlock);
- FOR_EACH_HOSTPING(hp) {
- for (i = 0; i < count; i++) {
- struct json_value *obj, *var, *jv;
- json_array_get(ar, i, &obj);
- json_object_get(obj, "name", &jv);
-
- if (hostping_match(hp, jv->v.s, aiv[i]) == 0) {
- json_object_get(obj, "hosts", &var);
- if (!(jv = json_new_string(hp->name))
- || json_array_append(var, jv)) {
- json_value_free(jv);
- errors = 1;
- break;
- }
+ json_object_get(obj, "hosts", &var);
+
+ hp = hostping_lookup_by_name(name);
+ if (hp) {
+ if (!(jv = json_new_string(hp->name))
+ || json_array_append(var, jv)) {
+ json_value_free(jv);
+ errors = 1;
+ }
+ }
+ for (rp = res; !errors && rp; rp = rp->ai_next) {
+ hp = hostping_lookup_by_addr(rp->ai_addr,
+ rp->ai_addrlen);
+
+ if (hp) {
+ if (!(jv = json_new_string(hp->name))
+ || json_array_append(var, jv)) {
+ json_value_free(jv);
+ errors = 1;
}
}
- if (errors)
- break;
}
- pthread_rwlock_unlock(&hostlist_rwlock);
- }
-
- for (i = 0; i < count; i++) {
- if (aiv[i])
- freeaddrinfo(aiv[i]);
+ freeaddrinfo(res);
}
- free(aiv);
-
+ pthread_rwlock_unlock(&hostlist_rwlock);
+
return errors;
}
@@ -653,7 +699,8 @@ pinger_host_delete_by_name(char const *name)
int rc;
pthread_mutex_lock(&update_mutex);
- if (check_host(name)) {
+
+ if (check_host(name, NULL, 0) == CHECK_HOST_FOUND) {
char *cp = strdup(name);
if (cp) {
if (update_add(UPDATE_DELETE, cp) == 0)
@@ -676,7 +723,7 @@ pinger_host_add_name(char const *name)
int rc = 0;
struct addrinfo hints, *res;
HOSTPING *hp;
-
+
memset(&hints, 0, sizeof(hints));
hints.ai_family = AF_INET;
hints.ai_protocol = IPPROTO_TCP;
@@ -686,7 +733,7 @@ pinger_host_add_name(char const *name)
}
pthread_mutex_lock(&update_mutex);
- if (check_host(name) == 0) {
+ if (check_host(name, res->ai_addr, res->ai_addrlen) == CHECK_HOST_NOT_FOUND) {
rc = UPD_NOMEM;
hp = hostping_create(name, res->ai_addr, res->ai_addrlen);
if (hp) {
@@ -775,6 +822,22 @@ pinger_hostlist_set(struct json_value *obj, char const **err_text,
if (rc)
RETERR(MHD_HTTP_BAD_REQUEST,
"host name does not resolve", i + 1);
+ switch (check_host(jv->v.s, res->ai_addr, res->ai_addrlen)) {
+ case CHECK_HOST_NOT_FOUND:
+ /* Safe to add */
+ break;
+ case CHECK_HOST_FOUND:
+ if (mode == UPDATE_REPLACE) {
+ /* It's OK in replace mode */
+ break;
+ }
+ /* fall through */
+ case CHECK_HOST_IMMUTABLE:
+ freeaddrinfo(res);
+ RETERR(MHD_HTTP_BAD_REQUEST,
+ "host name or IP address already exists",
+ i + 1);
+ }
hp = hostping_create(jv->v.s, res->ai_addr, res->ai_addrlen);
freeaddrinfo(res);
if (!hp)
@@ -806,7 +869,7 @@ typedef struct update_entry {
static UPDATE_ENTRY *update_head, *update_tail;
-static void save_local_ip_list(void);
+static void save_mutable_ip_list(void);
static int
update_add(UPDATE_TYPE t, void *data)
@@ -845,26 +908,32 @@ update_add(UPDATE_TYPE t, void *data)
return 0;
}
-static HOSTPING *
-hostping_find_local(char const *name)
+static void
+hostlist_copy_stat(HOSTLIST *hl)
{
HOSTPING *hp;
-
- FOR_EACH_LOCAL_HOSTPING(hp) {
- if (strcmp(hp->name, name) == 0)
- break;
+ for (hp = hl->head; hp; hp = hp->next) {
+ HOSTPING *cur = hostping_lookup_by_name(hp->name);
+ if (cur)
+ hp->stat_last = cur->stat_last;
}
- return hp;
}
static void
-hostlist_copy_stat(HOSTLIST *hl)
+hostlist_index(HOSTLIST *hl)
{
HOSTPING *hp;
for (hp = hl->head; hp; hp = hp->next) {
- HOSTPING *cur = hostping_find_local(hp->name);
- if (cur)
- hp->stat_last = cur->stat_last;
+ pinger_rbt_insert(hp); //FIXME: Handle RBT_LOOKUP_FAILURE (out of memory)
+ }
+}
+
+static void
+hostlist_unindex(HOSTLIST *hl)
+{
+ HOSTPING *hp;
+ for (hp = hl->head; hp; hp = hp->next) {
+ pinger_rbt_delete(hp);
}
}
@@ -881,41 +950,45 @@ p903_update_commit(void)
UPDATE_ENTRY *next = update_head->next;
switch (update_head->type) {
case UPDATE_APPEND:
+ hostlist_index(update_head->v.hlist);
hostlist_concat(hostlist, update_head->v.hlist);
hostlist_free(update_head->v.hlist);
break;
case UPDATE_REPLACE:
hostlist_copy_stat(update_head->v.hlist);
- if (conf_hostping_tail) {
+ if (immutable_hostping_tail) {
HOSTLIST *tmp = update_head->v.hlist;
- hp = conf_hostping_tail->next;
+ hp = immutable_hostping_tail->next;
if (tmp->head)
- tmp->head->prev = conf_hostping_tail;
- conf_hostping_tail->next = tmp->head;
+ tmp->head->prev = immutable_hostping_tail;
+ immutable_hostping_tail->next = tmp->head;
hostlist->tail = tmp->tail;
hostlist->count += tmp->count;
while (hp) {
HOSTPING *next = hp->next;
+ pinger_rbt_delete(hp);
hostping_free(hp);
hp = next;
hostlist->count--;
}
+ hostlist_index(tmp);
free(tmp);
} else {
+ hostlist_unindex(hostlist);
hostlist_free(hostlist);
hostlist = update_head->v.hlist;
+ hostlist_index(hostlist);
}
break;
case UPDATE_DELETE:
- FOR_EACH_LOCAL_HOSTPING(hp) {
- if (strcmp(hp->name, update_head->v.name) == 0) {
- hostlist_remove(hostlist, hp);
- hostping_free(hp);
- break;
- }
+ hp = hostping_lookup_by_name(update_head->v.name);
+ if (hp) {
+ hostlist_remove(hostlist, hp);
+ pinger_rbt_delete(hp);
+ hostping_free(hp);
}
free(update_head->v.name);
}
@@ -925,23 +998,35 @@ p903_update_commit(void)
}
update_tail = NULL;
if (upd)
- save_local_ip_list();
+ save_mutable_ip_list();
pthread_rwlock_unlock(&hostlist_rwlock);
pthread_mutex_unlock(&update_mutex);
}
+/*
+ * Check if the given host is already in the hostlist. Look for
+ * matching name or, if specified, address.
+ * Return value:
+ * CHECK_HOST_NOT_FOUND - Host not found.
+ * CHECK_HOST_FOUND - Host found.
+ * CHECK_HOST_IMMUTABLE - Host found and is immutable.
+ */
static int
-check_host(char const *name)
+check_host(char const *name, struct sockaddr *addr, socklen_t len)
{
HOSTPING *hp;
UPDATE_ENTRY *uent;
int found;
-
- FOR_EACH_HOSTPING(hp) {
- if (strcmp(hp->name, name) == 0)
- return 1;
- }
- found = 0;
+
+ hp = hostping_lookup_by_name(name);
+ if (!hp)
+ hp = hostping_lookup_by_addr(addr, len);
+ if (hp) {
+ if (hp->immutable)
+ return CHECK_HOST_IMMUTABLE;
+ found = 1;
+ } else
+ found = 0;
for (uent = update_head; uent; uent = uent->next) {
switch (uent->type) {
case UPDATE_APPEND:
@@ -958,9 +1043,8 @@ check_host(char const *name)
found--;
}
}
- return found;
+ return found > 0 ? CHECK_HOST_FOUND : CHECK_HOST_NOT_FOUND;
}
-
static int ping_fd;
@@ -1126,16 +1210,23 @@ p903_init(void)
struct protoent *proto;
int i;
FILE *fp;
-
- conf_hostping_tail = hostlist->tail;
- fp = fopen(LOCAL_IP_LIST_FILE, "r");
+ HOSTPING *hp;
+
+ /* Mark all hosts configured so far as immutable and mark the
+ end of the immutable hostlist segment. */
+ for (hp = hostlist->head; hp; hp = hp->next)
+ hp->immutable = 1;
+ immutable_hostping_tail = hostlist->tail;
+
+ /* Read in mutable IP list. */
+ fp = fopen(MUTABLE_IP_LIST_FILE, "r");
if (fp) {
- int rc = file_read_ip_list(fp, LOCAL_IP_LIST_FILE);
+ int rc = file_read_ip_list(fp, MUTABLE_IP_LIST_FILE);
if (rc == CF_RET_FAIL)
exit(1);
fclose(fp);
} else if (errno != ENOENT) {
- fatal("can't open %s: %s", LOCAL_IP_LIST_FILE,
+ fatal("can't open %s: %s", MUTABLE_IP_LIST_FILE,
strerror(errno));
exit(1);
}
@@ -1143,7 +1234,8 @@ p903_init(void)
if (hostlist->count == 0) {
info("no IP addresses configured, starting anyway");
}
-
+
+ /* Open ICMP socket */
proto = getprotobyname("icmp");
if (!proto) {
fatal("no entry for icmp in the system protocol database");
@@ -1155,12 +1247,15 @@ p903_init(void)
exit(1);
}
+ /* Initialize ICMP identifier. */
ping_ident = getpid() & 0xffff;
-
+
+ /* Initialize payload buffer */
data_buffer = emalloc(data_length);
for (i = 0; i < data_length; i++)
data_buffer[i] = i;
+ /* Initialize sequence number database. */
seqidx = calloc(MAX_SEQNO + 1, sizeof(seqidx[0]));
if (!seqidx)
emalloc_die();
@@ -1513,26 +1608,26 @@ err:
}
static void
-save_local_ip_list(void)
+save_mutable_ip_list(void)
{
FILE *fp;
HOSTPING *hp;
info("saving mutable IP address list");
- fp = fopen(LOCAL_IP_LIST_FILE, "w");
+ fp = fopen(MUTABLE_IP_LIST_FILE, "w");
if (!fp) {
if (errno == ENOENT) {
- create_dirs(LOCAL_IP_LIST_FILE);
- fp = fopen(LOCAL_IP_LIST_FILE, "w");
+ create_dirs(MUTABLE_IP_LIST_FILE);
+ fp = fopen(MUTABLE_IP_LIST_FILE, "w");
}
if (!fp) {
fatal("can't open %s for writing: %s",
- LOCAL_IP_LIST_FILE,
+ MUTABLE_IP_LIST_FILE,
strerror(errno));
return;
}
}
- FOR_EACH_LOCAL_HOSTPING(hp) {
+ FOR_EACH_MUTABLE_HOSTPING(hp) {
fprintf(fp, "%s\n", hp->name);
}
fclose(fp);
diff --git a/src/rbt.c b/src/rbt.c
new file mode 100644
index 0000000..85a1361
--- a/dev/null
+++ b/src/rbt.c
@@ -0,0 +1,457 @@
+/* Red-black tree support for Ping903
+ Copyright (C) 2020 Sergey Poznyakoff
+
+ Ping903 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 3, or (at your option)
+ any later version.
+
+ Ping903 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 Ping903. If not, see <http://www.gnu.org/licenses/>.
+*/
+#include <config.h>
+#include <stdlib.h>
+#include <string.h>
+#include "ping903.h"
+
+typedef struct rbt_node RBT_NODE;
+
+typedef enum { RED, BLACK } RBT_COLOR;
+
+struct rbt_node {
+ RBT_NODE *left, *right, *parent;
+ RBT_COLOR color;
+ HOSTPING *host;
+};
+
+struct rbt_tree {
+ int (*cmp)(HOSTPING*, HOSTPING*);
+ RBT_NODE *root; /* Root of the tree */
+};
+
+RBT_TREE *
+rbt_tree_create(int (*cmp)(HOSTPING*, HOSTPING*))
+{
+ RBT_TREE *tree = malloc(sizeof(*tree));
+ if (tree) {
+ tree->cmp = cmp;
+ tree->root = NULL;
+ }
+ return tree;
+}
+
+/*
+ * Red-black tree properties:
+ * 1. Each node is either red or black.
+ * 2. The root node is black.
+ * 3. All leaves are black and contain no data.
+ * 4. Every red node has two children, and both are black. IOW, the
+ * parent of every red node is black.
+ * 5. All paths from any given node to its leaf nodes contain the same
+ * number of black nodes.
+ */
+
+/*
+ * Auxiliary functions for accessing nodes.
+ */
+
+/*
+ * Return the grandparent node of N. Prerequisite: N may not be root.
+ */
+static inline RBT_NODE *
+grandparent(RBT_NODE *n)
+{
+ return n->parent->parent;
+}
+
+/*
+ * Return the sibling node of N. Prerequisite: N may not be root.
+ */
+static inline RBT_NODE *
+sibling(RBT_NODE *n)
+{
+ return (n == n->parent->left) ? n->parent->right : n->parent->left;
+}
+
+/*
+ * Return the uncle node of N. Prerequisite: N must be at least 2 nodes
+ * away from root.
+ */
+static inline RBT_NODE *
+uncle(RBT_NODE *n)
+{
+ return sibling(n->parent);
+}
+
+/*
+ * Returns the color of the node N. Empty leaves are represented by NULL,
+ * therefore NULL is assumed to be black (see property 3).
+ */
+static inline RBT_COLOR
+node_color(RBT_NODE *n)
+{
+ return n == NULL ? BLACK : n->color;
+}
+
+/*
+ * Replace the OLDN with NEWN. Does not modify OLDN.
+ */
+static void
+replace_node(RBT_TREE *tree, RBT_NODE *oldn, RBT_NODE *newn)
+{
+ if (oldn->parent == NULL)
+ tree->root = newn;
+ else if (oldn == oldn->parent->left)
+ oldn->parent->left = newn;
+ else
+ oldn->parent->right = newn;
+
+ if (newn != NULL)
+ newn->parent = oldn->parent;
+}
+
+/*
+ * Rotate the TREE left over the node N.
+ */
+static void
+rotate_left(RBT_TREE *tree, RBT_NODE *n)
+{
+ RBT_NODE *right = n->right;
+ replace_node(tree, n, right);
+ n->right = right->left;
+ if (right->left != NULL)
+ right->left->parent = n;
+ right->left = n;
+ n->parent = right;
+}
+
+/*
+ * Rotate the TREE right over the node N.
+ */
+static void
+rotate_right(RBT_TREE *tree, RBT_NODE *n)
+{
+ RBT_NODE *left = n->left;
+ replace_node(tree, n, left);
+ n->left = left->right;
+ if (left->right != NULL)
+ left->right->parent = n;
+ left->right = n;
+ n->parent = left;
+}
+
+static void
+rbt_delete_fixup(RBT_TREE *tree, RBT_NODE *n)
+{
+ while (1) {
+ if (n->parent == NULL) {
+ /*
+ * If N has become the root node, deletion resulted in
+ * removing one black node (prior root) from every path, so
+ * all properties still hold.
+ */
+ return;
+ } else {
+ /*
+ * If N has a red sibling, change the colors of the parent and
+ * sibling and rotate about the parent. Thus, the sibling
+ * becomes grandparent and we can proceed to the next case.
+ */
+ if (node_color(sibling(n)) == RED) {
+ n->parent->color = RED;
+ sibling(n)->color = BLACK;
+ if (n == n->parent->left)
+ rotate_left(tree, n->parent);
+ else
+ rotate_right(tree, n->parent);
+ }
+
+ /*
+ * If the parent, sibling and nephews are all black, paint the
+ * sibling red. This means one black node was removed from
+ * all paths passing through the parent, so we recurse to the
+ * beginning of the loop with parent as the argument to
+ * restore the properties. This is the only branch that
+ * loops.
+ */
+ if (node_color(n->parent) == BLACK
+ && node_color(sibling(n)) == BLACK
+ && node_color(sibling(n)->left) == BLACK
+ && node_color(sibling(n)->right) == BLACK) {
+ sibling(n)->color = RED;
+ n = n->parent;
+ continue;
+ } else {
+ /*
+ * If the sibling and nephews are black but the parent is
+ * red, swap the colors of the sibling and parent. The
+ * properties are then restored.
+ */
+ if (node_color(n->parent) == RED
+ && node_color(sibling(n)) == BLACK
+ && node_color(sibling(n)->left) == BLACK
+ && node_color(sibling(n)->right) == BLACK) {
+ sibling(n)->color = RED;
+ n->parent->color = BLACK;
+ } else {
+ /*
+ * N is the left child of its parent, its sibling is
+ * black, and the sibling's right child is black. Swap
+ * the colors of the sibling and its left sibling and
+ * rotate right over the sibling.
+ */
+ if (n == n->parent->left
+ && node_color(sibling(n)) == BLACK
+ && node_color(sibling(n)->left) == RED
+ && node_color(sibling(n)->right) == BLACK) {
+ sibling(n)->color = RED;
+ sibling(n)->left->color = BLACK;
+ rotate_right(tree, sibling(n));
+ } else if (n == n->parent->right
+ && node_color(sibling(n)) == BLACK
+ && node_color(sibling(n)->right) == RED
+ && node_color(sibling(n)->left) == BLACK) {
+ /*
+ * The mirror case is handled similarly.
+ */
+ sibling(n)->color = RED;
+ sibling(n)->right->color = BLACK;
+ rotate_left(tree, sibling(n));
+ }
+ /*
+ * N is the left child of its parent, its sibling is
+ * black and the sibling's right child is red. Swap
+ * the colors of the parent and sibling, paint the
+ * sibling's right child black and rotate left at the
+ * parent. Similarly for the mirror case. This
+ * achieves the following:
+ *
+ * . A black node is added to all paths passing
+ * through N;
+ * . A black node is removed from all paths
+ * through the sibling's red child.
+ * . The latter is painted black which restores the
+ * missing black node in all paths through the
+ * sibling's red child.
+ *
+ * Another sibling's child becomes a child of N's
+ * parent during the rotation and is therefore not
+ * affected.
+ */
+ sibling(n)->color = node_color(n->parent);
+ n->parent->color = BLACK;
+ if (n == n->parent->left) {
+ sibling(n)->right->color = BLACK;
+ rotate_left(tree, n->parent);
+ } else {
+ sibling(n)->left->color = BLACK;
+ rotate_right(tree, n->parent);
+ }
+ }
+ }
+ }
+ break;
+ }
+}
+
+/*
+ * Remove N from the TREE.
+ */
+void
+rbt_delete_node(RBT_TREE *tree, RBT_NODE *n)
+{
+ RBT_NODE *child;
+
+ /*
+ * If N has both left and right children, reduce the problem to the
+ * node with only one child. To do so, find the in-order predecessor
+ * of N, copy its value (elem) to N and then delete the predecessor.
+ */
+ if (n->left != NULL && n->right != NULL) {
+ RBT_NODE *p;
+ for (p = n->left; p->right; p = p->right)
+ ;
+ n->host = p->host;
+ n = p;
+ }
+
+ /*
+ * N has only one child. Select it.
+ */
+ child = n->left ? n->left : n->right;
+ if (node_color(n) == BLACK) {
+ n->color = node_color(child);
+ rbt_delete_fixup(tree, n);
+ }
+ replace_node(tree, n, child);
+ if (n->parent == NULL && child != NULL) /* root should be black */
+ child->color = BLACK;
+
+ free(n);
+}
+
+static void
+rbt_insert_fixup(RBT_TREE *tree, RBT_NODE *n)
+{
+ while (1) {
+ if (n->parent == NULL) {
+ /*
+ * Node was inserted at the root of the tree. The root node
+ * must be black (property 2). Changing its color to black
+ * would add one black node to every path, which means the
+ * property 5 would remain satisfied. So we simply paint the
+ * node black.
+ */
+ n->color = BLACK;
+ } else if (node_color(n->parent) == BLACK) {
+ /*
+ * The node has black parent. All properties are satisfied.
+ * There's no need to change anything.
+ */
+ return;
+ } else if (node_color(uncle(n)) == RED) {
+ /*
+ * The uncle node is red. Repaint the parent and uncle black
+ * and the grandparent red. This would satisfy 4. However,
+ * if the grandparent is root, this would violate the property
+ * 2. So we repaint the grandparent by re-entering the fixup
+ * loop with grandparent as the node. This is the only branch
+ * that loops.
+ */
+ n->parent->color = BLACK;
+ uncle(n)->color = BLACK;
+ n = grandparent(n);
+ n->color = RED;
+ continue;
+ } else {
+ /*
+ * The new node is the right child of its parent and the
+ * parent is the left child of the grandparent. Rotate left
+ * about the parent. Mirror case: The new node is the left
+ * child of its parent and the parent is the right child of
+ * the grandparent. Rotate right about the parent. This
+ * fixes the properties for the rbt_insert_5.
+ */
+ if (n == n->parent->right && n->parent == grandparent(n)->left) {
+ rotate_left(tree, n->parent);
+ n = n->left;
+ } else if (n == n->parent->left
+ && n->parent == grandparent(n)->right) {
+ rotate_right(tree, n->parent);
+ n = n->right;
+ }
+
+ /*
+ * The new node is the left child of its parent and the parent
+ * is the left child of the grandparent. Rotate right about
+ * the grandparent. Mirror case: The new node is the right
+ * child of its parent and the parent is the right child of
+ * the grandparent. Rotate left.
+ */
+ n->parent->color = BLACK;
+ grandparent(n)->color = RED;
+ if (n == n->parent->left && n->parent == grandparent(n)->left) {
+ rotate_right(tree, grandparent(n));
+ } else {
+ rotate_left(tree, grandparent(n));
+ }
+ }
+ break;
+ }
+}
+
+RBT_LOOKUP_RESULT
+rbt_lookup_or_insert_node(RBT_TREE *tree, HOSTPING *key, int insert,
+ RBT_NODE **retval)
+{
+ RBT_LOOKUP_RESULT res;
+ RBT_NODE *node, *parent = NULL;
+ RBT_NODE **nodeptr;
+
+ nodeptr = &tree->root;
+ while ((node = *nodeptr) != NULL) {
+ int rc = tree->cmp(key, node->host);
+ if (rc == 0)
+ break;
+ parent = node;
+ if (rc < 0)
+ nodeptr = &node->left;
+ else
+ nodeptr = &node->right;
+ }
+
+ if (node) {
+ res = RBT_LOOKUP_SUCCESS;
+ *retval = node;
+ } else {
+ res = RBT_LOOKUP_NOENT;
+ if (insert) {
+ node = malloc(sizeof(*node));
+ if (!node)
+ return RBT_LOOKUP_FAILURE;
+ memset(node, 0, sizeof(*node));
+ *nodeptr = node;
+ node->parent = parent;
+ rbt_insert_fixup(tree, node);
+ *retval = node;
+ }
+ }
+ return res;
+}
+
+HOSTPING *
+rbt_lookup(RBT_TREE *tree, HOSTPING *key)
+{
+ RBT_NODE *node;
+ switch (rbt_lookup_or_insert_node(tree, key, 0, &node)) {
+ case RBT_LOOKUP_SUCCESS:
+ return node->host;
+
+ case RBT_LOOKUP_NOENT:
+ return NULL;
+
+ default:
+ /* Should not happen, since no allocation takes place. */
+ abort();
+ }
+}
+
+RBT_LOOKUP_RESULT
+rbt_insert(RBT_TREE *tree, HOSTPING *host)
+{
+ RBT_NODE *node;
+ RBT_LOOKUP_RESULT res;
+ res = rbt_lookup_or_insert_node(tree, host, 1, &node);
+ switch (res) {
+ case RBT_LOOKUP_SUCCESS:
+ case RBT_LOOKUP_FAILURE:
+ break;
+
+ case RBT_LOOKUP_NOENT:
+ node->host = host;
+ break;
+
+ default:
+ /* Should not happen */
+ abort();
+ }
+ return res;
+}
+
+void
+rbt_delete(RBT_TREE *tree, HOSTPING *host)
+{
+ RBT_NODE *node;
+ if (rbt_lookup_or_insert_node(tree, host, 0, &node) == RBT_LOOKUP_SUCCESS)
+ rbt_delete_node(tree, node);
+}
+
+/* Local Variables: */
+/* mode: c */
+/* c-basic-offset: 4 */
+/* End: */

Return to:

Send suggestions and report system problems to the System administrator.