From 846a49199ba011a00e4814bacac524a6fe9b299a Mon Sep 17 00:00:00 2001 From: cbdev Date: Mon, 16 Mar 2020 22:19:27 +0100 Subject: Hash-index event routing table --- installer.sh | 87 +++++++++++++---------------------- midimonster.c | 142 +++++++++++++++++++++++++++++++--------------------------- midimonster.h | 2 + 3 files changed, 109 insertions(+), 122 deletions(-) diff --git a/installer.sh b/installer.sh index 56021c4..111c783 100755 --- a/installer.sh +++ b/installer.sh @@ -26,13 +26,13 @@ latest_version="$(curl --silent "https://api.github.com/repos/cbdevnet/midimonst # make invocation arguments makeargs="all" -normal=$(tput sgr0) -dim=$(tput dim) -bold=$(tput bold) -uline=$(tput smul) -c_red=$(tput setaf 1) -c_green=$(tput setaf 2) -c_mag=$(tput setaf 5) +normal="$(tput sgr0)" +dim="$(tput dim)" +bold="$(tput bold)" +uline="$(tput smul)" +c_red="$(tput setaf 1)" +c_green="$(tput setaf 2)" +c_mag="$(tput setaf 5)" DEFAULT_PREFIX="/usr" DEFAULT_PLUGINPATH="/lib/midimonster" @@ -49,7 +49,7 @@ assign_defaults(){ ARGS(){ for i in "$@"; do - case $i in + case "$i" in --prefix=*) VAR_PREFIX="${i#*=}" ;; @@ -71,37 +71,28 @@ ARGS(){ -fu|--forceupdate) UPDATER_FORCE="1" ;; - -supd|--selfupdate) - NIGHTLY="" - self_update - rmdir "$tmp_path" + --install-updater) + NIGHTLY=1 prepare_repo + install_script exit 0 ;; - -insup|--installupdater) - NIGHTLY="" - install_updater - rmdir "$tmp_path" - exit 0 - ;; - -insdep|--installdeps) + --install-dependencies) install_dependencies - rmdir "$tmp_path" exit 0 ;; -h|--help|*) assign_defaults printf "${bold}Usage:${normal} ${0} ${c_green}[OPTIONS]${normal}" - printf "\n\t${c_green} --prefix${normal} ${c_red}${normal}\tSet the installation prefix\t\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_PREFIX" - printf "\n\t${c_green} --plugins${normal} ${c_red}${normal}\tSet the plugin install path\t\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_PLUGINS" - printf "\n\t${c_green} --defcfg${normal} ${c_red}${normal}\tSet the default configuration path\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_DEFAULT_CFG" - printf "\n\t${c_green} --examples${normal} ${c_red}${normal}\tSet the path for example configurations\t${c_mag}Default:${normal} ${dim}%s${normal}\n" "$VAR_EXAMPLE_CFGS" - printf "\n\t${c_green} --dev${normal}\t\t\tInstall nightly version" - printf "\n ${c_green}-d,\t --default${normal}\t\tUse default values to install" - printf "\n ${c_green}-fu,\t --forceupdate${normal}\t\tForce the updater to update without a version check" - printf "\n ${c_green}-supd,\t --selfupdate${normal}\t\tUpdates this script to the newest version" - printf "\n ${c_green}-insup, --installupdater${normal}\tInstall the updater (Run with midimonster-updater)" - printf "\n ${c_green}-insdep, --installdeps${normal}\t\tInstall dependencies and exit" - printf "\n ${c_green}-h,\t --help${normal}\t\tShow this message and exit" + printf "\n\t${c_green}--prefix${normal} ${c_red}${normal}\t\tSet the installation prefix\t\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_PREFIX" + printf "\n\t${c_green}--plugins${normal} ${c_red}${normal}\tSet the plugin install path\t\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_PLUGINS" + printf "\n\t${c_green}--defcfg${normal} ${c_red}${normal}\t\tSet the default configuration path\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_DEFAULT_CFG" + printf "\n\t${c_green}--examples${normal} ${c_red}${normal}\tSet the path for example configurations\t${c_mag}Default:${normal} ${dim}%s${normal}\n" "$VAR_EXAMPLE_CFGS" + printf "\n\t${c_green}--dev${normal}\t\t\t\tInstall nightly version" + printf "\n\t${c_green}-d, --default${normal}\t\t\tUse default values to install" + printf "\n\t${c_green}-fu, --forceupdate${normal}\t\tForce the updater to update without a version check" + printf "\n\t${c_green}--install-updater${normal}\t\tInstall the updater (Run with midimonster-updater)" + printf "\n\t${c_green}--install-dependencies${normal}\t\tInstall dependencies and exit" + printf "\n\t${c_green}-h, --help${normal}\t\t\tShow this message and exit" printf "\n\t${uline}${bold}${c_mag}Each argument can be overwritten by another, the last one is used!${normal}\n" rmdir "$tmp_path" exit 1 @@ -116,7 +107,7 @@ install_dependencies(){ for dependency in ${deps[@]}; do if [ "$(dpkg-query -W -f='${Status}' "$dependency" 2>/dev/null | grep -c "ok installed")" -eq 0 ]; then printf "Installing %s\n" "$dependency" - apt-get install $dependency + apt-get install "$dependency" else printf "%s already installed!\n" "$dependency" fi @@ -181,7 +172,7 @@ prepare_repo(){ printf "Finding latest stable version...\n" last_tag=$(git describe --abbrev=0) printf "Checking out %s...\n" "$last_tag" - git checkout -f -q $last_tag + git checkout -f -q "$last_tag" fi } @@ -207,30 +198,14 @@ save_config(){ printf "VAR_PREFIX=%s\nVAR_PLUGINS=%s\nVAR_DEFAULT_CFG=%s\nVAR_DESTDIR=%s\nVAR_EXAMPLE_CFGS=%s\n" "$VAR_PREFIX" "$VAR_PLUGINS" "$VAR_DEFAULT_CFG" "$VAR_DESTDIR" "$VAR_EXAMPLE_CFGS" > "$updater_dir/updater.conf" } -# Updates this script either from the downloaded sources or the remote repository. -self_update(){ +# Updates this script using the one from the checked out repo (containing the requested version) +install_script(){ mkdir -p "$updater_dir" - if [ "$NIGHTLY" = "1" ]; then - cp -u "$tmp_path/installer.sh" "$0" - elif [ "$NIGHTLY" != "1" ]; then - wget https://raw.githubusercontent.com/cbdevnet/midimonster/master/installer.sh -O "$0" - fi - chmod +x "$0" -} - -install_updater(){ - mkdir -p "$updater_dir" - if [ "$NIGHTLY" = "1" ]; then - printf "Copying updater to %s/updater.sh\n" "$updater_dir" - cp -u "$tmp_path/installer.sh" "$updater_dir/updater.sh" - else - printf "Downloading updater to %s/updater.sh\n" "$updater_dir" - wget https://raw.githubusercontent.com/cbdevnet/midimonster/master/installer.sh -O "$updater_dir/updater.sh" - fi + printf "Copying updater to %s/updater.sh\n" "$updater_dir" + cp "$tmp_path/installer.sh" "$updater_dir/updater.sh" chmod +x "$updater_dir/updater.sh" printf "Creating symlink /usr/bin/midimonster-updater\n" ln -s "$updater_dir/updater.sh" "/usr/bin/midimonster-updater" - printf "Done.\n" } error_handler(){ @@ -238,7 +213,7 @@ error_handler(){ exit 1 } -cleanup() { +cleanup(){ if [ -d "$tmp_path" ]; then printf "Cleaning up temporary files...\n" rm -rf "$tmp_path" @@ -288,7 +263,7 @@ if [ -f "$updater_dir/updater.conf" ] || [ "$UPDATER_FORCE" = "1" ]; then # Run updater steps prepare_repo - install_updater + install_script save_config build else @@ -296,7 +271,7 @@ else install_dependencies prepare_repo ask_questions - install_updater + install_script save_config build fi diff --git a/midimonster.c b/midimonster.c index 8e217e7..afb6a2b 100644 --- a/midimonster.c +++ b/midimonster.c @@ -29,25 +29,34 @@ typedef struct /*_mm_channel_mapping*/ { channel** to; } channel_mapping; -static size_t mappings = 0; -static channel_mapping* map = NULL; +static struct { + //routing_hash is set up for 256 buckets + size_t entries[256]; + channel_mapping* map[256]; + + event_collection pool[2]; + event_collection* events; +} routing = { + .events = routing.pool +}; + static size_t fds = 0; static managed_fd* fd = NULL; static volatile sig_atomic_t fd_set_dirty = 1; static uint64_t global_timestamp = 0; -static event_collection event_pool[2] = { - {0}, - {0} -}; -static event_collection* primary = event_pool; - volatile static sig_atomic_t shutdown_requested = 0; static void signal_handler(int signum){ shutdown_requested = 1; } +static size_t routing_hash(channel* key){ + uint64_t repr = (uint64_t) key; + //return 8bit hash for 256 buckets, not ideal but it works + return (repr ^ (repr >> 8) ^ (repr >> 16) ^ (repr >> 24) ^ (repr >> 32)) & 0xFF; +} + MM_API uint64_t mm_timestamp(){ return global_timestamp; } @@ -67,53 +76,66 @@ static void update_timestamp(){ } int mm_map_channel(channel* from, channel* to){ - size_t u, m; + size_t u, m, bucket = routing_hash(from); + //find existing source mapping - for(u = 0; u < mappings; u++){ - if(map[u].from == from){ + for(u = 0; u < routing.entries[bucket]; u++){ + if(routing.map[bucket][u].from == from){ break; } } //create new entry - if(u == mappings){ - map = realloc(map, (mappings + 1) * sizeof(channel_mapping)); - if(!map){ + if(u == routing.entries[bucket]){ + routing.map[bucket] = realloc(routing.map[bucket], (routing.entries[bucket] + 1) * sizeof(channel_mapping)); + if(!routing.map[bucket]){ + routing.entries[bucket] = 0; fprintf(stderr, "Failed to allocate memory\n"); return 1; } - memset(map + mappings, 0, sizeof(channel_mapping)); - mappings++; - map[u].from = from; + + memset(routing.map[bucket] + routing.entries[bucket], 0, sizeof(channel_mapping)); + routing.entries[bucket]++; + routing.map[bucket][u].from = from; } //check whether the target is already mapped - for(m = 0; m < map[u].destinations; m++){ - if(map[u].to[m] == to){ + for(m = 0; m < routing.map[bucket][u].destinations; m++){ + if(routing.map[bucket][u].to[m] == to){ return 0; } } - map[u].to = realloc(map[u].to, (map[u].destinations + 1) * sizeof(channel*)); - if(!map[u].to){ + //add a mapping target + routing.map[bucket][u].to = realloc(routing.map[bucket][u].to, (routing.map[bucket][u].destinations + 1) * sizeof(channel*)); + if(!routing.map[bucket][u].to){ fprintf(stderr, "Failed to allocate memory\n"); - map[u].destinations = 0; + routing.map[bucket][u].destinations = 0; return 1; } - map[u].to[map[u].destinations] = to; - map[u].destinations++; + routing.map[bucket][u].to[routing.map[bucket][u].destinations] = to; + routing.map[bucket][u].destinations++; return 0; } -static void map_free(){ - size_t u; - for(u = 0; u < mappings; u++){ - free(map[u].to); +static void routing_cleanup(){ + size_t u, n; + + for(u = 0; u < sizeof(routing.map) / sizeof(routing.map[0]); u++){ + for(n = 0; n < routing.entries[u]; n++){ + free(routing.map[u][n].to); + } + free(routing.map[u]); + routing.map[u] = NULL; + routing.entries[u] = 0; + } + + for(u = 0; u < sizeof(routing.pool) / sizeof(routing.pool[0]); u++){ + free(routing.pool[u].channel); + free(routing.pool[u].value); + routing.pool[u].alloc = 0; } - free(map); - mappings = 0; - map = NULL; } MM_API int mm_manage_fd(int new_fd, char* back, int manage, void* impl){ @@ -170,7 +192,6 @@ MM_API int mm_manage_fd(int new_fd, char* back, int manage, void* impl){ static void fds_free(){ size_t u; for(u = 0; u < fds; u++){ - //TODO free impl if(fd[u].fd >= 0){ close(fd[u].fd); fd[u].fd = -1; @@ -182,56 +203,46 @@ static void fds_free(){ } MM_API int mm_channel_event(channel* c, channel_value v){ - size_t u, p; + size_t u, p, bucket = routing_hash(c); //find mapped channels - for(u = 0; u < mappings; u++){ - if(map[u].from == c){ + for(u = 0; u < routing.entries[bucket]; u++){ + if(routing.map[bucket][u].from == c){ break; } } - if(u == mappings){ + if(u == routing.entries[bucket]){ //target-only channel return 0; } //resize event structures to fit additional events - if(primary->n + map[u].destinations >= primary->alloc){ - primary->channel = realloc(primary->channel, (primary->alloc + map[u].destinations) * sizeof(channel*)); - primary->value = realloc(primary->value, (primary->alloc + map[u].destinations) * sizeof(channel_value)); + if(routing.events->n + routing.map[bucket][u].destinations >= routing.events->alloc){ + routing.events->channel = realloc(routing.events->channel, (routing.events->alloc + routing.map[bucket][u].destinations) * sizeof(channel*)); + routing.events->value = realloc(routing.events->value, (routing.events->alloc + routing.map[bucket][u].destinations) * sizeof(channel_value)); - if(!primary->channel || !primary->value){ + if(!routing.events->channel || !routing.events->value){ fprintf(stderr, "Failed to allocate memory\n"); - primary->alloc = 0; - primary->n = 0; + routing.events->alloc = 0; + routing.events->n = 0; return 1; } - primary->alloc += map[u].destinations; + routing.events->alloc += routing.map[bucket][u].destinations; } //enqueue channel events //FIXME this might lead to one channel being mentioned multiple times in an apply call - for(p = 0; p < map[u].destinations; p++){ - primary->channel[primary->n + p] = map[u].to[p]; - primary->value[primary->n + p] = v; + memcpy(routing.events->channel + routing.events->n, routing.map[bucket][u].to, routing.map[bucket][u].destinations * sizeof(channel*)); + for(p = 0; p < routing.map[bucket][u].destinations; p++){ + routing.events->value[routing.events->n + p] = v; } - primary->n += map[u].destinations; + routing.events->n += routing.map[bucket][u].destinations; return 0; } -static void event_free(){ - size_t u; - - for(u = 0; u < sizeof(event_pool) / sizeof(event_collection); u++){ - free(event_pool[u].channel); - free(event_pool[u].value); - event_pool[u].alloc = 0; - } -} - static void version(){ printf("MIDIMonster %s\n", MIDIMONSTER_VERSION); } @@ -336,13 +347,13 @@ static int core_process(size_t nfds, managed_fd* signaled_fds){ return 1; } - while(primary->n){ + while(routing.events->n){ //swap primary and secondary event collectors - DBGPF("Swapping event collectors, %lu events in primary\n", primary->n); - for(u = 0; u < sizeof(event_pool) / sizeof(event_collection); u++){ - if(primary != event_pool + u){ - secondary = primary; - primary = event_pool + u; + DBGPF("Swapping event collectors, %lu events in primary\n", routing.events->n); + for(u = 0; u < sizeof(routing.pool) / sizeof(routing.pool[0]); u++){ + if(routing.events != routing.pool + u){ + secondary = routing.events; + routing.events = routing.pool + u; break; } } @@ -466,7 +477,7 @@ int main(int argc, char** argv){ if(config_read(cfg_file)){ fprintf(stderr, "Failed to read configuration file %s\n", cfg_file); backends_stop(); - map_free(); + routing_cleanup(); fds_free(); plugins_close(); config_free(); @@ -495,9 +506,8 @@ int main(int argc, char** argv){ bail: //free all data backends_stop(); - map_free(); + routing_cleanup(); fds_free(); - event_free(); plugins_close(); config_free(); platform_shutdown(); diff --git a/midimonster.h b/midimonster.h index dc0e255..61467c1 100644 --- a/midimonster.h +++ b/midimonster.h @@ -247,6 +247,8 @@ MM_API channel* mm_channel(instance* i, uint64_t ident, uint8_t create); * Register (manage = 1) or unregister (manage = 0) a file descriptor * to be selected on. The backend will be notified when the descriptor * becomes ready to read via its registered mmbackend_process_fd call. + * The `impl` argument will be provided within the corresponding + * managed_fd structure upon callback. */ MM_API int mm_manage_fd(int fd, char* backend, int manage, void* impl); -- cgit v1.2.3