[RFC PATCH 1/2] Shrink compat_ioctl.c

[RFC PATCH 1/2] Shrink compat_ioctl.c

[Matt Mackall]

I'm throwing this out untested as I don't have a mixed 64/32 system
handy at the moment.

compat_ioctl: shrink structures

Initially, compat_ioctl.c has a ~18k table of translated ioctls.
Each table entry is 24 bytes but we can shrink this to 16:

- use short table indexes rather than a pointer for .next values
- use unsigned ints for cmd numbers (they're 32-bit ioctls, after all)

In addition, there's a 2k hash table that we can do away with simply
by hashifying the main table in place at init time.

This saves about 6k data and 2k BSS.

diff -r f6d1daaf90b2 -r b055e64aea17 fs/compat_ioctl.c
--- a/fs/compat_ioctl.c	Mon Sep 29 17:28:28 2008 -0500
+++ b/fs/compat_ioctl.c	Mon Sep 29 17:28:41 2008 -0500
@@ -1825,21 +1825,21 @@
 					unsigned long, struct file *);
 
 struct ioctl_trans {
-	unsigned long cmd;
 	ioctl_trans_handler_t handler;
-	struct ioctl_trans *next;
+	unsigned int cmd;
+	unsigned short next;
 };
 
 #define HANDLE_IOCTL(cmd,handler) \
-	{ (cmd), (ioctl_trans_handler_t)(handler) },
+	{ (ioctl_trans_handler_t)(handler), (cmd)},
 
 /* pointer to compatible structure or no argument */
 #define COMPATIBLE_IOCTL(cmd) \
-	{ (cmd), do_ioctl32_pointer },
+	{ do_ioctl32_pointer, (cmd) },
 
 /* argument is an unsigned long integer, not a pointer */
 #define ULONG_IOCTL(cmd) \
-	{ (cmd), (ioctl_trans_handler_t)sys_ioctl },
+	{ (ioctl_trans_handler_t)sys_ioctl, (cmd) },
 
 /* ioctl should not be warned about even if it's not implemented.
    Valid reasons to use this:
@@ -1850,7 +1850,7 @@
    Most other reasons are not valid. */
 #define IGNORE_IOCTL(cmd) COMPATIBLE_IOCTL(cmd)
 
