From f7041112f179aa79b6e315e7d57afbf76d3cd8bb Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Fri, 25 Dec 2015 17:28:09 -0500 Subject: implement child lookup via hash table --- src/client.c | 7 ++- src/hash.c | 84 +++++++++++++++++++++++++++ src/hash.h | 10 ++++ src/netcosm.h | 3 - src/room.c | 6 ++ src/server.c | 178 +++++++++++++++++++++++++++------------------------------- src/test.c | 17 ++++-- 7 files changed, 201 insertions(+), 104 deletions(-) (limited to 'src') diff --git a/src/client.c b/src/client.c index 5930f48..b50e71d 100644 --- a/src/client.c +++ b/src/client.c @@ -116,14 +116,18 @@ void sigusr2_handler(int s, siginfo_t *info, void *vp) (void) s; (void) vp; - sig_printf("got SIGUSR2\n"); + sig_printf("PID %d got SIGUSR2\n", getpid()); /* we only listen to requests from our parent */ if(info->si_pid != getppid()) + { + sig_printf("Unknown PID sent SIGUSR2\n"); return; + } unsigned char cmd; read(from_parent, &cmd, 1); + sig_printf("Got data from parent.\n"); unsigned char buf[MSG_MAX + 1]; switch(cmd) { @@ -151,6 +155,7 @@ void sigusr2_handler(int s, siginfo_t *info, void *vp) out("Cannot go that way.\n"); } case REQ_NOP: + sig_printf("NOP from parent.\n"); break; default: sig_printf("WARNING: client process received unknown code %d\n", cmd); diff --git a/src/hash.c b/src/hash.c index 52a5b93..8e4888a 100644 --- a/src/hash.c +++ b/src/hash.c @@ -63,6 +63,49 @@ void hash_free(void *ptr) free(map); } +void *hash_iterate(void *map, void **saveptr, void **keyptr) +{ + struct iterstate_t { + struct hash_map *map; + struct hash_node *node; + unsigned bucket; + }; + + struct iterstate_t *saved; + + if(map) + { + *saveptr = malloc(sizeof(struct iterstate_t)); + saved = *saveptr; + + saved->map = map; + saved->bucket = 0; + saved->node = NULL; + } + else + saved = *saveptr; + + for(;saved->bucket < saved->map->table_sz; ++(saved->bucket)) + { + do { + if(!saved->node) + saved->node = saved->map->table[saved->bucket]; + else + saved->node = saved->node->next; + if(saved->node) + { + if(keyptr) + *keyptr = saved->node->key; + return (void*)saved->node->data; + } + } while(saved->node); + } + + free(saved); + + return NULL; +} + void *hash_insert(void *ptr, const void *key, const void *data) { struct hash_map *map = ptr; @@ -119,3 +162,44 @@ void hash_insert_pairs(void *ptr, const struct hash_pair *pairs, iter += pairsize; } } + +bool hash_remove(void *ptr, void *key) +{ + struct hash_map *map = ptr; + unsigned hash = map->hash(key) % map->table_sz; + + struct hash_node *iter = map->table[hash], *last = NULL; + + while(iter) + { + if(map->compare(key, iter->key) == 0) + { + if(last) + last->next = iter->next; + else + map->table[hash] = iter->next; + free(iter); + return true; + } + last = iter; + iter = iter->next; + } + + return false; +} + +void *hash_getkeyptr(void *ptr, const void *key) +{ + struct hash_map *map = ptr; + unsigned hash = map->hash(key) % map->table_sz; + + struct hash_node *iter = map->table[hash]; + + while(iter) + { + if(map->compare(key, iter->key) == 0) + return (void*)(iter->key); + iter = iter->next; + } + return NULL; +} diff --git a/src/hash.h b/src/hash.h index ae86b26..23586f4 100644 --- a/src/hash.h +++ b/src/hash.h @@ -1,3 +1,4 @@ +#include #include /* simple, generic chained hash map implementation */ @@ -17,6 +18,12 @@ void *hash_insert(void*, const void *key, const void *data); /* returns NULL if not found */ void *hash_lookup(void*, const void *key); +bool hash_remove(void *ptr, void *key); + +/* use like you would strtok_r */ +/* allocates a buffer that's freed once all elements are processed */ +void *hash_iterate(void *map, void **saved, void **keyptr); + struct hash_pair { void *key; unsigned char value[0]; @@ -25,6 +32,9 @@ struct hash_pair { /* insert n key->pair members of size pairsize */ void hash_insert_pairs(void*, const struct hash_pair*, size_t pairsize, size_t n); +/* gets the original pointer used to store the tuple */ +void *hash_getkeyptr(void*, const void *key); + #define SIMP_HASH(TYPE, NAME) \ unsigned NAME (const void *key) \ { \ diff --git a/src/netcosm.h b/src/netcosm.h index 94fa42f..c9c4a0f 100644 --- a/src/netcosm.h +++ b/src/netcosm.h @@ -116,9 +116,6 @@ struct child_data { char *user; struct in_addr addr; - - /* a linked list works well for this because no random-access is needed */ - struct child_data *next; }; /* the data we get from a world module */ diff --git a/src/room.c b/src/room.c index fb8d138..18fd37e 100644 --- a/src/room.c +++ b/src/room.c @@ -125,11 +125,17 @@ bool world_load(const char *fname, const struct roomdata_t *data, size_t data_sz if(magic != WORLD_MAGIC) return false; read(fd, &world_sz, sizeof(world_sz)); + if(world) + /* possible memory leak here as strings allocated inside of world + aren't freed. avoided by loading only one world per instance */ free(world); + if(world_sz != data_sz) return false; + world = calloc(world_sz, sizeof(struct room_t)); + for(unsigned i = 0; i < world_sz; ++i) { world[i].id = read_roomid(fd); diff --git a/src/server.c b/src/server.c index 3476f38..2ea5d1d 100644 --- a/src/server.c +++ b/src/server.c @@ -35,7 +35,7 @@ void __attribute__((noreturn)) error(const char *fmt, ...) /* assume int is atomic */ volatile int num_clients = 0; -struct child_data *child_data; +void *child_map = NULL; static void sigchld_handler(int s, siginfo_t *info, void *vp) { @@ -50,20 +50,9 @@ static void sigchld_handler(int s, siginfo_t *info, void *vp) pid_t pid; while((pid = waitpid(-1, NULL, WNOHANG)) > 0) { - struct child_data *iter = child_data, *last = NULL; - while(iter) - { - if(iter->pid == pid) - { - if(!last) - child_data = iter->next; - else - last->next = iter->next; - free(iter); - break; - } - iter = iter->next; - } + void *key = hash_getkeyptr(child_map, &pid); + hash_remove(child_map, &pid); + free(key); } errno = saved_errno; @@ -107,7 +96,9 @@ static void req_pass_msg(unsigned char *data, size_t datalen, } write(child->outpipe[1], data, datalen); - kill(child->pid, SIGUSR2); + + if(sender->pid != child->pid) + kill(child->pid, SIGUSR2); } static void req_send_clientinfo(unsigned char *data, size_t datalen, @@ -127,12 +118,17 @@ static void req_send_clientinfo(unsigned char *data, size_t datalen, }; if(child->user) - len = snprintf(buf, sizeof(buf), "Client %s PID %d [%s] USER %s\n", + len = snprintf(buf, sizeof(buf), "Client %s PID %d [%s] USER %s", inet_ntoa(child->addr), child->pid, state[child->state], child->user); else - len = snprintf(buf, sizeof(buf), "Client %s PID %d [%s]\n", + len = snprintf(buf, sizeof(buf), "Client %s PID %d [%s]", inet_ntoa(child->addr), child->pid, state[child->state]); + if(sender->pid == child->pid) + strncat(buf, " [YOU]\n", sizeof(buf)); + else + strncat(buf, "\n", sizeof(buf)); + write(sender->outpipe[1], buf, len); } @@ -317,80 +313,67 @@ static void sigusr1_handler(int s, siginfo_t *info, void *vp) unsigned char cmd, data[MSG_MAX + 1]; const struct child_request *req = NULL; size_t datalen = 0; - struct child_data *sender = NULL; + struct child_data *sender = hash_lookup(child_map, &sender_pid); - /* we have to iterate over the linked list twice */ - /* first to get the data, second to send it to the rest of the children */ + if(!sender) + { + printf("WARNING: got SIGUSR1 from unknown PID, ignoring.\n"); + return; + } - struct child_data *iter = child_data; + read(sender->readpipe[0], &cmd, 1); + req = hash_lookup(request_map, &cmd); + if(!req) + { + sig_printf("Unknown request.\n"); + return; + } - while(iter) + sig_printf("Got command %d\n", cmd); + if(req->havedata) { - if(!req) - { - if(iter->pid == sender_pid) - { - sender = iter; - read(iter->readpipe[0], &cmd, 1); - req = hash_lookup(request_map, &cmd); - if(!req) - { - sig_printf("Unknown request.\n"); - return; - } - - sig_printf("Got command %d\n", cmd); - if(req->havedata) - { - datalen = read(iter->readpipe[0], data, sizeof(data)); - } - - write(sender->outpipe[1], &req->cmd_to_send, 1); - - switch(req->which) - { - case CHILD_SENDER: - case CHILD_ALL: - req->handle_child(data, datalen, sender, iter); - if(req->which == CHILD_SENDER) - goto finish; - break; - case CHILD_NONE: - goto finish; - default: - break; - } - } - } - else - { - switch(req->which) - { - case CHILD_ALL: - case CHILD_ALL_BUT_SENDER: - req->handle_child(data, datalen, sender, iter); - break; - default: - break; - } - } - iter = iter->next; + datalen = read(sender->readpipe[0], data, sizeof(data)); } - /* iterate over the rest of the children, if needed */ - if(req && req->which != CHILD_SENDER) + write(sender->outpipe[1], &req->cmd_to_send, 1); + + switch(req->which) { - iter = child_data; - while(iter) - { - if(iter->pid == sender_pid) - break; + case CHILD_SENDER: + case CHILD_ALL: + req->handle_child(data, datalen, sender, sender); + if(req->which == CHILD_SENDER) + goto finish; + break; + case CHILD_NONE: + goto finish; + default: + break; + } - req->handle_child(data, datalen, sender, iter); + struct child_data *child = NULL; + void *ptr = child_map, *save; - iter = iter->next; + do { + pid_t *key; + child = hash_iterate(ptr, &save, (void**)&key); + ptr = NULL; + if(!child) + break; + sig_printf("Iterating over PID %d\n", *key); + if(child->pid == sender->pid) + continue; + + switch(req->which) + { + case CHILD_ALL: + case CHILD_ALL_BUT_SENDER: + req->handle_child(data, datalen, sender, child); + break; + default: + break; } - } + } while(1); finish: @@ -402,9 +385,6 @@ finish: else sig_printf("WARN: unknown child sent request.\n"); - if(!req) - sig_printf("WARN: unknown request, request ignored\n"); - sig_printf("finished handling client request\n"); } @@ -487,6 +467,9 @@ static int server_bind(void) return sock; } +static SIMP_HASH(pid_t, pid_hash); +static SIMP_EQUAL(pid_t, pid_equal); + int main(int argc, char *argv[]) { if(argc != 2) @@ -508,7 +491,8 @@ int main(int argc, char *argv[]) reqmap_init(); - child_data = NULL; + /* this is set very low to make iteration faster */ + child_map = hash_init(8, pid_hash, pid_equal); printf("Listening on port %d\n", port); @@ -558,16 +542,18 @@ int main(int argc, char *argv[]) close(outpipe[0]); close(new_sock); - /* add the child to the child list */ - struct child_data *old = child_data; - child_data = malloc(sizeof(struct child_data)); - memcpy(child_data->outpipe, outpipe, sizeof(outpipe)); - memcpy(child_data->readpipe, readpipe, sizeof(readpipe)); - child_data->addr = client.sin_addr; - child_data->next = old; - child_data->pid = pid; - child_data->state = STATE_INIT; - child_data->user = NULL; + /* add the child to the child map */ + struct child_data *new = calloc(1, sizeof(struct child_data)); + memcpy(new->outpipe, outpipe, sizeof(outpipe)); + memcpy(new->readpipe, readpipe, sizeof(readpipe)); + new->addr = client.sin_addr; + new->pid = pid; + new->state = STATE_INIT; + new->user = NULL; + + pid_t *pidbuf = malloc(sizeof(pid_t)); + *pidbuf = pid; + hash_insert(child_map, pidbuf, new); } } } diff --git a/src/test.c b/src/test.c index 23a7530..95129e5 100644 --- a/src/test.c +++ b/src/test.c @@ -1,10 +1,19 @@ #include "hash.h" #include +#include int main() { - struct hash_map *map = hash_init(10, hash_djb, strcmp); - hash_insert(map, "a", 42); - hash_insert(map, "b", 32); - printf("weird. %d\n", hash_lookup(map, "a")); + void *map = hash_init(10000, hash_djb, compare_strings); + hash_insert(map, "a",1); + hash_insert(map, "b",2); + void *ptr = map; + void *data = NULL; + void *save; + do { + char *key; + data = hash_iterate(ptr, &save, &key); + ptr = NULL; + printf("%d %s\n", data, key); + } while(data); } -- cgit v1.1