[PATCH v10 4/4] ipc: Add a cyclic mode for id generation

From: Waiman Long
Date: Mon Nov 05 2018 - 10:46:04 EST


The idea of using the cyclic mode to reduce id reuse came from Manfred
Spraul <manfred@xxxxxxxxxxxxxxxx>. There may be a little bit of
additional memory/performance overhead in doing cyclic id allocation,
but it is a slow path anyway and a bit of overhead shouldn't be an issue.

This patch differs from his as the cyclic mode is not the default and
has to be explicitly opted in for users who want that.

Note that it is possible to use an identifier larger than the given
IPC mni number in cyclic mode.

Signed-off-by: Waiman Long <longman@xxxxxxxxxx>
---
Documentation/sysctl/kernel.txt | 10 ++++++++--
include/linux/ipc_namespace.h | 1 +
ipc/ipc_sysctl.c | 3 ++-
ipc/util.c | 6 +++++-
4 files changed, 16 insertions(+), 4 deletions(-)

diff --git a/Documentation/sysctl/kernel.txt b/Documentation/sysctl/kernel.txt
index 91bada1..6de0679 100644
--- a/Documentation/sysctl/kernel.txt
+++ b/Documentation/sysctl/kernel.txt
@@ -406,12 +406,18 @@ are being generated.

0: legacy mode
1: delete mode
+2: cyclic mode

There are two components in an IPC id - an integer identifier and a
sequence number. In the legacy mode, the sequence number is incremented
every time a new id is generated. In the delete mode, the sequence number
-is only incremented if one or more ids have been previously deleted. The
-delete mode reduces the chance that a given id will be reused again.
+is only incremented if one or more ids have been previously deleted.
+In the cyclic mode, the sequence number increments in the same way as the
+delete mode, but the identifier is allocated cyclically through the whole
+IPC identifier number space instead of using the lowest available number.
+
+The cyclic mode has the lowest chance of IPC id reuse followed by the
+delete mode and the legacy mode.

==============================================================

diff --git a/include/linux/ipc_namespace.h b/include/linux/ipc_namespace.h
index 79d9d50..481dc02 100644
--- a/include/linux/ipc_namespace.h
+++ b/include/linux/ipc_namespace.h
@@ -33,6 +33,7 @@ struct ipc_ids {
enum ipc_id_mode {
ipc_id_legacy, /* Sequence # incremented on every allocation */
ipc_id_delete, /* Sequence # incremented only if an ID was deleted */
+ ipc_id_cyclic, /* Identifier is allocated cyclically */
};

struct ipc_namespace {
diff --git a/ipc/ipc_sysctl.c b/ipc/ipc_sysctl.c
index 4c30e62..8d114d0 100644
--- a/ipc/ipc_sysctl.c
+++ b/ipc/ipc_sysctl.c
@@ -119,6 +119,7 @@ static int proc_ipc_sem_dointvec(struct ctl_table *table, int write,

static int zero;
static int one = 1;
+static int two = 2;
static int int_max = INT_MAX;
int ipc_mni = IPCMNI;
int ipc_mni_shift = IPCMNI_SHIFT;
@@ -207,7 +208,7 @@ static int proc_ipc_sem_dointvec(struct ctl_table *table, int write,
.mode = 0644,
.proc_handler = proc_ipc_dointvec_minmax,
.extra1 = &zero,
- .extra2 = &one,
+ .extra2 = &two,
},
#ifdef CONFIG_CHECKPOINT_RESTORE
{
diff --git a/ipc/util.c b/ipc/util.c
index 04c8e31..8d73d17 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -230,7 +230,11 @@ static inline int ipc_idr_alloc(struct ipc_ids *ids, struct kern_ipc_perm *new,
ids->deleted = false;
}
new->seq = ids->seq;
- idx = idr_alloc(&ids->ipcs_idr, new, 0, 0, GFP_NOWAIT);
+ if (idmode == ipc_id_cyclic)
+ idx = idr_alloc_cyclic(&ids->ipcs_idr, new, 0, IPCMNI,
+ GFP_NOWAIT);
+ else
+ idx = idr_alloc(&ids->ipcs_idr, new, 0, 0, GFP_NOWAIT);
} else {
new->seq = ipcid_to_seqx(next_id);
idx = idr_alloc(&ids->ipcs_idr, new, ipcid_to_idx(next_id),
--
1.8.3.1