pespin has uploaded this change for review. ( https://gerrit.osmocom.org/c/libosmocore/+/31808 )
Change subject: select: Optimize osmo_fd_get_by_fd ......................................................................
select: Optimize osmo_fd_get_by_fd
Optimize osmo_fd_get_by_fd() from O(n) to O(k) by means of allocating dynamically growing array.
Make use from the fact that the kernel always tries to use the smallest possible unused value when allocating a new fd.
Change-Id: I8b71547df8bed84192cb160479fa3debf9b7eade --- M src/core/select.c 1 file changed, 62 insertions(+), 8 deletions(-)
git pull ssh://gerrit.osmocom.org:29418/libosmocore refs/changes/08/31808/1
diff --git a/src/core/select.c b/src/core/select.c index 72f794f..6ff3243 100644 --- a/src/core/select.c +++ b/src/core/select.c @@ -54,6 +54,39 @@ static __thread struct llist_head osmo_fds; /* TLS cannot use LLIST_HEAD() */ static __thread int unregistered_count;
+/* Array of struct osmo_fd * (size "max_fd") ordered by "ofd->fd" */ +static __thread struct { + struct osmo_fd **table; + unsigned int size; +} osmo_fd_lookup; + +static void osmo_fd_lookup_table_extend(unsigned int new_max_fd) +{ + unsigned int min_new_size; + unsigned int pw2; + unsigned int new_size; + + /* First calculate the minimally required new size of the array in bytes: */ + min_new_size = (new_max_fd + 1) * sizeof(struct osmo_fd *); + /* Now find the lower power of two of min_new_size (in bytes): */ + pw2 = 32 - __builtin_clz(min_new_size); + /* get next (upper side) power of 2: */ + pw2++; + OSMO_ASSERT(pw2 <= 31); /* Avoid shifting more than 31 bits */ + new_size = 1 << (pw2 + 1); + + /* Let's make it at least 1024B, to avoid reallocating quickly at startup */ + if (new_size < 1024) + new_size = 1024; + if (new_size > osmo_fd_lookup.size) { + uint8_t *ptr = talloc_realloc_size(OTC_GLOBAL, osmo_fd_lookup.table, new_size); + OSMO_ASSERT(ptr); + memset(ptr + osmo_fd_lookup.size, 0, new_size - osmo_fd_lookup.size); + osmo_fd_lookup.table = (struct osmo_fd **)ptr; + osmo_fd_lookup.size = new_size; + } +} + #ifndef FORCE_IO_SELECT struct poll_state { /* array of pollfd */ @@ -142,8 +175,10 @@ return flags;
/* Register FD */ - if (fd->fd > maxfd) + if (fd->fd > maxfd) { maxfd = fd->fd; + osmo_fd_lookup_table_extend(maxfd); + }
#ifdef OSMO_FD_CHECK if (osmo_fd_is_registered(fd)) { @@ -166,6 +201,7 @@ #endif /* FORCE_IO_SELECT */
llist_add_tail(&fd->list, &osmo_fds); + osmo_fd_lookup.table[fd->fd] = fd;
return 0; } @@ -180,6 +216,12 @@ * osmo_fd_is_registered() */ unregistered_count++; llist_del(&fd->list); + OSMO_ASSERT(fd->fd <= maxfd); + /* Some old programs incorrectly changed fd value to -1 before + * unregistering, so we avoid asserting here, in order to keep backward + * compatibility... */ + if (fd->fd >= 0) + osmo_fd_lookup.table[fd->fd] = NULL; #ifndef FORCE_IO_SELECT g_poll.num_registered--; #endif /* FORCE_IO_SELECT */ @@ -464,19 +506,16 @@ * \returns \ref osmo_fd for \ref fd; NULL in case it doesn't exist */ struct osmo_fd *osmo_fd_get_by_fd(int fd) { - struct osmo_fd *ofd; - - llist_for_each_entry(ofd, &osmo_fds, list) { - if (ofd->fd == fd) - return ofd; - } - return NULL; + if (fd > maxfd) + return NULL; + return osmo_fd_lookup.table[fd]; }
/*! initialize the osmocom select abstraction for the current thread */ void osmo_select_init(void) { INIT_LLIST_HEAD(&osmo_fds); + osmo_fd_lookup_table_extend(0); }
/* ensure main thread always has pre-initialized osmo_fds */