Re: [RFC, PATCH] ipc/util.c: use idr_alloc_cyclic() for ipc allocations
On 10/2/18 8:27 PM, Waiman Long wrote:
On 10/02/2018 12:19 PM, Manfred Spraul wrote:
A bit related to the patch series that increases IPC_MNI:
(User space) id reuse create the risk of data corruption:
Process A: calls ipc function
Process A: sleeps just at the beginning of the syscall
Process B: Frees the ipc object (i.e.: calls ...ctl(IPC_RMID)
Process B: Creates a new ipc object (i.e.: calls ...get())
Process A: is woken up, and accesses the new object
To reduce the probability that the new and the old object
have the same id, the current implementation adds a
sequence number to the index of the object in the idr tree.
To further reduce the probability for a reuse, switch from
idr_alloc to idr_alloc_cyclic.
The patch cycles over at least RADIX_TREE_MAP_SIZE, i.e.
if there is only a small number of objects, the accesses
continue to be direct.
As an option, this could be made dependent on the extended
mode: In extended mode, cycle over e.g. at least 16k ids.
Signed-off-by: Manfred Spraul
---
Open questions:
- Is there a significant performance advantage, especially
there are many ipc ids?
- Over how many ids should the code cycle always?
- Further review remarks?
ipc/util.c | 22 +-
1 file changed, 21 insertions(+), 1 deletion(-)
diff --git a/ipc/util.c b/ipc/util.c
index 0af05752969f..6f83841f6761 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -216,10 +216,30 @@ static inline int ipc_idr_alloc(struct ipc_ids *ids,
struct kern_ipc_perm *new)
*/
if (next_id < 0) { /* !CHECKPOINT_RESTORE or next_id is unset */
+ int idr_max;
+
new->seq = ids->seq++;
if (ids->seq > IPCID_SEQ_MAX)
ids->seq = 0;
- idx = idr_alloc(>ipcs_idr, new, 0, 0, GFP_NOWAIT);
+
+ /*
+* If a user space visible id is reused, then this creates a
+* risk for data corruption. To reduce the probability that
+* a number is reduced, two approaches are used:
reduced -> reused?
Of course.
+* 1) the idr index is allocated cyclically.
+* 2) the use space id is build by concatenating the
+*internal idr index with a sequence number
+* To avoid that both numbers have the same cycle time, try
+* to set the size for the cyclic alloc to an odd number.
+*/
+ idr_max = ids->in_use*2+1;
+ if (idr_max < RADIX_TREE_MAP_SIZE-1)
+ idr_max = RADIX_TREE_MAP_SIZE-1;
+ if (idr_max > IPCMNI)
+ idr_max = IPCMNI;
+
+ idx = idr_alloc_cyclic(>ipcs_idr, new, 0, idr_max,
+ GFP_NOWAIT);
} else {
new->seq = ipcid_to_seqx(next_id);
idx = idr_alloc(>ipcs_idr, new, ipcid_to_idx(next_id),
Each of IPC components have their own sysctl parameters limiting the max
number of objects that can be allocated. With cyclic allocation, you
will have to make sure that idr_max is not larger than the corresponding
IPC sysctl parameters. That may require moving the limits to the
corresponding ipc_ids structure so that it can be used in ipc_idr_alloc().
First, I would disagree:
the sysctl limits specify how many objects can exist.
idr_max is the maximum index in the radix tree that can exist. There is
a hard limit of IPCMNI, but that's it.
But:
The name is wrong, I will rename the variable to idx_max
What is the point of comparing idr_max against RADIX_TREE_MAP_SIZE-1? Is
it for performance reason.
Let's assume you have only 1 ipc object, and you alloc/release that object.
At alloc time, ids->in_use is 0 -> idr_max 1 -> every object will end up
with idx=0.
This would defeat the whole purpose of using a cyclic alloc.
Thus: cycle over at least 63 ids -> 5 additional bits to avoid collisions.
--
Manfred
Re: [RFC, PATCH] ipc/util.c: use idr_alloc_cyclic() for ipc allocations
On 10/2/18 8:27 PM, Waiman Long wrote:
On 10/02/2018 12:19 PM, Manfred Spraul wrote:
A bit related to the patch series that increases IPC_MNI:
(User space) id reuse create the risk of data corruption:
Process A: calls ipc function
Process A: sleeps just at the beginning of the syscall
Process B: Frees the ipc object (i.e.: calls ...ctl(IPC_RMID)
Process B: Creates a new ipc object (i.e.: calls ...get())
Process A: is woken up, and accesses the new object
To reduce the probability that the new and the old object
have the same id, the current implementation adds a
sequence number to the index of the object in the idr tree.
To further reduce the probability for a reuse, switch from
idr_alloc to idr_alloc_cyclic.
The patch cycles over at least RADIX_TREE_MAP_SIZE, i.e.
if there is only a small number of objects, the accesses
continue to be direct.
As an option, this could be made dependent on the extended
mode: In extended mode, cycle over e.g. at least 16k ids.
Signed-off-by: Manfred Spraul
---
Open questions:
- Is there a significant performance advantage, especially
there are many ipc ids?
- Over how many ids should the code cycle always?
- Further review remarks?
ipc/util.c | 22 +-
1 file changed, 21 insertions(+), 1 deletion(-)
diff --git a/ipc/util.c b/ipc/util.c
index 0af05752969f..6f83841f6761 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -216,10 +216,30 @@ static inline int ipc_idr_alloc(struct ipc_ids *ids,
struct kern_ipc_perm *new)
*/
if (next_id < 0) { /* !CHECKPOINT_RESTORE or next_id is unset */
+ int idr_max;
+
new->seq = ids->seq++;
if (ids->seq > IPCID_SEQ_MAX)
ids->seq = 0;
- idx = idr_alloc(>ipcs_idr, new, 0, 0, GFP_NOWAIT);
+
+ /*
+* If a user space visible id is reused, then this creates a
+* risk for data corruption. To reduce the probability that
+* a number is reduced, two approaches are used:
reduced -> reused?
Of course.
+* 1) the idr index is allocated cyclically.
+* 2) the use space id is build by concatenating the
+*internal idr index with a sequence number
+* To avoid that both numbers have the same cycle time, try
+* to set the size for the cyclic alloc to an odd number.
+*/
+ idr_max = ids->in_use*2+1;
+ if (idr_max < RADIX_TREE_MAP_SIZE-1)
+ idr_max = RADIX_TREE_MAP_SIZE-1;
+ if (idr_max > IPCMNI)
+ idr_max = IPCMNI;
+
+ idx = idr_alloc_cyclic(>ipcs_idr, new, 0, idr_max,
+ GFP_NOWAIT);
} else {
new->seq = ipcid_to_seqx(next_id);
idx = idr_alloc(>ipcs_idr, new, ipcid_to_idx(next_id),
Each of IPC components have their own sysctl parameters limiting the max
number of objects that can be allocated. With cyclic allocation, you
will have to make sure that idr_max is not larger than the corresponding
IPC sysctl parameters. That may require moving the limits to the
corresponding ipc_ids structure so that it can be used in ipc_idr_alloc().
First, I would disagree:
the sysctl limits specify how many objects can exist.
idr_max is the maximum index in the radix tree that can exist. There is
a hard limit of IPCMNI, but that's it.
But:
The name is wrong, I will rename the variable to idx_max
What is the point of comparing idr_max against RADIX_TREE_MAP_SIZE-1? Is
it for performance reason.
Let's assume you have only 1 ipc object, and you alloc/release that object.
At alloc time, ids->in_use is 0 -> idr_max 1 -> every object will end up
with idx=0.
This would defeat the whole purpose of using a cyclic alloc.
Thus: cycle over at least 63 ids -> 5 additional bits to avoid collisions.
--
Manfred
Re: [RFC, PATCH] ipc/util.c: use idr_alloc_cyclic() for ipc allocations
On 10/02/2018 12:19 PM, Manfred Spraul wrote:
> A bit related to the patch series that increases IPC_MNI:
>
> (User space) id reuse create the risk of data corruption:
>
> Process A: calls ipc function
> Process A: sleeps just at the beginning of the syscall
> Process B: Frees the ipc object (i.e.: calls ...ctl(IPC_RMID)
> Process B: Creates a new ipc object (i.e.: calls ...get())
>
> Process A: is woken up, and accesses the new object
>
> To reduce the probability that the new and the old object
> have the same id, the current implementation adds a
> sequence number to the index of the object in the idr tree.
>
> To further reduce the probability for a reuse, switch from
> idr_alloc to idr_alloc_cyclic.
>
> The patch cycles over at least RADIX_TREE_MAP_SIZE, i.e.
> if there is only a small number of objects, the accesses
> continue to be direct.
>
> As an option, this could be made dependent on the extended
> mode: In extended mode, cycle over e.g. at least 16k ids.
>
> Signed-off-by: Manfred Spraul
> ---
>
> Open questions:
> - Is there a significant performance advantage, especially
> there are many ipc ids?
> - Over how many ids should the code cycle always?
> - Further review remarks?
>
> ipc/util.c | 22 +-
> 1 file changed, 21 insertions(+), 1 deletion(-)
>
> diff --git a/ipc/util.c b/ipc/util.c
> index 0af05752969f..6f83841f6761 100644
> --- a/ipc/util.c
> +++ b/ipc/util.c
> @@ -216,10 +216,30 @@ static inline int ipc_idr_alloc(struct ipc_ids *ids,
> struct kern_ipc_perm *new)
>*/
>
> if (next_id < 0) { /* !CHECKPOINT_RESTORE or next_id is unset */
> + int idr_max;
> +
> new->seq = ids->seq++;
> if (ids->seq > IPCID_SEQ_MAX)
> ids->seq = 0;
> - idx = idr_alloc(>ipcs_idr, new, 0, 0, GFP_NOWAIT);
> +
> + /*
> + * If a user space visible id is reused, then this creates a
> + * risk for data corruption. To reduce the probability that
> + * a number is reduced, two approaches are used:
reduced -> reused?
> + * 1) the idr index is allocated cyclically.
> + * 2) the use space id is build by concatenating the
> + *internal idr index with a sequence number
> + * To avoid that both numbers have the same cycle time, try
> + * to set the size for the cyclic alloc to an odd number.
> + */
> + idr_max = ids->in_use*2+1;
> + if (idr_max < RADIX_TREE_MAP_SIZE-1)
> + idr_max = RADIX_TREE_MAP_SIZE-1;
> + if (idr_max > IPCMNI)
> + idr_max = IPCMNI;
> +
> + idx = idr_alloc_cyclic(>ipcs_idr, new, 0, idr_max,
> + GFP_NOWAIT);
> } else {
> new->seq = ipcid_to_seqx(next_id);
> idx = idr_alloc(>ipcs_idr, new, ipcid_to_idx(next_id),
Each of IPC components have their own sysctl parameters limiting the max
number of objects that can be allocated. With cyclic allocation, you
will have to make sure that idr_max is not larger than the corresponding
IPC sysctl parameters. That may require moving the limits to the
corresponding ipc_ids structure so that it can be used in ipc_idr_alloc().
What is the point of comparing idr_max against RADIX_TREE_MAP_SIZE-1? Is
it for performance reason.
Cheers,
Longman
Re: [RFC, PATCH] ipc/util.c: use idr_alloc_cyclic() for ipc allocations
On 10/02/2018 12:19 PM, Manfred Spraul wrote:
> A bit related to the patch series that increases IPC_MNI:
>
> (User space) id reuse create the risk of data corruption:
>
> Process A: calls ipc function
> Process A: sleeps just at the beginning of the syscall
> Process B: Frees the ipc object (i.e.: calls ...ctl(IPC_RMID)
> Process B: Creates a new ipc object (i.e.: calls ...get())
>
> Process A: is woken up, and accesses the new object
>
> To reduce the probability that the new and the old object
> have the same id, the current implementation adds a
> sequence number to the index of the object in the idr tree.
>
> To further reduce the probability for a reuse, switch from
> idr_alloc to idr_alloc_cyclic.
>
> The patch cycles over at least RADIX_TREE_MAP_SIZE, i.e.
> if there is only a small number of objects, the accesses
> continue to be direct.
>
> As an option, this could be made dependent on the extended
> mode: In extended mode, cycle over e.g. at least 16k ids.
>
> Signed-off-by: Manfred Spraul
> ---
>
> Open questions:
> - Is there a significant performance advantage, especially
> there are many ipc ids?
> - Over how many ids should the code cycle always?
> - Further review remarks?
>
> ipc/util.c | 22 +-
> 1 file changed, 21 insertions(+), 1 deletion(-)
>
> diff --git a/ipc/util.c b/ipc/util.c
> index 0af05752969f..6f83841f6761 100644
> --- a/ipc/util.c
> +++ b/ipc/util.c
> @@ -216,10 +216,30 @@ static inline int ipc_idr_alloc(struct ipc_ids *ids,
> struct kern_ipc_perm *new)
>*/
>
> if (next_id < 0) { /* !CHECKPOINT_RESTORE or next_id is unset */
> + int idr_max;
> +
> new->seq = ids->seq++;
> if (ids->seq > IPCID_SEQ_MAX)
> ids->seq = 0;
> - idx = idr_alloc(>ipcs_idr, new, 0, 0, GFP_NOWAIT);
> +
> + /*
> + * If a user space visible id is reused, then this creates a
> + * risk for data corruption. To reduce the probability that
> + * a number is reduced, two approaches are used:
reduced -> reused?
> + * 1) the idr index is allocated cyclically.
> + * 2) the use space id is build by concatenating the
> + *internal idr index with a sequence number
> + * To avoid that both numbers have the same cycle time, try
> + * to set the size for the cyclic alloc to an odd number.
> + */
> + idr_max = ids->in_use*2+1;
> + if (idr_max < RADIX_TREE_MAP_SIZE-1)
> + idr_max = RADIX_TREE_MAP_SIZE-1;
> + if (idr_max > IPCMNI)
> + idr_max = IPCMNI;
> +
> + idx = idr_alloc_cyclic(>ipcs_idr, new, 0, idr_max,
> + GFP_NOWAIT);
> } else {
> new->seq = ipcid_to_seqx(next_id);
> idx = idr_alloc(>ipcs_idr, new, ipcid_to_idx(next_id),
Each of IPC components have their own sysctl parameters limiting the max
number of objects that can be allocated. With cyclic allocation, you
will have to make sure that idr_max is not larger than the corresponding
IPC sysctl parameters. That may require moving the limits to the
corresponding ipc_ids structure so that it can be used in ipc_idr_alloc().
What is the point of comparing idr_max against RADIX_TREE_MAP_SIZE-1? Is
it for performance reason.
Cheers,
Longman
[RFC, PATCH] ipc/util.c: use idr_alloc_cyclic() for ipc allocations
A bit related to the patch series that increases IPC_MNI:
(User space) id reuse create the risk of data corruption:
Process A: calls ipc function
Process A: sleeps just at the beginning of the syscall
Process B: Frees the ipc object (i.e.: calls ...ctl(IPC_RMID)
Process B: Creates a new ipc object (i.e.: calls ...get())
Process A: is woken up, and accesses the new object
To reduce the probability that the new and the old object
have the same id, the current implementation adds a
sequence number to the index of the object in the idr tree.
To further reduce the probability for a reuse, switch from
idr_alloc to idr_alloc_cyclic.
The patch cycles over at least RADIX_TREE_MAP_SIZE, i.e.
if there is only a small number of objects, the accesses
continue to be direct.
As an option, this could be made dependent on the extended
mode: In extended mode, cycle over e.g. at least 16k ids.
Signed-off-by: Manfred Spraul
---
Open questions:
- Is there a significant performance advantage, especially
there are many ipc ids?
- Over how many ids should the code cycle always?
- Further review remarks?
ipc/util.c | 22 +-
1 file changed, 21 insertions(+), 1 deletion(-)
diff --git a/ipc/util.c b/ipc/util.c
index 0af05752969f..6f83841f6761 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -216,10 +216,30 @@ static inline int ipc_idr_alloc(struct ipc_ids *ids,
struct kern_ipc_perm *new)
*/
if (next_id < 0) { /* !CHECKPOINT_RESTORE or next_id is unset */
+ int idr_max;
+
new->seq = ids->seq++;
if (ids->seq > IPCID_SEQ_MAX)
ids->seq = 0;
- idx = idr_alloc(>ipcs_idr, new, 0, 0, GFP_NOWAIT);
+
+ /*
+* If a user space visible id is reused, then this creates a
+* risk for data corruption. To reduce the probability that
+* a number is reduced, two approaches are used:
+* 1) the idr index is allocated cyclically.
+* 2) the use space id is build by concatenating the
+*internal idr index with a sequence number
+* To avoid that both numbers have the same cycle time, try
+* to set the size for the cyclic alloc to an odd number.
+*/
+ idr_max = ids->in_use*2+1;
+ if (idr_max < RADIX_TREE_MAP_SIZE-1)
+ idr_max = RADIX_TREE_MAP_SIZE-1;
+ if (idr_max > IPCMNI)
+ idr_max = IPCMNI;
+
+ idx = idr_alloc_cyclic(>ipcs_idr, new, 0, idr_max,
+ GFP_NOWAIT);
} else {
new->seq = ipcid_to_seqx(next_id);
idx = idr_alloc(>ipcs_idr, new, ipcid_to_idx(next_id),
--
2.17.1
[RFC, PATCH] ipc/util.c: use idr_alloc_cyclic() for ipc allocations
A bit related to the patch series that increases IPC_MNI:
(User space) id reuse create the risk of data corruption:
Process A: calls ipc function
Process A: sleeps just at the beginning of the syscall
Process B: Frees the ipc object (i.e.: calls ...ctl(IPC_RMID)
Process B: Creates a new ipc object (i.e.: calls ...get())
Process A: is woken up, and accesses the new object
To reduce the probability that the new and the old object
have the same id, the current implementation adds a
sequence number to the index of the object in the idr tree.
To further reduce the probability for a reuse, switch from
idr_alloc to idr_alloc_cyclic.
The patch cycles over at least RADIX_TREE_MAP_SIZE, i.e.
if there is only a small number of objects, the accesses
continue to be direct.
As an option, this could be made dependent on the extended
mode: In extended mode, cycle over e.g. at least 16k ids.
Signed-off-by: Manfred Spraul
---
Open questions:
- Is there a significant performance advantage, especially
there are many ipc ids?
- Over how many ids should the code cycle always?
- Further review remarks?
ipc/util.c | 22 +-
1 file changed, 21 insertions(+), 1 deletion(-)
diff --git a/ipc/util.c b/ipc/util.c
index 0af05752969f..6f83841f6761 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -216,10 +216,30 @@ static inline int ipc_idr_alloc(struct ipc_ids *ids,
struct kern_ipc_perm *new)
*/
if (next_id < 0) { /* !CHECKPOINT_RESTORE or next_id is unset */
+ int idr_max;
+
new->seq = ids->seq++;
if (ids->seq > IPCID_SEQ_MAX)
ids->seq = 0;
- idx = idr_alloc(>ipcs_idr, new, 0, 0, GFP_NOWAIT);
+
+ /*
+* If a user space visible id is reused, then this creates a
+* risk for data corruption. To reduce the probability that
+* a number is reduced, two approaches are used:
+* 1) the idr index is allocated cyclically.
+* 2) the use space id is build by concatenating the
+*internal idr index with a sequence number
+* To avoid that both numbers have the same cycle time, try
+* to set the size for the cyclic alloc to an odd number.
+*/
+ idr_max = ids->in_use*2+1;
+ if (idr_max < RADIX_TREE_MAP_SIZE-1)
+ idr_max = RADIX_TREE_MAP_SIZE-1;
+ if (idr_max > IPCMNI)
+ idr_max = IPCMNI;
+
+ idx = idr_alloc_cyclic(>ipcs_idr, new, 0, idr_max,
+ GFP_NOWAIT);
} else {
new->seq = ipcid_to_seqx(next_id);
idx = idr_alloc(>ipcs_idr, new, ipcid_to_idx(next_id),
--
2.17.1
