Re: [RFC][PATCH 1/6] Storing ipcs into radix trees
Hi, On Friday 08 June 2007, Nadia Derbey wrote: > Ingo Oeser wrote: > > ... together with this means 4*256 -> 1k of precious stack space used. > > Please consider either lowering IPCS_MAX_SCAN_ENTRIES or kmalloc() that. > You're completely right, but trying to lower the extraction size, I'm > afraid this will have an impact on performances. > > Here are the results of a small test I did: I have run ctxbench on both > the 256 and and 16 entries versions > > 1) 256 entries: > 42523679 itterations in 300.005423 seconds = 141743/sec > 2) 16 entries: > 41774255 itterations in 300.005334 seconds = 139245/sec So that is around 1.8% in a benchmark. Not bad, if one considers, that this is an expensive syncronisation primitive anyway (and thus shouldn't dominate any real workload). At least _much_ better than possible stack underflow :-) BTW: You forgot to include measurements with the unmodified code as it is in Linus' tree now. They woule be a nice data point here. > Will try with a dynamic allocation. But than you have an additional error path or have to sleep until memory becomes available. Maybe try doubling IPCS_MAX_SCAN_ENTRIES - until the performance impact is in the noise - is simpler. Up to 64 seems acceptable. Best Regards Ingo Oeser - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC][PATCH 1/6] Storing ipcs into radix trees
Ingo Oeser wrote:
Hi Nadia,
good to see someone is pounding this old beast again :-)
On Thursday 07 June 2007, [EMAIL PROTECTED] wrote:
Index: linux-2.6.21/ipc/util.h
===
--- linux-2.6.21.orig/ipc/util.h2007-06-07 11:00:30.0 +0200
+++ linux-2.6.21/ipc/util.h 2007-06-07 11:07:22.0 +0200
@@ -13,6 +13,8 @@
#define USHRT_MAX 0x
#define SEQ_MULTIPLIER (IPCMNI)
+#define IPCS_MAX_SCAN_ENTRIES 256
That ...
Index: linux-2.6.21/ipc/util.c
===
--- linux-2.6.21.orig/ipc/util.c2007-06-07 11:00:30.0 +0200
+++ linux-2.6.21/ipc/util.c 2007-06-07 11:29:43.0 +0200
@@ -252,72 +241,94 @@ void __init ipc_init_proc_interface(cons
* @key: The key to find
*
* Requires ipc_ids.mutex locked.
- * Returns the identifier if found or -1 if not.
+ * Returns the LOCKED pointer to the ipc structure if found or NULL
+ * if not.
+ * If key is found ipc contains its ipc structure
*/
-int ipc_findkey(struct ipc_ids* ids, key_t key)
+struct kern_ipc_perm *ipc_findkey(struct ipc_ids *ids, key_t key)
{
- int id;
- struct kern_ipc_perm* p;
- int max_id = ids->max_id;
+ struct kern_ipc_perm *ipc;
+ struct kern_ipc_perm *ipcs[IPCS_MAX_SCAN_ENTRIES];
... together with this means 4*256 -> 1k of precious stack space used.
Please consider either lowering IPCS_MAX_SCAN_ENTRIES or kmalloc() that.
Same problem with your third patch called
"Changing the loops on a single ipcid into radix_tree_gang_lookup() calls"
If you cannot sleep, try to lower that constant (e.g. 16-32).
The current users use much smaller numbers.
If you can sleep and performance goes down after lowering that constant,
try to kmalloc these arrays (since kmalloc() of that small amount
should succeed easily).
Regards
Ingo Oeser
Ingo,
You're completely right, but trying to lower the extraction size, I'm
afraid this will have an impact on performances.
Here are the results of a small test I did: I have run ctxbench on both
the 256 and and 16 entries versions
1) 256 entries:
[EMAIL PROTECTED] ctxbench-1.9]# echo 1000 > /proc/sys/kernel/msgmni
[EMAIL PROTECTED] ctxbench-1.9]# ./ctx -m -t300
Context switching benchmark v1.17
Using message queue for IPC control
Max iterations:0 (zero = no limit)
Max runtime (sec): 300 (zero = no limit)
42523679 itterations in 300.005423 seconds = 141743/sec
2) 16 entries:
[EMAIL PROTECTED] ctxbench-1.9]# echo 1000 > /proc/sys/kernel/msgmni
[EMAIL PROTECTED] ctxbench-1.9]# ./ctx -m -t300
Context switching benchmark v1.17
Using message queue for IPC control
Max iterations:0 (zero = no limit)
Max runtime (sec): 300 (zero = no limit)
41774255 itterations in 300.005334 seconds = 139245/sec
Will try with a dynamic allocation.
Regards,
Nadia
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC][PATCH 1/6] Storing ipcs into radix trees
Hi Nadia,
good to see someone is pounding this old beast again :-)
On Thursday 07 June 2007, [EMAIL PROTECTED] wrote:
> Index: linux-2.6.21/ipc/util.h
> ===
> --- linux-2.6.21.orig/ipc/util.h 2007-06-07 11:00:30.0 +0200
> +++ linux-2.6.21/ipc/util.h 2007-06-07 11:07:22.0 +0200
> @@ -13,6 +13,8 @@
> #define USHRT_MAX 0x
> #define SEQ_MULTIPLIER (IPCMNI)
>
> +#define IPCS_MAX_SCAN_ENTRIES 256
That ...
> Index: linux-2.6.21/ipc/util.c
> ===
> --- linux-2.6.21.orig/ipc/util.c 2007-06-07 11:00:30.0 +0200
> +++ linux-2.6.21/ipc/util.c 2007-06-07 11:29:43.0 +0200
> @@ -252,72 +241,94 @@ void __init ipc_init_proc_interface(cons
> * @key: The key to find
> *
> * Requires ipc_ids.mutex locked.
> - * Returns the identifier if found or -1 if not.
> + * Returns the LOCKED pointer to the ipc structure if found or NULL
> + * if not.
> + * If key is found ipc contains its ipc structure
> */
>
> -int ipc_findkey(struct ipc_ids* ids, key_t key)
> +struct kern_ipc_perm *ipc_findkey(struct ipc_ids *ids, key_t key)
> {
> - int id;
> - struct kern_ipc_perm* p;
> - int max_id = ids->max_id;
> + struct kern_ipc_perm *ipc;
> + struct kern_ipc_perm *ipcs[IPCS_MAX_SCAN_ENTRIES];
... together with this means 4*256 -> 1k of precious stack space used.
Please consider either lowering IPCS_MAX_SCAN_ENTRIES or kmalloc() that.
Same problem with your third patch called
"Changing the loops on a single ipcid into radix_tree_gang_lookup() calls"
If you cannot sleep, try to lower that constant (e.g. 16-32).
The current users use much smaller numbers.
If you can sleep and performance goes down after lowering that constant,
try to kmalloc these arrays (since kmalloc() of that small amount
should succeed easily).
Regards
Ingo Oeser
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[RFC][PATCH 1/6] Storing ipcs into radix trees
[PATCH 01/06]
This patch introduces ipcs storage into radix trees. The main changes are:
. This ipc_ids structure is changed: the entries array is changed into a
root radix_tree structure.
. The grow_ary() routine is removed: it is not needed anymore when adding
an ipc structure, due to radix trees introduction
Signed-off-by: Nadia Derbey <[EMAIL PROTECTED]>
---
include/linux/ipc.h |1
include/linux/msg.h |1
include/linux/sem.h |1
include/linux/shm.h |1
ipc/msg.c | 64 ++---
ipc/sem.c | 63 ++--
ipc/shm.c | 63 ++--
ipc/util.c | 253
ipc/util.h | 30 +-
9 files changed, 248 insertions(+), 229 deletions(-)
Index: linux-2.6.21/ipc/util.h
===
--- linux-2.6.21.orig/ipc/util.h2007-06-07 11:00:30.0 +0200
+++ linux-2.6.21/ipc/util.h 2007-06-07 11:07:22.0 +0200
@@ -13,6 +13,8 @@
#define USHRT_MAX 0x
#define SEQ_MULTIPLIER (IPCMNI)
+#define IPCS_MAX_SCAN_ENTRIES 256
+
void sem_init (void);
void msg_init (void);
void shm_init (void);
@@ -25,19 +27,15 @@ void sem_exit_ns(struct ipc_namespace *n
void msg_exit_ns(struct ipc_namespace *ns);
void shm_exit_ns(struct ipc_namespace *ns);
-struct ipc_id_ary {
- int size;
- struct kern_ipc_perm *p[0];
-};
-
struct ipc_ids {
int in_use;
int max_id;
+ int first_free;
unsigned short seq;
unsigned short seq_max;
struct mutex mutex;
- struct ipc_id_ary nullentry;
- struct ipc_id_ary* entries;
+ struct radix_tree_root id_tree;
+ DECLARE_BITMAP(in_use_bitmap, IPCMNI);
};
struct seq_file;
@@ -46,7 +44,7 @@ struct seq_file;
#else
#define __ipc_init __init
#endif
-void __ipc_init ipc_init_ids(struct ipc_ids *ids, int size);
+void __ipc_init ipc_init_ids(struct ipc_ids *);
#ifdef CONFIG_PROC_FS
void __init ipc_init_proc_interface(const char *path, const char *header,
int ids, int (*show)(struct seq_file *, void *));
@@ -59,8 +57,8 @@ void __init ipc_init_proc_interface(cons
#define IPC_SHM_IDS2
/* must be called with ids->mutex acquired.*/
-int ipc_findkey(struct ipc_ids* ids, key_t key);
-int ipc_addid(struct ipc_ids* ids, struct kern_ipc_perm* new, int size);
+struct kern_ipc_perm *ipc_findkey(struct ipc_ids *, key_t);
+int ipc_addid(struct ipc_ids *, struct kern_ipc_perm *, int);
/* must be called with both locks acquired. */
struct kern_ipc_perm* ipc_rmid(struct ipc_ids* ids, int id);
@@ -83,18 +81,6 @@ void* ipc_rcu_alloc(int size);
void ipc_rcu_getref(void *ptr);
void ipc_rcu_putref(void *ptr);
-static inline void __ipc_fini_ids(struct ipc_ids *ids,
- struct ipc_id_ary *entries)
-{
- if (entries != &ids->nullentry)
- ipc_rcu_putref(entries);
-}
-
-static inline void ipc_fini_ids(struct ipc_ids *ids)
-{
- __ipc_fini_ids(ids, ids->entries);
-}
-
struct kern_ipc_perm* ipc_get(struct ipc_ids* ids, int id);
struct kern_ipc_perm* ipc_lock(struct ipc_ids* ids, int id);
void ipc_lock_by_ptr(struct kern_ipc_perm *ipcp);
Index: linux-2.6.21/ipc/util.c
===
--- linux-2.6.21.orig/ipc/util.c2007-06-07 11:00:30.0 +0200
+++ linux-2.6.21/ipc/util.c 2007-06-07 11:29:43.0 +0200
@@ -33,6 +33,7 @@
#include
#include
#include
+#include
#include
@@ -51,6 +52,8 @@ struct ipc_namespace init_ipc_ns = {
},
};
+static void ipc_set_max_id(struct ipc_ids *);
+
#ifdef CONFIG_IPC_NS
static struct ipc_namespace *clone_ipc_ns(struct ipc_namespace *old_ns)
{
@@ -172,23 +175,18 @@ __initcall(ipc_init);
/**
* ipc_init_ids- initialise IPC identifiers
* @ids: Identifier set
- * @size: Number of identifiers
*
- * Given a size for the ipc identifier range (limited below IPCMNI)
- * set up the sequence range to use then allocate and initialise the
- * array itself.
+ * Set up the sequence range to use for the ipc identifier range (limited
+ * below IPCMNI) then initialise the ids radix tree.
*/
-void __ipc_init ipc_init_ids(struct ipc_ids* ids, int size)
+void __ipc_init ipc_init_ids(struct ipc_ids *ids)
{
- int i;
-
mutex_init(&ids->mutex);
- if(size > IPCMNI)
- size = IPCMNI;
ids->in_use = 0;
ids->max_id = -1;
+ ids->first_free = 0;
ids->seq = 0;
{
int seq_limit = INT_MAX/SEQ_MULTIPLIER;
@@ -198,17 +196,8 @@ void __ipc_init ipc_init_ids(struct ipc_
ids->seq_max = seq_limit;
}
- ids->entries = ipc_rcu_alloc(sizeof(struct kern_ipc_perm *)*size +
-sizeof(struct ipc_id_ary));
-
- if(ids->entries == NULL) {
- prin
