diff options
author | Sergey Poznyakoff <gray@gnu.org> | 2020-03-12 16:09:03 +0200 |
---|---|---|
committer | Sergey Poznyakoff <gray@gnu.org> | 2020-03-12 16:22:46 +0200 |
commit | 56a0f367dff140a1bbd2dc3680c7a645ecf85c18 (patch) | |
tree | fadcaa30c932cad9e5bc26eb52109b1b63a2cb49 /src | |
parent | 22416a1df87f93f611af1ef419f921ed358a8115 (diff) | |
download | ping903-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 (limited to 'src')
-rw-r--r-- | src/Makefile.am | 3 | ||||
-rw-r--r-- | src/config.c | 18 | ||||
-rw-r--r-- | src/defs.h | 2 | ||||
-rw-r--r-- | src/ping903.c | 2 | ||||
-rw-r--r-- | src/ping903.h | 105 | ||||
-rw-r--r-- | src/pinger.c | 339 | ||||
-rw-r--r-- | src/rbt.c | 457 |
7 files changed, 755 insertions, 171 deletions
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; } } @@ -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 --- /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 |