pespin has submitted this change. (
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, 59 insertions(+), 8 deletions(-)
Approvals:
laforge: Looks good to me, but someone else must approve
daniel: Looks good to me, but someone else must approve
pespin: Looks good to me, approved
osmith: Looks good to me, but someone else must approve
Jenkins Builder: Verified
diff --git a/src/core/select.c b/src/core/select.c
index 72f794f..f983601 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,9 @@
* osmo_fd_is_registered() */
unregistered_count++;
llist_del(&fd->list);
+ OSMO_ASSERT(fd->fd >= 0);
+ OSMO_ASSERT(fd->fd <= maxfd);
+ osmo_fd_lookup.table[fd->fd] = NULL;
#ifndef FORCE_IO_SELECT
g_poll.num_registered--;
#endif /* FORCE_IO_SELECT */
@@ -464,19 +503,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 */
--
To view, visit https://gerrit.osmocom.org/c/libosmocore/+/31808
To unsubscribe, or for help writing mail filters, visit
https://gerrit.osmocom.org/settings
Gerrit-Project: libosmocore
Gerrit-Branch: master
Gerrit-Change-Id: I8b71547df8bed84192cb160479fa3debf9b7eade
Gerrit-Change-Number: 31808
Gerrit-PatchSet: 3
Gerrit-Owner: pespin <[email protected]>
Gerrit-Reviewer: Jenkins Builder
Gerrit-Reviewer: daniel <[email protected]>
Gerrit-Reviewer: laforge <[email protected]>
Gerrit-Reviewer: osmith <[email protected]>
Gerrit-Reviewer: pespin <[email protected]>
Gerrit-MessageType: merged