-static struct ioctl_trans ioctl_start[] = {
+static struct ioctl_trans ioctl_table[] = {
 /* compatible ioctls first */
 COMPATIBLE_IOCTL(0x4B50)   /* KDGHWCLK - not in the kernel, but don't complain */
 COMPATIBLE_IOCTL(0x4B51)   /* KDSHWCLK - not in the kernel, but don't complain */
@@ -2728,10 +2728,9 @@
 #endif
 };
 
-#define IOCTL_HASHSIZE 256
-static struct ioctl_trans *ioctl32_hash_table[IOCTL_HASHSIZE];
+#define IOCTL_HASHSIZE 256 /* must be less than table size */
 
-static inline unsigned long ioctl32_hash(unsigned long cmd)
+static inline unsigned int ioctl32_hash(unsigned int cmd)
 {
 	return (((cmd >> 6) ^ (cmd >> 4) ^ cmd)) % IOCTL_HASHSIZE;
 }
@@ -2770,7 +2769,7 @@
 {
 	struct file *filp;
 	int error = -EBADF;
-	struct ioctl_trans *t;
+	int t;
 	int fput_needed;
 
 	filp = fget_light(fd, &fput_needed);
@@ -2815,8 +2814,8 @@
 		break;
 	}
 
-	for (t = ioctl32_hash_table[ioctl32_hash(cmd)]; t; t = t->next) {
-		if (t->cmd == cmd)
+	for (t = ioctl32_hash(cmd); t >= 0; t = ioctl_table[t].next) {
+		if (ioctl_table[t].cmd == cmd)
 			goto found_handler;
 	}
 
@@ -2837,9 +2836,9 @@
 	goto out_fput;
 
  found_handler:
-	if (t->handler) {
+	if (ioctl_table[t].handler) {
 		lock_kernel();
-		error = t->handler(fd, cmd, arg, filp);
+		error = ioctl_table[t].handler(fd, cmd, arg, filp);
 		unlock_kernel();
 		goto out_fput;
 	}
@@ -2852,34 +2851,25 @@
 	return error;
 }
 
-static void ioctl32_insert_translation(struct ioctl_trans *trans)
-{
-	unsigned long hash;
-	struct ioctl_trans *t;
-
-	hash = ioctl32_hash (trans->cmd);
-	if (!ioctl32_hash_table[hash])
-		ioctl32_hash_table[hash] = trans;
-	else {
-		t = ioctl32_hash_table[hash];
-		while (t->next)
-			t = t->next;
-		trans->next = NULL;
-		t->next = trans;
-	}
-}
-
 static int __init init_sys32_ioctl(void)
 {
 	int i;
+	unsigned long hash;
+	struct ioctl_trans t;
 
-	for (i = 0; i < ARRAY_SIZE(ioctl_start); i++) {
-		if (ioctl_start[i].next) {
-			printk("ioctl translation %d bad\n",i);
-			return -1;
-		}
+	/* hash-order table in-place */
+	for (i = 0; i < ARRAY_SIZE(ioctl_table); i++) {
+		hash = ioctl32_hash(ioctl_table[i].cmd);
+		t = ioctl_table[hash];
+		ioctl_table[hash] = ioctl_table[i];
+		ioctl_table[i] = t;
+	}
 
-		ioctl32_insert_translation(&ioctl_start[i]);
+	/* link entries outside of hash area */
+	for (i = IOCTL_HASHSIZE; i < ARRAY_SIZE(ioctl_table); i++) {
+		hash = ioctl32_hash(ioctl_table[i].cmd);
+		ioctl_table[i].next = ioctl_table[hash].next;
+		ioctl_table[hash].next = i;
 	}
 	return 0;
 }


-- 
Mathematics is the supreme nostalgia of our time.

[RFC PATCH 2/2] Shrink compat_ioctl.c

[Matt Mackall]

compat-ioctl: further compactify table

Most entries use the basic compat handler, which means for most
entries it's redundant. Rather than store a handler for each entry, we
split the table so that there are two entry types, the 'basic stuff'
and the handler pointer.

At build time, the table is sorted so that each entry with a handler
pointer is two entries, handler pointer first. At init time we re-sort
the list so that all the handler pointers are at the end of the table
and each basic entry tracks the index that the corresponding handler
pointer is at.

This cuts the size of most entries in half, so the table goes from
~12k to ~7k.

diff -r b055e64aea17 -r 6841f3ce32be fs/compat_ioctl.c
--- a/fs/compat_ioctl.c	Mon Sep 29 17:28:41 2008 -0500
+++ b/fs/compat_ioctl.c	Mon Sep 29 17:28:44 2008 -0500
@@ -1825,21 +1825,26 @@
 					unsigned long, struct file *);
 
 struct ioctl_trans {
-	ioctl_trans_handler_t handler;
-	unsigned int cmd;
-	unsigned short next;
+	union {
+		struct {
+			unsigned int cmd;
+			short handle; /* index of entry containing fn ptr */
+			short next; /* index of next entry in hash chain */
+		} e;
+		ioctl_trans_handler_t handler;
+	} u;
 };
 
-#define HANDLE_IOCTL(cmd,handler) \
-	{ (ioctl_trans_handler_t)(handler), (cmd)},
+#define HANDLE_IOCTL(command, fn) \
+	{{ .handler = (ioctl_trans_handler_t)(fn) }},	\
+	{{ .e = { .cmd = (command), .handle = 1 }}},
+
+/* argument is an unsigned long integer, not a pointer */
+#define ULONG_IOCTL(cmd) HANDLE_IOCTL(cmd, sys_ioctl)
 
 /* pointer to compatible structure or no argument */
-#define COMPATIBLE_IOCTL(cmd) \
-	{ do_ioctl32_pointer, (cmd) },
-
-/* argument is an unsigned long integer, not a pointer */
-#define ULONG_IOCTL(cmd) \
-	{ (ioctl_trans_handler_t)sys_ioctl, (cmd) },
+#define COMPATIBLE_IOCTL(command) \
+	{{ .e = { .cmd = (command) }}},
 
 /* ioctl should not be warned about even if it's not implemented.
    Valid reasons to use this:
@@ -2814,8 +2819,8 @@
 		break;
 	}
 
-	for (t = ioctl32_hash(cmd); t >= 0; t = ioctl_table[t].next) {
-		if (ioctl_table[t].cmd == cmd)
+	for (t = ioctl32_hash(cmd); t >= 0; t = ioctl_table[t].u.e.next) {
+		if (ioctl_table[t].u.e.cmd == cmd)
 			goto found_handler;
 	}
 
@@ -2836,12 +2841,13 @@
 	goto out_fput;
 
  found_handler:
-	if (ioctl_table[t].handler) {
-		lock_kernel();
-		error = ioctl_table[t].handler(fd, cmd, arg, filp);
-		unlock_kernel();
-		goto out_fput;
-	}
+	lock_kernel();
+	if (ioctl_table[t].u.e.handle)
+		error = ioctl_table[ioctl_table[t].u.e.handle].u.handler(fd, cmd, arg, filp);
+	else
+		error = do_ioctl32_pointer(fd, cmd, arg, filp);
+	unlock_kernel();
+	goto out_fput;
 
  do_ioctl:
 	error = do_vfs_ioctl(filp, fd, cmd, arg);
@@ -2853,23 +2859,38 @@
 
 static int __init init_sys32_ioctl(void)
 {
-	int i;
+	int i, top;
 	unsigned long hash;
 	struct ioctl_trans t;
 
+	/* walk table backward moving handler entries to the end */
+	top = ARRAY_SIZE(ioctl_table) - 1;
+	for (i = top; i >= 0; i--)
+		if (ioctl_table[i].u.e.handle) {
+			/* next entry down is a handler pointer, swap to top */
+			t = ioctl_table[top];
+			ioctl_table[top] = ioctl_table[i - 1];
+			ioctl_table[i - 1] = t;
+			/* fix up handle index for current entry */
+			ioctl_table[i].u.e.handle = top;
+			/* update top and skip next entry */
+			top--;
+			i--;
+		}
+
 	/* hash-order table in-place */
-	for (i = 0; i < ARRAY_SIZE(ioctl_table); i++) {
-		hash = ioctl32_hash(ioctl_table[i].cmd);
+	for (i = 0; i <= top; i++) {
+		hash = ioctl32_hash(ioctl_table[i].u.e.cmd);
 		t = ioctl_table[hash];
 		ioctl_table[hash] = ioctl_table[i];
 		ioctl_table[i] = t;
 	}
 
 	/* link entries outside of hash area */
-	for (i = IOCTL_HASHSIZE; i < ARRAY_SIZE(ioctl_table); i++) {
-		hash = ioctl32_hash(ioctl_table[i].cmd);
-		ioctl_table[i].next = ioctl_table[hash].next;
-		ioctl_table[hash].next = i;
+	for (i = IOCTL_HASHSIZE; i <= top; i++) {
+		hash = ioctl32_hash(ioctl_table[i].u.e.cmd);
+		ioctl_table[i].u.e.next = ioctl_table[hash].u.e.next;
+		ioctl_table[hash].u.e.next = i;
 	}
 	return 0;
 }

-- 
Mathematics is the supreme nostalgia of our time.

Re: [RFC PATCH 1/2] Shrink compat_ioctl.c

[Matt Mackall]

On Tue, 2008-09-30 at 01:38 +0200, Andi Kleen wrote:
> On Mon, Sep 29, 2008 at 06:27:10PM -0500, Matt Mackall wrote:
> > I'm throwing this out untested as I don't have a mixed 64/32 system
> > handy at the moment.
> 
> Makes sense (assuming it works, haven't tested)
> 
> > compat_ioctl: shrink structures
> > 
> > Initially, compat_ioctl.c has a ~18k table of translated ioctls.
> > Each table entry is 24 bytes but we can shrink this to 16:
> > 
> > - use short table indexes rather than a pointer for .next values
> > - use unsigned ints for cmd numbers (they're 32-bit ioctls, after all)
> > 
> > In addition, there's a 2k hash table that we can do away with simply
> > by hashifying the main table in place at init time.
> 
> You mean by using a closed hash?

The original hash table was 256 pointers into the main table. I simply
rearrange the main table so the first 256 entries have an appropriate
hash. Basically:

for i in len(table):
  h = hash(table[i])
  swap(table[i], table[hash])

At the end of this loop, table[0:256] will contain an appropriate table
entry, if it exists. So no secondary table is needed.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [RFC PATCH 1/2] Shrink compat_ioctl.c

[Andi Kleen]

On Mon, Sep 29, 2008 at 06:27:10PM -0500, Matt Mackall wrote:
> I'm throwing this out untested as I don't have a mixed 64/32 system
> handy at the moment.

Makes sense (assuming it works, haven't tested)

> compat_ioctl: shrink structures
> 
> Initially, compat_ioctl.c has a ~18k table of translated ioctls.
> Each table entry is 24 bytes but we can shrink this to 16:
> 
> - use short table indexes rather than a pointer for .next values
> - use unsigned ints for cmd numbers (they're 32-bit ioctls, after all)
> 
> In addition, there's a 2k hash table that we can do away with simply
> by hashifying the main table in place at init time.

You mean by using a closed hash?

Acked-by: Andi Kleen <ak@linux.intel.com>

-Andi