On Tue, May 19, 2026 at 09:43:15PM +0800, hongmianquan wrote: > Use a GHashTable to store cpr fds to reduce the time > consumption of `cpr_find_fd` in scenarios with a large > number of fds. The time complexity for `cpr_find_fd` is > reduced from O(N) to O(1). > Keep cpr fds lookups in a GHashTable during normal runtime > while preserving the existing QLIST migration ABI. Build a > temporary QLIST from the hash table in pre_save and rebuild > the hash table from the loaded QLIST in post_load. > > To demonstrate the performance improvement, we tested the total time > consumed by `cpr_find_fd` (called N times for N fds) under our real-world > business scenarios with different numbers of file descriptors. The results > are measured in nanoseconds: > > | Number of FDs | Total time with QLIST (ns) | Total time with GHashTable > (ns) | > |---------------|----------------------------|---------------------------------| > | 540 | 936,753 | 393,358 > | > | 2,870 | 24,102,342 | 2,212,113 > | > | 7,530 | 152,715,916 | 5,474,310 > | > > As shown in the data, the lookup time grows exponentially with the QLIST > as the number of fds increases. With the GHashTable, the time consumption > remains linear (O(1) per lookup), significantly reducing the downtime during > the CPR process.
Queued, thanks. Copy Maciej in case there's comments. > > Signed-off-by: hongmianquan <[email protected]> > --- > migration/cpr.c | 116 ++++++++++++++++++++++++++++++++++++++++-------- > 1 file changed, 98 insertions(+), 18 deletions(-) > > diff --git a/migration/cpr.c b/migration/cpr.c > index a0b37007f5..ffd1e5af7b 100644 > --- a/migration/cpr.c > +++ b/migration/cpr.c > @@ -24,6 +24,7 @@ > /* cpr state container for all information to be saved. */ > > CprState cpr_state; > +static GHashTable *cpr_fds_hash; > > > /****************************************************************************/ > > @@ -48,6 +49,84 @@ static const VMStateDescription vmstate_cpr_fd = { > } > }; > > +static guint cpr_fd_hash(gconstpointer v) > +{ > + const CprFd *elem = v; > + > + return g_str_hash(elem->name) ^ elem->id; > +} > + > +static gboolean cpr_fd_equal(gconstpointer a, gconstpointer b) > +{ > + const CprFd *elem_a = a; > + const CprFd *elem_b = b; > + > + return !strcmp(elem_a->name, elem_b->name) && elem_a->id == elem_b->id; > +} > + > +static void cpr_fd_destroy(gpointer data) > +{ > + CprFd *elem = data; > + > + g_free(elem->name); > + g_free(elem); > +} > + > +static GHashTable *get_cpr_fds_hash(void) > +{ > + if (!cpr_fds_hash) { > + cpr_fds_hash = g_hash_table_new_full(cpr_fd_hash, cpr_fd_equal, > + cpr_fd_destroy, NULL); > + } > + > + return cpr_fds_hash; > +} > + > +static void cpr_fd_hash_insert(CprFd *elem) > +{ > + /* Use the same CprFd as key and value. */ > + g_hash_table_insert(get_cpr_fds_hash(), elem, elem); > +} > + > +static int cpr_fd_pre_save(void *opaque) > +{ > + CprState *state = (CprState *)opaque; > + GHashTableIter iter; > + CprFd *elem; > + > + QLIST_INIT(&state->fds); > + > + g_hash_table_iter_init(&iter, get_cpr_fds_hash()); > + while (g_hash_table_iter_next(&iter, (gpointer *)&elem, NULL)) { > + QLIST_INSERT_HEAD(&state->fds, elem, next); > + } > + > + return 0; > +} > + > +static int cpr_fd_post_load(void *opaque, int version_id) > +{ > + CprState *state = (CprState *)opaque; > + CprFd *elem; > + > + while ((elem = QLIST_FIRST(&state->fds))) { > + QLIST_REMOVE(elem, next); > + > + /* > + * Preserve legacy QLIST lookup semantics if duplicate keys exist in > + * the incoming stream: the first matching entry wins. > + */ > + if (g_hash_table_contains(get_cpr_fds_hash(), elem)) { > + cpr_fd_destroy(elem); > + continue; > + } > + > + cpr_fd_hash_insert(elem); > + } > + > + return 0; > +} > + > void cpr_save_fd(const char *name, int id, int fd) > { > CprFd *elem = g_new0(CprFd, 1); > @@ -57,37 +136,34 @@ void cpr_save_fd(const char *name, int id, int fd) > elem->namelen = strlen(name) + 1; > elem->id = id; > elem->fd = fd; > - QLIST_INSERT_HEAD(&cpr_state.fds, elem, next); > + cpr_fd_hash_insert(elem); > } > > -static CprFd *find_fd(CprFdList *head, const char *name, int id) > +static CprFd *find_fd(const char *name, int id) > { > - CprFd *elem; > + CprFd key = { > + .name = (char *)name, > + .id = id, > + }; > > - QLIST_FOREACH(elem, head, next) { > - if (!strcmp(elem->name, name) && elem->id == id) { > - return elem; > - } > - } > - return NULL; > + return g_hash_table_lookup(get_cpr_fds_hash(), &key); > } > > void cpr_delete_fd(const char *name, int id) > { > - CprFd *elem = find_fd(&cpr_state.fds, name, id); > + CprFd key = { > + .name = (char *)name, > + .id = id, > + }; > > - if (elem) { > - QLIST_REMOVE(elem, next); > - g_free(elem->name); > - g_free(elem); > - } > + g_hash_table_remove(get_cpr_fds_hash(), &key); > > trace_cpr_delete_fd(name, id); > } > > int cpr_find_fd(const char *name, int id) > { > - CprFd *elem = find_fd(&cpr_state.fds, name, id); > + CprFd *elem = find_fd(name, id); > int fd = elem ? elem->fd : -1; > > trace_cpr_find_fd(name, id, fd); > @@ -96,7 +172,7 @@ int cpr_find_fd(const char *name, int id) > > void cpr_resave_fd(const char *name, int id, int fd) > { > - CprFd *elem = find_fd(&cpr_state.fds, name, id); > + CprFd *elem = find_fd(name, id); > int old_fd = elem ? elem->fd : -1; > > if (old_fd < 0) { > @@ -125,9 +201,11 @@ int cpr_open_fd(const char *path, int flags, const char > *name, int id, > > bool cpr_walk_fd(cpr_walk_fd_cb cb) > { > + GHashTableIter iter; > CprFd *elem; > > - QLIST_FOREACH(elem, &cpr_state.fds, next) { > + g_hash_table_iter_init(&iter, get_cpr_fds_hash()); > + while (g_hash_table_iter_next(&iter, (gpointer *)&elem, NULL)) { > g_assert(elem->fd >= 0); > if (!cb(elem->fd)) { > return false; > @@ -141,6 +219,8 @@ static const VMStateDescription vmstate_cpr_state = { > .name = CPR_STATE, > .version_id = 1, > .minimum_version_id = 1, > + .pre_save = cpr_fd_pre_save, > + .post_load = cpr_fd_post_load, > .fields = (VMStateField[]) { > VMSTATE_QLIST_V(fds, CprState, 1, vmstate_cpr_fd, CprFd, next), > VMSTATE_END_OF_LIST() > -- > 2.32.1 (Apple Git-133) > -- Peter Xu
