>From 4b7975d712db27c3d08731e0ebe4efd684256ca4 Mon Sep 17 00:00:00 2001 From: Manfred Spraul Date: Fri, 20 Aug 2021 21:08:12 +0200 Subject: [PATCH] [PATCH] Improve sysvipc_find_ipc() Initially noticed by Rafael Aquini, see https://lore.kernel.org/lkml/20210809203554.1562989-1-aquini@redhat.com/ The algorithm used in sysvipc_find_ipc() is highly inefficient. It actually needs to find the next used index in an idr, and it uses a for loop to locate that entry. But: The IDR API contains idr_get_next(), thus switch the code to use idr_get_next(). In addition: Update a few comments. Signed-off-by: Manfred Spraul --- ipc/util.c | 43 ++++++++++++++++++++----------------------- 1 file changed, 20 insertions(+), 23 deletions(-) diff --git a/ipc/util.c b/ipc/util.c index 0027e47626b7..083fd6dba1a1 100644 --- a/ipc/util.c +++ b/ipc/util.c @@ -783,35 +783,32 @@ struct pid_namespace *ipc_seq_pid_ns(struct seq_file *s) } /* - * This routine locks the ipc structure found at least at position pos. + * This routine locks the ipc structure found at least at index pos. */ static struct kern_ipc_perm *sysvipc_find_ipc(struct ipc_ids *ids, loff_t pos, loff_t *new_pos) { + int tmpidx; struct kern_ipc_perm *ipc; - int total, id; - - total = 0; - for (id = 0; id < pos && total < ids->in_use; id++) { - ipc = idr_find(&ids->ipcs_idr, id); - if (ipc != NULL) - total++; - } - ipc = NULL; - if (total >= ids->in_use) - goto out; + tmpidx = pos; - for (; pos < ipc_mni; pos++) { - ipc = idr_find(&ids->ipcs_idr, pos); - if (ipc != NULL) { - rcu_read_lock(); - ipc_lock_object(ipc); - break; - } + ipc = idr_get_next(&ids->ipcs_idr, &tmpidx); + if (ipc != NULL) { + rcu_read_lock(); + ipc_lock_object(ipc); + /* + * We found the object with the index tmpidx. + * For next search, start with tmpidx+1 + */ + *new_pos = tmpidx + 1; + } else { + /* + * EOF. seq_file can't notice that, thus + * move the offset by one. + */ + *new_pos = pos + 1; } -out: - *new_pos = pos + 1; return ipc; } @@ -829,7 +826,7 @@ static void *sysvipc_proc_next(struct seq_file *s, void *it, loff_t *pos) } /* - * File positions: pos 0 -> header, pos n -> ipc id = n - 1. + * File positions: pos 0 -> header, pos n -> ipc idx = n - 1. * SeqFile iterator: iterator value locked ipc pointer or SEQ_TOKEN_START. */ static void *sysvipc_proc_start(struct seq_file *s, loff_t *pos) @@ -854,7 +851,7 @@ static void *sysvipc_proc_start(struct seq_file *s, loff_t *pos) if (*pos == 0) return SEQ_START_TOKEN; - /* Find the (pos-1)th ipc */ + /* Find the ipc object with the index >= (pos-1) */ return sysvipc_find_ipc(ids, *pos - 1, pos); } -- 2.31.1