From abfd8436df46ca46de9766d17445e2a0cc1da590 Mon Sep 17 00:00:00 2001 From: Shehjar Tikoo Date: Mon, 15 Jun 2009 13:05:39 +0000 Subject: libglusterfs: Turn fd-table O(1) This commit reduces CPU usage of gf_fd_unused_get drastically by making it O(1) instead of O(n). Related to: http://bugs.gluster.com/cgi-bin/bugzilla3/show_bug.cgi?id=16 Signed-off-by: Anand V. Avati --- libglusterfs/src/fd.c | 171 +++++++++++++++++---------- libglusterfs/src/fd.h | 20 +++- xlators/protocol/server/src/server-helpers.c | 32 ++--- 3 files changed, 141 insertions(+), 82 deletions(-) diff --git a/libglusterfs/src/fd.c b/libglusterfs/src/fd.c index fc78acc7c..cfebf1489 100644 --- a/libglusterfs/src/fd.c +++ b/libglusterfs/src/fd.c @@ -77,10 +77,32 @@ gf_roundup_power_of_two (uint32_t nr) return result; } +static int +gf_fd_chain_fd_entries (fdentry_t *entries, uint32_t startidx, + uint32_t endcount) +{ + uint32_t i = 0; + + if (!entries) + return -1; + + /* Chain only till the second to last entry because we want to + * ensure that the last entry has GF_FDTABLE_END. + */ + for (i = startidx; i < (endcount - 1); i++) + entries[i].next_free = i + 1; + + /* i has already been incremented upto the last entry. */ + entries[i].next_free = GF_FDTABLE_END; + + return 0; +} + + static uint32_t gf_fd_fdtable_expand (fdtable_t *fdtable, uint32_t nr) { - fd_t **oldfds = NULL; + fdentry_t *oldfds = NULL; uint32_t oldmax_fds = -1; if (fdtable == NULL || nr < 0) @@ -89,22 +111,30 @@ gf_fd_fdtable_expand (fdtable_t *fdtable, uint32_t nr) return EINVAL; } - nr /= (1024 / sizeof (fd_t *)); + nr /= (1024 / sizeof (fdentry_t)); nr = gf_roundup_power_of_two (nr + 1); - nr *= (1024 / sizeof (fd_t *)); + nr *= (1024 / sizeof (fdentry_t)); - oldfds = fdtable->fds; + oldfds = fdtable->fdentries; oldmax_fds = fdtable->max_fds; - fdtable->fds = CALLOC (nr, sizeof (fd_t *)); - ERR_ABORT (fdtable->fds); + fdtable->fdentries = CALLOC (nr, sizeof (fdentry_t)); + ERR_ABORT (fdtable->fdentries); fdtable->max_fds = nr; if (oldfds) { - uint32_t cpy = oldmax_fds * sizeof (fd_t *); - memcpy (fdtable->fds, oldfds, cpy); + uint32_t cpy = oldmax_fds * sizeof (fdentry_t); + memcpy (fdtable->fdentries, oldfds, cpy); } + gf_fd_chain_fd_entries (fdtable->fdentries, oldmax_fds, + fdtable->max_fds); + + /* Now that expansion is done, we must update the fd list + * head pointer so that the fd allocation functions can continue + * using the expanded table. + */ + fdtable->first_free = oldmax_fds; FREE (oldfds); return 0; } @@ -129,36 +159,36 @@ gf_fd_fdtable_alloc (void) return fdtable; } -fd_t ** +fdentry_t * __gf_fd_fdtable_get_all_fds (fdtable_t *fdtable, uint32_t *count) { - fd_t **fds = NULL; + fdentry_t *fdentries = NULL; if (count == NULL) { goto out; } - fds = fdtable->fds; - fdtable->fds = calloc (fdtable->max_fds, sizeof (fd_t *)); + fdentries = fdtable->fdentries; + fdtable->fdentries = calloc (fdtable->max_fds, sizeof (fdentry_t)); *count = fdtable->max_fds; out: - return fds; + return fdentries; } -fd_t ** +fdentry_t * gf_fd_fdtable_get_all_fds (fdtable_t *fdtable, uint32_t *count) { - fd_t **fds = NULL; + fdentry_t *entries = NULL; if (fdtable) { pthread_mutex_lock (&fdtable->lock); { - fds = __gf_fd_fdtable_get_all_fds (fdtable, count); + entries = __gf_fd_fdtable_get_all_fds (fdtable, count); } pthread_mutex_unlock (&fdtable->lock); } - return fds; + return entries; } void @@ -166,31 +196,31 @@ gf_fd_fdtable_destroy (fdtable_t *fdtable) { struct list_head list = {0, }; fd_t *fd = NULL; - fd_t **fds = NULL; + fdentry_t *fdentries = NULL; uint32_t fd_count = 0; int32_t i = 0; INIT_LIST_HEAD (&list); - if (fdtable) { - pthread_mutex_lock (&fdtable->lock); - { - fds = __gf_fd_fdtable_get_all_fds (fdtable, &fd_count); - FREE (fdtable->fds); - } - pthread_mutex_unlock (&fdtable->lock); + if (!fdtable) + return; - if (fds != NULL) { - for (i = 0; i < fd_count; i++) { - fd = fds[i]; - if (fd != NULL) { - fd_unref (fd); - } - } + pthread_mutex_lock (&fdtable->lock); + { + fdentries = __gf_fd_fdtable_get_all_fds (fdtable, &fd_count); + FREE (fdtable->fdentries); + } + pthread_mutex_unlock (&fdtable->lock); - FREE (fds); + if (fdentries != NULL) { + for (i = 0; i < fd_count; i++) { + fd = fdentries[i].fd; + if (fd != NULL) { + fd_unref (fd); + } } + FREE (fdentries); pthread_mutex_destroy (&fdtable->lock); FREE (fdtable); } @@ -222,19 +252,10 @@ gf_fd_unused_get2 (fdtable_t *fdtable, fd_t *fdptr, int32_t fd) } } - if (!fdtable->fds[fd]) - { - fdtable->fds[fd] = fdptr; - fd_ref (fdptr); - ret = fd; - } - else - { - gf_log ("fd.c", - GF_LOG_ERROR, - "Cannot allocate fd %d (slot not empty in fdtable)", fd); - } - } + fdtable->fdentries[fd].fd = fdptr; + fd_ref (fdptr); + ret = fd; + } err: pthread_mutex_unlock (&fdtable->lock); @@ -245,7 +266,10 @@ err: int32_t gf_fd_unused_get (fdtable_t *fdtable, fd_t *fdptr) { - int32_t fd = -1, i = 0; + int32_t fd = -1; + fdentry_t *fde = NULL; + int error; + int alloc_attempts = 0; if (fdtable == NULL || fdptr == NULL) { @@ -255,28 +279,42 @@ gf_fd_unused_get (fdtable_t *fdtable, fd_t *fdptr) pthread_mutex_lock (&fdtable->lock); { - for (i = 0; imax_fds; i++) - { - if (!fdtable->fds[i]) - break; - } - - if (i < fdtable->max_fds) { - fdtable->fds[i] = fdptr; - fd = i; +fd_alloc_try_again: + if (fdtable->first_free != GF_FDTABLE_END) { + fde = &fdtable->fdentries[fdtable->first_free]; + fd = fdtable->first_free; + fdtable->first_free = fde->next_free; + fde->next_free = GF_FDENTRY_ALLOCATED; + fde->fd = fdptr; } else { - int32_t error; - error = gf_fd_fdtable_expand (fdtable, fdtable->max_fds + 1); + /* If this is true, there is something + * seriously wrong with our data structures. + */ + if (alloc_attempts >= 2) { + gf_log ("server-protocol.c", GF_LOG_ERROR, + "Multiple attempts to expand fd table" + " have failed."); + goto out; + } + error = gf_fd_fdtable_expand (fdtable, + fdtable->max_fds + 1); if (error) { gf_log ("server-protocol.c", GF_LOG_ERROR, "Cannot expand fdtable:%s", strerror (error)); - } else { - fdtable->fds[i] = fdptr; - fd = i; + goto out; } + ++alloc_attempts; + /* At this point, the table stands expanded + * with the first_free referring to the first + * free entry in the new set of fdentries that + * have just been allocated. That means, the + * above logic should just work. + */ + goto fd_alloc_try_again; } } +out: pthread_mutex_unlock (&fdtable->lock); return fd; @@ -287,6 +325,8 @@ inline void gf_fd_put (fdtable_t *fdtable, int32_t fd) { fd_t *fdptr = NULL; + fdentry_t *fde = NULL; + if (fdtable == NULL || fd < 0) { gf_log ("fd", GF_LOG_ERROR, "invalid argument"); @@ -301,8 +341,11 @@ gf_fd_put (fdtable_t *fdtable, int32_t fd) pthread_mutex_lock (&fdtable->lock); { - fdptr = fdtable->fds[fd]; - fdtable->fds[fd] = NULL; + fde = &fdtable->fdentries[fd]; + fdptr = fde->fd; + fde->fd = NULL; + fde->next_free = fdtable->first_free; + fdtable->first_free = fd; } pthread_mutex_unlock (&fdtable->lock); @@ -333,7 +376,7 @@ gf_fd_fdptr_get (fdtable_t *fdtable, int64_t fd) pthread_mutex_lock (&fdtable->lock); { - fdptr = fdtable->fds[fd]; + fdptr = fdtable->fdentries[fd].fd; if (fdptr) { fd_ref (fdptr); } diff --git a/libglusterfs/src/fd.h b/libglusterfs/src/fd.h index d3c9afde3..b4bb12118 100644 --- a/libglusterfs/src/fd.h +++ b/libglusterfs/src/fd.h @@ -51,14 +51,30 @@ struct _fd { }; typedef struct _fd fd_t; +struct fd_table_entry { + fd_t *fd; + int next_free; +}; +typedef struct fd_table_entry fdentry_t; + struct _fdtable { int refcount; uint32_t max_fds; pthread_mutex_t lock; - fd_t **fds; + fdentry_t *fdentries; + int first_free; }; typedef struct _fdtable fdtable_t; +/* Signifies no more entries in the fd table. */ +#define GF_FDTABLE_END -1 + +/* The value us the same as GF_FDTABLE_END but the + * purpose is different here. This is used to invalidated + * the next_free value in an fdentry that has been allocated + */ +#define GF_FDENTRY_ALLOCATED -1 + #include "logging.h" #include "xlator.h" @@ -77,7 +93,7 @@ gf_fd_unused_get (fdtable_t *fdtable, fd_t *fdptr); int32_t gf_fd_unused_get2 (fdtable_t *fdtable, fd_t *fdptr, int32_t fd); -fd_t ** +fdentry_t * gf_fd_fdtable_get_all_fds (fdtable_t *fdtable, uint32_t *count); void diff --git a/xlators/protocol/server/src/server-helpers.c b/xlators/protocol/server/src/server-helpers.c index f49673546..759a9ec82 100644 --- a/xlators/protocol/server/src/server-helpers.c +++ b/xlators/protocol/server/src/server-helpers.c @@ -516,7 +516,7 @@ server_connection_cleanup_flush_cbk (call_frame_t *frame, int do_fd_cleanup (xlator_t *this, server_connection_t *conn, call_frame_t *frame, - fd_t **fds, int fd_count) + fdentry_t *fdentries, int fd_count) { fd_t *fd = NULL; int i = 0, ret = -1; @@ -525,7 +525,7 @@ do_fd_cleanup (xlator_t *this, server_connection_t *conn, call_frame_t *frame, bound_xl = conn->bound_xl; for (i = 0;i < fd_count; i++) { - fd = fds[i]; + fd = fdentries[i].fd; if (fd != NULL) { tmp_frame = copy_frame (frame); @@ -545,7 +545,7 @@ do_fd_cleanup (xlator_t *this, server_connection_t *conn, call_frame_t *frame, fd); } } - FREE (fds); + FREE (fdentries); ret = 0; out: @@ -554,7 +554,7 @@ out: int do_connection_cleanup (xlator_t *this, server_connection_t *conn, - struct _lock_table *ltable, fd_t **fds, int fd_count) + struct _lock_table *ltable, fdentry_t *fdentries, int fd_count) { int32_t ret = 0, saved_ret = 0; call_frame_t *frame = NULL; @@ -568,8 +568,8 @@ do_connection_cleanup (xlator_t *this, server_connection_t *conn, saved_ret = do_lock_table_cleanup (this, conn, frame, ltable); - if (fds != NULL) { - ret = do_fd_cleanup (this, conn, frame, fds, fd_count); + if (fdentries != NULL) { + ret = do_fd_cleanup (this, conn, frame, fdentries, fd_count); } state = CALL_STATE (frame); @@ -591,7 +591,7 @@ server_connection_cleanup (xlator_t *this, server_connection_t *conn) { char do_cleanup = 0; struct _lock_table *ltable = NULL; - fd_t **fds = NULL; + fdentry_t *fdentries = NULL; uint32_t fd_count = 0; int ret = 0; @@ -609,8 +609,8 @@ server_connection_cleanup (xlator_t *this, server_connection_t *conn) } if (conn->fdtable) { - fds = gf_fd_fdtable_get_all_fds (conn->fdtable, - &fd_count); + fdentries = gf_fd_fdtable_get_all_fds (conn->fdtable, + &fd_count); } do_cleanup = 1; } @@ -618,7 +618,7 @@ server_connection_cleanup (xlator_t *this, server_connection_t *conn) pthread_mutex_unlock (&conn->lock); if (do_cleanup && conn->bound_xl) - ret = do_connection_cleanup (this, conn, ltable, fds, fd_count); + ret = do_connection_cleanup (this, conn, ltable, fdentries, fd_count); out: return ret; @@ -639,7 +639,7 @@ server_connection_destroy (xlator_t *this, server_connection_t *conn) struct flock flock = {0,}; fd_t *fd = NULL; int32_t i = 0; - fd_t **fds = NULL; + fdentry_t *fdentries = NULL; uint32_t fd_count = 0; if (conn == NULL) { @@ -752,17 +752,17 @@ server_connection_destroy (xlator_t *this, server_connection_t *conn) pthread_mutex_lock (&(conn->lock)); { if (conn->fdtable) { - fds = gf_fd_fdtable_get_all_fds (conn->fdtable, - &fd_count); + fdentries = gf_fd_fdtable_get_all_fds (conn->fdtable, + &fd_count); gf_fd_fdtable_destroy (conn->fdtable); conn->fdtable = NULL; } } pthread_mutex_unlock (&conn->lock); - if (fds != NULL) { + if (fdentries != NULL) { for (i = 0; i < fd_count; i++) { - fd = fds[i]; + fd = fdentries[i].fd; if (fd != NULL) { tmp_frame = copy_frame (frame); tmp_frame->local = fd; @@ -774,7 +774,7 @@ server_connection_destroy (xlator_t *this, server_connection_t *conn) fd); } } - FREE (fds); + FREE (fdentries); } } -- cgit