[PATCH] change pts allocation behaviour in

[PATCH] change pts allocation behaviour in

[Steve Young]

  Hello,

  Here is a patch to change the way ptses are allocated.  It applies against
2.6.6-rc3.  Basically it tries to humour old glibc by always obtaining a pts
in the range of 0-255 first.  However, if that fails, then it will search the
higher ranges.  The net effect should be that old glibc users won't notice
problems until they try and get more than 256 concurrent ptses (which would
break under the first-fit scheme anyway), yet we reduce the average number of 
iterations required to find a new pts when a lot are in use.  In the very
worst case of only one pts available, this still performs no worse than
the either the old or more recent allocation schemes.

  Thanks,
  Steve.

diff -ur linux-2.6.5-virgin/drivers/char/tty_io.c linux-2.6.5-deflowered/drivers/char/tty_io.c
--- linux-2.6.5-virgin/drivers/char/tty_io.c	2004-05-07 02:07:45.486690184 -0600
+++ linux-2.6.5-deflowered/drivers/char/tty_io.c	2004-05-07 01:57:19.447753528 -0600
@@ -1362,14 +1362,24 @@
 #ifdef CONFIG_UNIX98_PTYS
 	if (device == MKDEV(TTYAUX_MAJOR,2)) {
 		/* find a device that is not in use. */
-		static int next_ptmx_dev = 0;
+		static int next_ptmx_dev = MAX_PREFERRED_PTY;
 		retval = -1;
 		driver = ptm_driver;
+		/* first, try for a pty < 256 for old glibc that doesn't support
+		 * larger pts numbers */
+		for (index = 0; index < MAX_PREFERRED_PTY && driver->refcount < pty_limit; index++) {
+			if (!init_dev(driver, index, &tty)) 
+				goto ptmx_found;
+		}
+		/* nothing below MAX_PREFERRED_PTY, try something higher */
 		while (driver->refcount < pty_limit) {
 			index = next_ptmx_dev;
 			next_ptmx_dev = (next_ptmx_dev+1) % driver->num;
-			if (!init_dev(driver, index, &tty))
+			if (!next_ptmx_dev) 
+				next_ptmx_dev = MAX_PREFERRED_PTY;
+			if (!init_dev(driver, index, &tty)) {
 				goto ptmx_found; /* ok! */
+			}
 		}
 		return -EIO; /* no free ptys */
 	ptmx_found:
diff -ur linux-2.6.5-virgin/include/linux/tty.h linux-2.6.5-deflowered/include/linux/tty.h
--- linux-2.6.5-virgin/include/linux/tty.h	2004-05-07 02:07:47.386401384 -0600
+++ linux-2.6.5-deflowered/include/linux/tty.h	2004-05-07 01:43:55.000000000 -0600
@@ -35,6 +35,7 @@
 #define NR_UNIX98_PTY_DEFAULT	4096      /* Default maximum for Unix98 ptys */
 #define NR_UNIX98_PTY_MAX	(1 << MINORBITS) /* Absolute limit */
 #define NR_LDISCS		16
+#define MAX_PREFERRED_PTY	256			/* we prefer to allocate ptys beneath this number */
 
 /*
  * These are set up by the setup-routine at boot-time:

Re: [PATCH] change pts allocation behaviour in tty_io.c, v2

[Steve Young]

On Fri, May 07, 2004 at 02:42:42AM -0600, Steve Young wrote:
>   Here is a patch to change the way ptses are allocated.  It applies against
> 2.6.6-rc3.  Basically it tries to humour old glibc by always obtaining a pts

  I realized this won't properly cope when driver->num < MAX_PREFERRED_PTY.
Use this patch instead.  I've tested it on my box.

  Thanks,
  Steve.

diff -ur linux-2.6.5-virgin/drivers/char/tty_io.c linux-2.6.5-eviltron/drivers/char/tty_io.c
--- linux-2.6.5-virgin/drivers/char/tty_io.c	2004-05-07 03:39:25.085624064 -0600
+++ linux-2.6.5-eviltron/drivers/char/tty_io.c	2004-05-07 03:37:51.697821168 -0600
@@ -1362,14 +1362,25 @@
 #ifdef CONFIG_UNIX98_PTYS
 	if (device == MKDEV(TTYAUX_MAJOR,2)) {
 		/* find a device that is not in use. */
-		static int next_ptmx_dev = 0;
+		static int next_ptmx_dev = MAX_PREFERRED_PTY;
 		retval = -1;
 		driver = ptm_driver;
-		while (driver->refcount < pty_limit) {
-			index = next_ptmx_dev;
-			next_ptmx_dev = (next_ptmx_dev+1) % driver->num;
-			if (!init_dev(driver, index, &tty))
-				goto ptmx_found; /* ok! */
+		/* first, try and allocate a pty < 256 for old glibc */
+		for (index = 0; index < MAX_PREFERRED_PTY && driver->refcount < pty_limit && index < driver->num; index++) {
+			if (!init_dev(driver, index, &tty)) 
+				goto ptmx_found;
+		}
+		/* nothing below MAX_PREFERRED_PTY, try something higher, unless
+		 * we've already run out of options */
+		if (index != driver->num) {
+			while (driver->refcount < pty_limit) {
+				index = next_ptmx_dev;
+				next_ptmx_dev = (next_ptmx_dev+1) % driver->num;
+				if (!next_ptmx_dev) 
+					next_ptmx_dev = MAX_PREFERRED_PTY;
+				if (!init_dev(driver, index, &tty)) 
+					goto ptmx_found; /* ok! */
+			}
 		}
 		return -EIO; /* no free ptys */
 	ptmx_found:

diff -ur linux-2.6.5-virgin/include/linux/tty.h linux-2.6.5-eviltron/include/linux/tty.h
--- linux-2.6.5-virgin/include/linux/tty.h	2004-05-07 03:39:26.953340128 -0600
+++ linux-2.6.5-eviltron/include/linux/tty.h	2004-05-07 01:43:55.000000000 -0600
@@ -35,6 +35,7 @@
 #define NR_UNIX98_PTY_DEFAULT	4096      /* Default maximum for Unix98 ptys */
 #define NR_UNIX98_PTY_MAX	(1 << MINORBITS) /* Absolute limit */
 #define NR_LDISCS		16
+#define MAX_PREFERRED_PTY	256			/* we prefer to allocate ptys beneath this number */
 
 /*
  * These are set up by the setup-routine at boot-time:

Re: [PATCH] change pts allocation behaviour in

[Andrew Morton]

Steve Young <sdyoung@vt220.org> wrote:
>
>   Here is a patch to change the way ptses are allocated.  It applies against
>  2.6.6-rc3.  Basically it tries to humour old glibc by always obtaining a pts
>  in the range of 0-255 first.  However, if that fails, then it will search the
>  higher ranges. 

Wouldn't we be better off with plain old first-fit-from-zero?

Re: [PATCH] change pts allocation behaviour in

[Steve Young]

On Fri, May 07, 2004 at 04:14:42AM -0700, Andrew Morton wrote:
> >  in the range of 0-255 first.  However, if that fails, then it will search the
> >  higher ranges. 
> 
> Wouldn't we be better off with plain old first-fit-from-zero?

  In the typical case where <256 pts devices are allocated, you're right that
there will be no benefit over the first-fit-from-zero implementation.  However 
when there are a lot of pts devices in use, the algorithm used for searching 
the high ranges ought to generally find a new pts in fewer iterations than
just linearly searching from 0 to the maximum pts number.  For example, if a 
system allocates 5000 ptses in a row, when it goes to look for a new one with 
first-fit-from-zero, that's 5001 iterations to find an available pts.  Using
the patch though, it will only take 257 iterations.  As time goes on and 
ptses get allocated and freed the situation becomes a bit murkier, but 
the patch should still cut down the number of iterations required to find
a free pts.

  Thanks,
  Steve.

Re: [PATCH] change pts allocation behaviour in

[Andrew Morton]

Steve Young <sdyoung@vt220.org> wrote:
>
> On Fri, May 07, 2004 at 04:14:42AM -0700, Andrew Morton wrote:
> > >  in the range of 0-255 first.  However, if that fails, then it will search the
> > >  higher ranges. 
> > 
> > Wouldn't we be better off with plain old first-fit-from-zero?
> 
>   In the typical case where <256 pts devices are allocated, you're right that
> there will be no benefit over the first-fit-from-zero implementation.  However 
> when there are a lot of pts devices in use, the algorithm used for searching 
> the high ranges ought to generally find a new pts in fewer iterations than
> just linearly searching from 0 to the maximum pts number.  For example, if a 
> system allocates 5000 ptses in a row, when it goes to look for a new one with 
> first-fit-from-zero, that's 5001 iterations to find an available pts.

first-fit-from-zero does not imply linear search!  The idr.c code provides
a logarithmic-time search.