[PATCH] Chardev checking of overlapping ranges is incorrect.

[PATCH] Chardev checking of overlapping ranges is incorrect.

[Linas Vepstas]

The current code in register_chrdev_region() attempts to check 
for overlapping regions of minor device numbers, but performs 
that check incorrectly. For example, if a device with minor 
numbers 128, 129, 130 is registered first, and a device with 
minor number 3,4,5 is registered later, then the later range
is incorrectly identified as "overlapping" (since 130>3), 
when clearly this is the wrong conclusion.

This patch fixes the overlap check to work correctly.

Signed-off-by: Signed-off-by: Linas Vepstas <linas@austin.ibm.com>

----
 fs/char_dev.c |    9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

Index: linux-2.6.18-rc3-mm2/fs/char_dev.c
===================================================================
--- linux-2.6.18-rc3-mm2.orig/fs/char_dev.c	2006-08-07 17:16:53.000000000 -0500
+++ linux-2.6.18-rc3-mm2/fs/char_dev.c	2006-08-07 17:18:59.000000000 -0500
@@ -93,6 +93,7 @@ __register_chrdev_region(unsigned int ma
 		}
 
 		if (i == 0) {
+printk ("duude egister_chrdev_regio no major !!\n");
 			ret = -EBUSY;
 			goto out;
 		}
@@ -113,9 +114,13 @@ __register_chrdev_region(unsigned int ma
 		     (((*cp)->baseminor >= baseminor) ||
 		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
 			break;
+
+	/* Check for overlap of minor ranges */
 	if (*cp && (*cp)->major == major &&
-	    (((*cp)->baseminor < baseminor + minorct) ||
-	     ((*cp)->baseminor + (*cp)->minorct > baseminor))) {
+	    ((((*cp)->baseminor <= baseminor) &&
+		   ((*cp)->baseminor + (*cp)->minorct >= baseminor)) ||
+	     (((*cp)->baseminor >= baseminor) &&
+	      ((*cp)->baseminor <= baseminor+minorct)))) {
 		ret = -EBUSY;
 		goto out;
 	}

Re: [PATCH] Chardev checking of overlapping ranges is incorrect.

[Linas Vepstas]

On Mon, Aug 07, 2006 at 05:55:55PM -0500, linas wrote:
> 
> The current code in register_chrdev_region() attempts to check 

A debug printk escaped with that patch. Here's the proper patch.
--linas

[PATCH] Chardev checking of overlapping ranges is incorrect.

The current code in register_chrdev_region() attempts to check 
for overlapping regions of minor device numbers, but performs 
that check incorrectly. For example, if a device with minor 
numbers 128, 129, 130 is registered first, and a device with 
minor number 3,4,5 is registered later, then the later range
is incorrectly identified as "overlapping" (since 130>3), 
when clearly this is the wrong conclusion.

This patch fixes the overlap check to work correctly.

Signed-off-by: Signed-off-by: Linas Vepstas <linas@austin.ibm.com>

----
 fs/char_dev.c |    8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

Index: linux-2.6.18-rc3-mm2/fs/char_dev.c
===================================================================
--- linux-2.6.18-rc3-mm2.orig/fs/char_dev.c	2006-08-07 17:16:53.000000000 -0500
+++ linux-2.6.18-rc3-mm2/fs/char_dev.c	2006-08-07 17:57:51.000000000 -0500
@@ -113,9 +113,13 @@ __register_chrdev_region(unsigned int ma
 		     (((*cp)->baseminor >= baseminor) ||
 		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
 			break;
+
+	/* Check for overlap of minor ranges */
 	if (*cp && (*cp)->major == major &&
-	    (((*cp)->baseminor < baseminor + minorct) ||
-	     ((*cp)->baseminor + (*cp)->minorct > baseminor))) {
+	    ((((*cp)->baseminor <= baseminor) &&
+		   ((*cp)->baseminor + (*cp)->minorct >= baseminor)) ||
+	     (((*cp)->baseminor >= baseminor) &&
+	      ((*cp)->baseminor <= baseminor+minorct)))) {
 		ret = -EBUSY;
 		goto out;
 	}

Re: [PATCH] Chardev checking of overlapping ranges is incorrect.

[Andrew Morton]

On Mon, 7 Aug 2006 17:55:55 -0500
linas@austin.ibm.com (Linas Vepstas) wrote:

> The current code in register_chrdev_region() attempts to check 
> for overlapping regions of minor device numbers, but performs 
> that check incorrectly. For example, if a device with minor 
> numbers 128, 129, 130 is registered first, and a device with 
> minor number 3,4,5 is registered later, then the later range
> is incorrectly identified as "overlapping" (since 130>3), 
> when clearly this is the wrong conclusion.
> 
> This patch fixes the overlap check to work correctly.


I yesterday merged the below.   Do you agree that it will fix the bug?


From: Amos Waterland <apw@us.ibm.com>

The code in __register_chrdev_region checks that if the driver wishing to
register has the same major as an existing driver the new minor range is
strictly less than the existing minor range.  However, it does not also
check that the new minor range is strictly greater than the existing minor
range.  That is, if driver X has registered with major=x and minor=0-3,
__register_chrdev_region will allow driver Y to register with major=x and
minor=1-4.

I came across this in the context of the Xen virtual console driver, but I
imagine it causes a problem for any driver with the same major number but
different minor numbers as a driver that has registered ahead of it.

Signed-off-by: Amos Waterland <apw@us.ibm.com>
Signed-off-by: Andrew Morton <akpm@osdl.org>
---


diff -puN fs/char_dev.c~fix-bounds-check-bug-in-__register_chrdev_region fs/char_dev.c
--- a/fs/char_dev.c~fix-bounds-check-bug-in-__register_chrdev_region
+++ a/fs/char_dev.c
@@ -109,10 +109,13 @@ __register_chrdev_region(unsigned int ma
 
 	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
 		if ((*cp)->major > major ||
-		    ((*cp)->major == major && (*cp)->baseminor >= baseminor))
+		    ((*cp)->major == major &&
+		     (((*cp)->baseminor >= baseminor) ||
+		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
 			break;
 	if (*cp && (*cp)->major == major &&
-	    (*cp)->baseminor < baseminor + minorct) {
+	    (((*cp)->baseminor < baseminor + minorct) ||
+	     ((*cp)->baseminor + (*cp)->minorct > baseminor))) {
 		ret = -EBUSY;
 		goto out;
 	}
_

Re: [PATCH] Chardev checking of overlapping ranges is incorrect.

[Amos Waterland]

On Mon, Aug 07, 2006 at 11:47:53PM -0700, Andrew Morton wrote:
> On Mon, 7 Aug 2006 17:55:55 -0500 linas@austin.ibm.com (Linas Vepstas) wrote:
> > The current code in register_chrdev_region() attempts to check 
> > for overlapping regions of minor device numbers, but performs 
> > that check incorrectly. For example, if a device with minor 
> > numbers 128, 129, 130 is registered first, and a device with 
> > minor number 3,4,5 is registered later, then the later range
> > is incorrectly identified as "overlapping" (since 130>3), 
> > when clearly this is the wrong conclusion.
> > 
> > This patch fixes the overlap check to work correctly.
> 
> I yesterday merged the below.   Do you agree that it will fix the bug?

Hi Andrew.  It does fix the original bug, but it introduces the bug that
Linas pointed out.  After looking at Linas' fix and finding an
off-by-one error in his code, I decided that we had better have a
stand-alone harness that we can put the various versions of the function
in to verify them without having to reboot a kernel.  The harness is
below the patch, with the test results of all five implementations.

Can you please back out my original patch and use this instead?  I have
run it through the test harness and I am much more confident in its
correctness.  Linas can you take a look at this and make sure you agree?

Signed-off-by: Amos Waterland <apw@us.ibm.com>

---

 char_dev.c |   28 +++++++++++++++++++++++-----
 1 file changed, 23 insertions(+), 5 deletions(-)

diff --git a/fs/char_dev.c b/fs/char_dev.c
index 3483d3c..e13157f 100644
--- a/fs/char_dev.c
+++ b/fs/char_dev.c
@@ -109,13 +109,31 @@ __register_chrdev_region(unsigned int ma
 
 	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
 		if ((*cp)->major > major ||
-		    ((*cp)->major == major && (*cp)->baseminor >= baseminor))
+		    ((*cp)->major == major && 
+		     (((*cp)->baseminor >= baseminor) ||
+		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
 			break;
-	if (*cp && (*cp)->major == major &&
-	    (*cp)->baseminor < baseminor + minorct) {
-		ret = -EBUSY;
-		goto out;
+
+	/* Check for overlapping minor ranges.  */
+	if (*cp && (*cp)->major == major) {
+		int old_min = (*cp)->baseminor;
+		int old_max = (*cp)->baseminor + (*cp)->minorct - 1;
+		int new_min = baseminor;
+		int new_max = baseminor + minorct - 1;
+
+		/* New driver overlaps from the left.  */
+		if (new_max >= old_min && new_max <= old_max) {
+			ret = -EBUSY;
+			goto out;
+		}
+
+		/* New driver overlaps from the right.  */
+		if (new_min <= old_max && new_min >= old_min) {
+			ret = -EBUSY;
+			goto out;
+		}
 	}
+
 	cd->next = *cp;
 	*cp = cd;
 	mutex_unlock(&chrdevs_lock);

---

$ gcc -g -O0 -Wall -Werror test-register.c -o test-register
$ ./test-register 
OVERLAPPING MINORS
  NAME     MIN    MAX  DRIVER   PASS
 linus:      0      3   first     OK
 linus:      1      4  second   FAIL
  amos:      0      3   first     OK
  amos:     -1     -1    NULL     OK
andrew:      0      3   first     OK
andrew:     -1     -1    NULL     OK
 linas:      0      3   first     OK
 linas:     -1     -1    NULL     OK
 amos2:      0      3   first     OK
 amos2:     -1     -1    NULL     OK

NON-OVERLAPPING MINORS
  NAME     MIN    MAX  DRIVER   PASS
 linus:    128    130   first     OK
 linus:      3      5  second     OK
  amos:    128    130   first     OK
  amos:     -1     -1    NULL   FAIL
andrew:    128    130   first     OK
andrew:     -1     -1    NULL   FAIL
 linas:    128    130   first     OK
 linas:      3      5  second     OK
 amos2:    128    130   first     OK
 amos2:      3      5  second     OK

CORNER CASES
  NAME     MIN    MAX  DRIVER   PASS
 linas:      0      2   first     OK
 linas:     10     12  second     OK
 linas:      5      7   third     OK
 linas:     -1     -1    NULL     OK
 linas:     -1     -1    NULL     OK
 linas:     -1     -1    NULL   FAIL
 linas:     13     13 seventh     OK
 amos2:      0      2   first     OK
 amos2:     10     12  second     OK
 amos2:      5      7   third     OK
 amos2:     -1     -1    NULL     OK
 amos2:     -1     -1    NULL     OK
 amos2:      9      9   sixth     OK
 amos2:     13     13 seventh     OK

---

/* Released under the GPL.  */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define CHRDEV_MAJOR_HASH_SIZE 255
#define GFP_KERNEL 0
#define ENOMEM 12
#define EBUSY 16
#define MAX_ERRNO 4095
#define SHOULD_PASS 0
#define SHOULD_FAIL 1
#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
#define IS_ERR_VALUE(x) ((x) >= (unsigned long)-MAX_ERRNO)

struct mutex { int count; } chrdevs_lock;
static struct char_device_struct {
        struct char_device_struct *next;
        unsigned int major;
        unsigned int baseminor;
        int minorct;
        char name[64];
} *chrdevs[CHRDEV_MAJOR_HASH_SIZE];

long IS_ERR(const void *ptr) { return IS_ERR_VALUE((unsigned long)ptr); }
static inline void *ERR_PTR(long error) { return (void *) error; }
void *kzalloc(size_t size, int flags) { return calloc(1, size); }
void kfree(const void *p) { return; }
int major_to_index(int index) { return index; }
void inline mutex_lock(struct mutex *lock) { return; }
void inline mutex_unlock(struct mutex *lock) { return; }

static struct char_device_struct *
linus__register_chrdev_region(unsigned int major, unsigned int baseminor,
  			      int minorct, const char *name)
{
	struct char_device_struct *cd, **cp;
	int ret = 0;
	int i;

	cd = kzalloc(sizeof(struct char_device_struct), GFP_KERNEL);
	if (cd == NULL)
		return ERR_PTR(-ENOMEM);

	mutex_lock(&chrdevs_lock);

	/* temporary */
	if (major == 0) {
		for (i = ARRAY_SIZE(chrdevs)-1; i > 0; i--) {
			if (chrdevs[i] == NULL)
				break;
		}

		if (i == 0) {
			ret = -EBUSY;
			goto out;
		}
		major = i;
		ret = major;
	}

	cd->major = major;
	cd->baseminor = baseminor;
	cd->minorct = minorct;
	strncpy(cd->name,name, 64);

	i = major_to_index(major);

	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
		if ((*cp)->major > major ||
		    ((*cp)->major == major && (*cp)->baseminor >= baseminor))
			break;
	if (*cp && (*cp)->major == major &&
	    (*cp)->baseminor < baseminor + minorct) {
		ret = -EBUSY;
		goto out;
	}
	cd->next = *cp;
	*cp = cd;
	mutex_unlock(&chrdevs_lock);
	return cd;
out:
	mutex_unlock(&chrdevs_lock);
	kfree(cd);
	return ERR_PTR(ret);
}

static struct char_device_struct *
amos__register_chrdev_region(unsigned int major, unsigned int baseminor,
  			     int minorct, const char *name)
{
	struct char_device_struct *cd, **cp;
	int ret = 0;
	int i;

	cd = kzalloc(sizeof(struct char_device_struct), GFP_KERNEL);
	if (cd == NULL)
		return ERR_PTR(-ENOMEM);

	mutex_lock(&chrdevs_lock);

	/* temporary */
	if (major == 0) {
		for (i = ARRAY_SIZE(chrdevs)-1; i > 0; i--) {
			if (chrdevs[i] == NULL)
				break;
		}

		if (i == 0) {
			ret = -EBUSY;
			goto out;
		}
		major = i;
		ret = major;
	}

	cd->major = major;
	cd->baseminor = baseminor;
	cd->minorct = minorct;
	strncpy(cd->name,name, 64);

	i = major_to_index(major);

	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
		if ((*cp)->major > major ||
		    ((*cp)->major == major &&
		     (((*cp)->baseminor >= baseminor) ||
		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
			break;
	if (*cp && (*cp)->major == major &&
	    (((*cp)->baseminor < baseminor + minorct) ||
	     ((*cp)->baseminor + (*cp)->minorct > baseminor))) {
		ret = -EBUSY;
		goto out;
	}
	cd->next = *cp;
	*cp = cd;
	mutex_unlock(&chrdevs_lock);
	return cd;
out:
	mutex_unlock(&chrdevs_lock);
	kfree(cd);
	return ERR_PTR(ret);
}

static struct char_device_struct *
andrew__register_chrdev_region(unsigned int major, unsigned int baseminor,
			       int minorct, const char *name)
{
	struct char_device_struct *cd, **cp;
	int ret = 0;
	int i;

	cd = kzalloc(sizeof(struct char_device_struct), GFP_KERNEL);
	if (cd == NULL)
		return ERR_PTR(-ENOMEM);

	mutex_lock(&chrdevs_lock);

	/* temporary */
	if (major == 0) {
		for (i = ARRAY_SIZE(chrdevs)-1; i > 0; i--) {
			if (chrdevs[i] == NULL)
				break;
		}

		if (i == 0) {
			ret = -EBUSY;
			goto out;
		}
		major = i;
		ret = major;
	}

	cd->major = major;
	cd->baseminor = baseminor;
	cd->minorct = minorct;
	strncpy(cd->name,name, 64);

	i = major_to_index(major);

	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
		if ((*cp)->major > major ||
		    ((*cp)->major == major &&
		     (((*cp)->baseminor >= baseminor) ||
		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
			break;
	if (*cp && (*cp)->major == major &&
	    (((*cp)->baseminor < baseminor + minorct) ||
	     ((*cp)->baseminor + (*cp)->minorct > baseminor))) {
		ret = -EBUSY;
		goto out;
	}
	cd->next = *cp;
	*cp = cd;
	mutex_unlock(&chrdevs_lock);
	return cd;
out:
	mutex_unlock(&chrdevs_lock);
	kfree(cd);
	return ERR_PTR(ret);
}

static struct char_device_struct *
linas__register_chrdev_region(unsigned int major, unsigned int baseminor,
			      int minorct, const char *name)
{
	struct char_device_struct *cd, **cp;
	int ret = 0;
	int i;

	cd = kzalloc(sizeof(struct char_device_struct), GFP_KERNEL);
	if (cd == NULL)
		return ERR_PTR(-ENOMEM);

	mutex_lock(&chrdevs_lock);

	/* temporary */
	if (major == 0) {
		for (i = ARRAY_SIZE(chrdevs)-1; i > 0; i--) {
			if (chrdevs[i] == NULL)
				break;
		}

		if (i == 0) {
			ret = -EBUSY;
			goto out;
		}
		major = i;
		ret = major;
	}

	cd->major = major;
	cd->baseminor = baseminor;
	cd->minorct = minorct;
	strncpy(cd->name,name, 64);

	i = major_to_index(major);

	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
		if ((*cp)->major > major ||
		    ((*cp)->major == major &&
		     (((*cp)->baseminor >= baseminor) ||
		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
			break;

	/* Check for overlap of minor ranges */
	if (*cp && (*cp)->major == major &&
	    ((((*cp)->baseminor <= baseminor) &&
		   ((*cp)->baseminor + (*cp)->minorct >= baseminor)) ||
	     (((*cp)->baseminor >= baseminor) &&
	      ((*cp)->baseminor <= baseminor+minorct)))) {
		ret = -EBUSY;
		goto out;
	}
	cd->next = *cp;
	*cp = cd;
	mutex_unlock(&chrdevs_lock);
	return cd;
out:
	mutex_unlock(&chrdevs_lock);
	kfree(cd);
	return ERR_PTR(ret);
}

static struct char_device_struct *
amos2__register_chrdev_region(unsigned int major, unsigned int baseminor,
  			      int minorct, const char *name)
{
	struct char_device_struct *cd, **cp;
	int ret = 0;
	int i;

	cd = kzalloc(sizeof(struct char_device_struct), GFP_KERNEL);
	if (cd == NULL)
		return ERR_PTR(-ENOMEM);

	mutex_lock(&chrdevs_lock);

	/* temporary */
	if (major == 0) {
		for (i = ARRAY_SIZE(chrdevs)-1; i > 0; i--) {
			if (chrdevs[i] == NULL)
				break;
		}

		if (i == 0) {
			ret = -EBUSY;
			goto out;
		}
		major = i;
		ret = major;
	}

	cd->major = major;
	cd->baseminor = baseminor;
	cd->minorct = minorct;
	strncpy(cd->name,name, 64);

	i = major_to_index(major);

	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
		if ((*cp)->major > major ||
		    ((*cp)->major == major && 
		     (((*cp)->baseminor >= baseminor) ||
		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
			break;

	/* Check for overlapping minor ranges.  */
	if (*cp && (*cp)->major == major) {
		int old_min = (*cp)->baseminor;
		int old_max = (*cp)->baseminor + (*cp)->minorct - 1;
		int new_min = baseminor;
		int new_max = baseminor + minorct - 1;

		/* New driver overlaps from the left.  */
		if (new_max >= old_min && new_max <= old_max) {
			ret = -EBUSY;
			goto out;
		}

		/* New driver overlaps from the right.  */
		if (new_min <= old_max && new_min >= old_min) {
			ret = -EBUSY;
			goto out;
		}
	}

	cd->next = *cp;
	*cp = cd;
	mutex_unlock(&chrdevs_lock);
	return cd;
out:
	mutex_unlock(&chrdevs_lock);
	kfree(cd);
	return ERR_PTR(ret);
}

void clear(struct char_device_struct **chrdevs)
{
	int i = 0;

	for (i = 0; i < CHRDEV_MAJOR_HASH_SIZE; i++)
		chrdevs[i] = 0x0;
}

void dump(const char *prefix, struct char_device_struct *cd, int should_fail)
{
	if (IS_ERR(cd)) {
		printf("%6s: %6i %6i %7s %6s\n", 
                       prefix, -1, -1, "NULL",
 		       should_fail ? "OK" : "FAIL");
		return;	
	}

	printf("%6s: %6i %6i %7s %6s\n", 
		prefix, cd->baseminor,  cd->baseminor + cd->minorct - 1, 
		cd->name, should_fail ? "FAIL" : "OK");
}

int main(int argc, char *argv[])
{
	struct char_device_struct *cd;

	/* First we test the case that a driver registers 0-3 and then
	 * another driver comes along and tries to take 1-4.  The second
	 * driver should be rejected.
	 */
	{
		printf("OVERLAPPING MINORS\n");
		printf("%6s  %6s %6s %7s %6s\n",
			"NAME", "MIN", "MAX", "DRIVER", "PASS");

		clear(chrdevs);
		cd = linus__register_chrdev_region(1, 0, 4, "first");
		dump("linus", cd, SHOULD_PASS);
		cd = linus__register_chrdev_region(1, 1, 4, "second");
		dump("linus", cd, SHOULD_FAIL);

		clear(chrdevs);
		cd = amos__register_chrdev_region(1, 0, 4, "first");
		dump("amos", cd, SHOULD_PASS);
		cd = amos__register_chrdev_region(1, 1, 4, "second");
		dump("amos", cd, SHOULD_FAIL);

		clear(chrdevs);
		cd = andrew__register_chrdev_region(1, 0, 4, "first");
		dump("andrew", cd, SHOULD_PASS);
		cd = andrew__register_chrdev_region(1, 1, 4, "second");
		dump("andrew", cd, SHOULD_FAIL);

		clear(chrdevs);
		cd = linas__register_chrdev_region(1, 0, 4, "first");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 1, 4, "second");
		dump("linas", cd, SHOULD_FAIL);

		clear(chrdevs);
		cd = amos2__register_chrdev_region(1, 0, 4, "first");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 1, 4, "second");
		dump("amos2", cd, SHOULD_FAIL);
	}

	/* Now we test the case that a driver registers 128-130 and then
	 * another driver comes along and asks for 3-5.  The second driver
	 * should NOT be rejected.
	 */
	{
		printf("\nNON-OVERLAPPING MINORS\n");
		printf("%6s  %6s %6s %7s %6s\n",
			"NAME", "MIN", "MAX", "DRIVER", "PASS");

		clear(chrdevs);
		cd = linus__register_chrdev_region(1, 128, 3, "first");
		dump("linus", cd, SHOULD_PASS);
		cd = linus__register_chrdev_region(1, 3, 3, "second");
		dump("linus", cd, SHOULD_PASS);

		clear(chrdevs);
		cd = amos__register_chrdev_region(1, 128, 3, "first");
		dump("amos", cd, SHOULD_PASS);
		cd = amos__register_chrdev_region(1, 3, 3, "second");
		dump("amos", cd, SHOULD_PASS);

		clear(chrdevs);
		cd = andrew__register_chrdev_region(1, 128, 3, "first");
		dump("andrew", cd, SHOULD_PASS);
		cd = andrew__register_chrdev_region(1, 3, 3, "second");
		dump("andrew", cd, SHOULD_PASS);

		clear(chrdevs);
		cd = linas__register_chrdev_region(1, 128, 3, "first");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 3, 3, "second");
		dump("linas", cd, SHOULD_PASS);

		clear(chrdevs);
		cd = amos2__register_chrdev_region(1, 128, 3, "first");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 3, 3, "second");
		dump("amos2", cd, SHOULD_PASS);
	}

	/* Since it looks like Linas' patch stacked on Amos' patch, which 
	 * is expressed as linus herein, is the correct solution, let's 
	 * hammer it with a few more corner cases.  We find that it has
	 * a false postive in the (10-12) + (9-9) case, so rewrite the code
	 * to make it clearer (called amos2 herein), which passes all the
	 * corner cases we know about.
	 */
	{
		printf("\nCORNER CASES\n");
		printf("%6s  %6s %6s %7s %6s\n",
			"NAME", "MIN", "MAX", "DRIVER", "PASS");

		clear(chrdevs);
		cd = linas__register_chrdev_region(1, 0, 3, "first");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 10, 3, "second");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 5, 3, "third");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 6, 3, "fourth");
		dump("linas", cd, SHOULD_FAIL);
		cd = linas__register_chrdev_region(1, 9, 2, "fifth");
		dump("linas", cd, SHOULD_FAIL);
		cd = linas__register_chrdev_region(1, 9, 1, "sixth");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 13, 1, "seventh");
		dump("linas", cd, SHOULD_PASS);

		clear(chrdevs);
		cd = amos2__register_chrdev_region(1, 0, 3, "first");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 10, 3, "second");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 5, 3, "third");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 6, 3, "fourth");
		dump("amos2", cd, SHOULD_FAIL);
		cd = amos2__register_chrdev_region(1, 9, 2, "fifth");
		dump("amos2", cd, SHOULD_FAIL);
		cd = amos2__register_chrdev_region(1, 9, 1, "sixth");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 13, 1, "seventh");
		dump("amos2", cd, SHOULD_PASS);
	}

	return 0;
}

---

Re: [PATCH] Chardev checking of overlapping ranges is incorrect.

[Linas Vepstas]

On Tue, Aug 08, 2006 at 04:52:58PM -0400, Amos Waterland wrote:
> On Mon, Aug 07, 2006 at 11:47:53PM -0700, Andrew Morton wrote:
> > On Mon, 7 Aug 2006 17:55:55 -0500 linas@austin.ibm.com (Linas Vepstas) wrote:
> > > The current code in register_chrdev_region() attempts to check 
> > > for overlapping regions of minor device numbers, but performs 
> > > that check incorrectly. For example, if a device with minor 
> > > numbers 128, 129, 130 is registered first, and a device with 
> > > minor number 3,4,5 is registered later, then the later range
> > > is incorrectly identified as "overlapping" (since 130>3), 
> > > when clearly this is the wrong conclusion.
> 
> Hi Andrew.  It does fix the original bug, but it introduces the bug that
> Linas pointed out.  After looking at Linas' fix and finding an
> off-by-one error in his code, 

Ooops

> Can you please back out my original patch and use this instead?  I have
> run it through the test harness and I am much more confident in its
> correctness.  Linas can you take a look at this and make sure you agree?

Actually, there's still a problem. An added device could still 
overlap with a previously added device and not be detected. 
We should keep the devices in order, and check that the region
fits in between the last and the next device.  So, for example,
the following will make the latest patch accept an invalid region:

First, add maj=x, minor=64-127
Next, add  maj=x, minor=0-63
Next, add  maj=x, minor=32-63

When going to insert the third chardev, the for-loop will catch 
the first elt in the chain, do the bounds-check, and add it
without complaint.  I'll try a patch shortly.

--linas

Re: [PATCH] Chardev checking of overlapping ranges is incorrect.

[Amos Waterland]

On Tue, Aug 08, 2006 at 04:33:31PM -0500, Linas Vepstas wrote:
> On Tue, Aug 08, 2006 at 04:52:58PM -0400, Amos Waterland wrote:
> > Hi Andrew.  It does fix the original bug, but it introduces the bug that
> > Linas pointed out.  After looking at Linas' fix and finding an
> > off-by-one error in his code, 
> 
> Ooops
> 
> > Can you please back out my original patch and use this instead?  I have
> > run it through the test harness and I am much more confident in its
> > correctness.  Linas can you take a look at this and make sure you agree?
> 
> Actually, there's still a problem. An added device could still 
> overlap with a previously added device and not be detected. 
> We should keep the devices in order, and check that the region
> fits in between the last and the next device.  So, for example,
> the following will make the latest patch accept an invalid region:
> 
> First, add maj=x, minor=64-127
> Next, add  maj=x, minor=0-63
> Next, add  maj=x, minor=32-63
> 
> When going to insert the third chardev, the for-loop will catch 
> the first elt in the chain, do the bounds-check, and add it
> without complaint.  I'll try a patch shortly.

Are you sure?  I do not see how that can happen.  Below is the harness
with your proposed sequence: the last patch that I posted properly
rejects it.

The harness is just a stand-alone C program, you can compile it on any
machine and test your sequence: maybe I misunderstood the minor ranges
you intended.

---

$  gcc -g -O0 -Wall -Werror test-register.c -o test-register
$ ./test-register 
OVERLAPPING MINORS
  NAME     MIN    MAX  DRIVER   PASS
 linus:      0      3   first     OK
 linus:      1      4  second   FAIL
  amos:      0      3   first     OK
  amos:     -1     -1    NULL     OK
andrew:      0      3   first     OK
andrew:     -1     -1    NULL     OK
 linas:      0      3   first     OK
 linas:     -1     -1    NULL     OK
 amos2:      0      3   first     OK
 amos2:     -1     -1    NULL     OK

NON-OVERLAPPING MINORS
  NAME     MIN    MAX  DRIVER   PASS
 linus:    128    130   first     OK
 linus:      3      5  second     OK
  amos:    128    130   first     OK
  amos:     -1     -1    NULL   FAIL
andrew:    128    130   first     OK
andrew:     -1     -1    NULL   FAIL
 linas:    128    130   first     OK
 linas:      3      5  second     OK
 amos2:    128    130   first     OK
 amos2:      3      5  second     OK

CORNER CASES
  NAME     MIN    MAX  DRIVER   PASS
 linas:      0      2   first     OK
 linas:     10     12  second     OK
 linas:      5      7   third     OK
 linas:     -1     -1    NULL     OK
 linas:     -1     -1    NULL     OK
 linas:     -1     -1    NULL   FAIL
 linas:     13     13 seventh     OK
 amos2:      0      2   first     OK
 amos2:     10     12  second     OK
 amos2:      5      7   third     OK
 amos2:     -1     -1    NULL     OK
 amos2:     -1     -1    NULL     OK
 amos2:      9      9   sixth     OK
 amos2:     13     13 seventh     OK
 amos2:     64    127  64-127     OK
 amos2:      0     63    0-63     OK
 amos2:     -1     -1    NULL     OK

---

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define CHRDEV_MAJOR_HASH_SIZE 255
#define GFP_KERNEL 0
#define ENOMEM 12
#define EBUSY 16
#define MAX_ERRNO 4095
#define SHOULD_PASS 0
#define SHOULD_FAIL 1
#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
#define IS_ERR_VALUE(x) ((x) >= (unsigned long)-MAX_ERRNO)

struct mutex { int count; } chrdevs_lock;
static struct char_device_struct {
        struct char_device_struct *next;
        unsigned int major;
        unsigned int baseminor;
        int minorct;
        char name[64];
} *chrdevs[CHRDEV_MAJOR_HASH_SIZE];

long IS_ERR(const void *ptr) { return IS_ERR_VALUE((unsigned long)ptr); }
static inline void *ERR_PTR(long error) { return (void *) error; }
void *kzalloc(size_t size, int flags) { return calloc(1, size); }
void kfree(const void *p) { return; }
int major_to_index(int index) { return index; }
void inline mutex_lock(struct mutex *lock) { return; }
void inline mutex_unlock(struct mutex *lock) { return; }

static struct char_device_struct *
linus__register_chrdev_region(unsigned int major, unsigned int baseminor,
  			      int minorct, const char *name)
{
	struct char_device_struct *cd, **cp;
	int ret = 0;
	int i;

	cd = kzalloc(sizeof(struct char_device_struct), GFP_KERNEL);
	if (cd == NULL)
		return ERR_PTR(-ENOMEM);

	mutex_lock(&chrdevs_lock);

	/* temporary */
	if (major == 0) {
		for (i = ARRAY_SIZE(chrdevs)-1; i > 0; i--) {
			if (chrdevs[i] == NULL)
				break;
		}

		if (i == 0) {
			ret = -EBUSY;
			goto out;
		}
		major = i;
		ret = major;
	}

	cd->major = major;
	cd->baseminor = baseminor;
	cd->minorct = minorct;
	strncpy(cd->name,name, 64);

	i = major_to_index(major);

	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
		if ((*cp)->major > major ||
		    ((*cp)->major == major && (*cp)->baseminor >= baseminor))
			break;
	if (*cp && (*cp)->major == major &&
	    (*cp)->baseminor < baseminor + minorct) {
		ret = -EBUSY;
		goto out;
	}
	cd->next = *cp;
	*cp = cd;
	mutex_unlock(&chrdevs_lock);
	return cd;
out:
	mutex_unlock(&chrdevs_lock);
	kfree(cd);
	return ERR_PTR(ret);
}

static struct char_device_struct *
amos__register_chrdev_region(unsigned int major, unsigned int baseminor,
  			     int minorct, const char *name)
{
	struct char_device_struct *cd, **cp;
	int ret = 0;
	int i;

	cd = kzalloc(sizeof(struct char_device_struct), GFP_KERNEL);
	if (cd == NULL)
		return ERR_PTR(-ENOMEM);

	mutex_lock(&chrdevs_lock);

	/* temporary */
	if (major == 0) {
		for (i = ARRAY_SIZE(chrdevs)-1; i > 0; i--) {
			if (chrdevs[i] == NULL)
				break;
		}

		if (i == 0) {
			ret = -EBUSY;
			goto out;
		}
		major = i;
		ret = major;
	}

	cd->major = major;
	cd->baseminor = baseminor;
	cd->minorct = minorct;
	strncpy(cd->name,name, 64);

	i = major_to_index(major);

	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
		if ((*cp)->major > major ||
		    ((*cp)->major == major &&
		     (((*cp)->baseminor >= baseminor) ||
		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
			break;
	if (*cp && (*cp)->major == major &&
	    (((*cp)->baseminor < baseminor + minorct) ||
	     ((*cp)->baseminor + (*cp)->minorct > baseminor))) {
		ret = -EBUSY;
		goto out;
	}
	cd->next = *cp;
	*cp = cd;
	mutex_unlock(&chrdevs_lock);
	return cd;
out:
	mutex_unlock(&chrdevs_lock);
	kfree(cd);
	return ERR_PTR(ret);
}

static struct char_device_struct *
andrew__register_chrdev_region(unsigned int major, unsigned int baseminor,
			       int minorct, const char *name)
{
	struct char_device_struct *cd, **cp;
	int ret = 0;
	int i;

	cd = kzalloc(sizeof(struct char_device_struct), GFP_KERNEL);
	if (cd == NULL)
		return ERR_PTR(-ENOMEM);

	mutex_lock(&chrdevs_lock);

	/* temporary */
	if (major == 0) {
		for (i = ARRAY_SIZE(chrdevs)-1; i > 0; i--) {
			if (chrdevs[i] == NULL)
				break;
		}

		if (i == 0) {
			ret = -EBUSY;
			goto out;
		}
		major = i;
		ret = major;
	}

	cd->major = major;
	cd->baseminor = baseminor;
	cd->minorct = minorct;
	strncpy(cd->name,name, 64);

	i = major_to_index(major);

	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
		if ((*cp)->major > major ||
		    ((*cp)->major == major &&
		     (((*cp)->baseminor >= baseminor) ||
		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
			break;
	if (*cp && (*cp)->major == major &&
	    (((*cp)->baseminor < baseminor + minorct) ||
	     ((*cp)->baseminor + (*cp)->minorct > baseminor))) {
		ret = -EBUSY;
		goto out;
	}
	cd->next = *cp;
	*cp = cd;
	mutex_unlock(&chrdevs_lock);
	return cd;
out:
	mutex_unlock(&chrdevs_lock);
	kfree(cd);
	return ERR_PTR(ret);
}

static struct char_device_struct *
linas__register_chrdev_region(unsigned int major, unsigned int baseminor,
			      int minorct, const char *name)
{
	struct char_device_struct *cd, **cp;
	int ret = 0;
	int i;

	cd = kzalloc(sizeof(struct char_device_struct), GFP_KERNEL);
	if (cd == NULL)
		return ERR_PTR(-ENOMEM);

	mutex_lock(&chrdevs_lock);

	/* temporary */
	if (major == 0) {
		for (i = ARRAY_SIZE(chrdevs)-1; i > 0; i--) {
			if (chrdevs[i] == NULL)
				break;
		}

		if (i == 0) {
			ret = -EBUSY;
			goto out;
		}
		major = i;
		ret = major;
	}

	cd->major = major;
	cd->baseminor = baseminor;
	cd->minorct = minorct;
	strncpy(cd->name,name, 64);

	i = major_to_index(major);

	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
		if ((*cp)->major > major ||
		    ((*cp)->major == major &&
		     (((*cp)->baseminor >= baseminor) ||
		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
			break;

	/* Check for overlap of minor ranges */
	if (*cp && (*cp)->major == major &&
	    ((((*cp)->baseminor <= baseminor) &&
		   ((*cp)->baseminor + (*cp)->minorct >= baseminor)) ||
	     (((*cp)->baseminor >= baseminor) &&
	      ((*cp)->baseminor <= baseminor+minorct)))) {
		ret = -EBUSY;
		goto out;
	}
	cd->next = *cp;
	*cp = cd;
	mutex_unlock(&chrdevs_lock);
	return cd;
out:
	mutex_unlock(&chrdevs_lock);
	kfree(cd);
	return ERR_PTR(ret);
}

static struct char_device_struct *
amos2__register_chrdev_region(unsigned int major, unsigned int baseminor,
  			      int minorct, const char *name)
{
	struct char_device_struct *cd, **cp;
	int ret = 0;
	int i;

	cd = kzalloc(sizeof(struct char_device_struct), GFP_KERNEL);
	if (cd == NULL)
		return ERR_PTR(-ENOMEM);

	mutex_lock(&chrdevs_lock);

	/* temporary */
	if (major == 0) {
		for (i = ARRAY_SIZE(chrdevs)-1; i > 0; i--) {
			if (chrdevs[i] == NULL)
				break;
		}

		if (i == 0) {
			ret = -EBUSY;
			goto out;
		}
		major = i;
		ret = major;
	}

	cd->major = major;
	cd->baseminor = baseminor;
	cd->minorct = minorct;
	strncpy(cd->name,name, 64);

	i = major_to_index(major);

	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
		if ((*cp)->major > major ||
		    ((*cp)->major == major && 
		     (((*cp)->baseminor >= baseminor) ||
		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
			break;

	/* Check for overlapping minor ranges.  */
	if (*cp && (*cp)->major == major) {
		int old_min = (*cp)->baseminor;
		int old_max = (*cp)->baseminor + (*cp)->minorct - 1;
		int new_min = baseminor;
		int new_max = baseminor + minorct - 1;

		/* New driver overlaps from the left.  */
		if (new_max >= old_min && new_max <= old_max) {
			ret = -EBUSY;
			goto out;
		}

		/* New driver overlaps from the right.  */
		if (new_min <= old_max && new_min >= old_min) {
			ret = -EBUSY;
			goto out;
		}
	}

	cd->next = *cp;
	*cp = cd;
	mutex_unlock(&chrdevs_lock);
	return cd;
out:
	mutex_unlock(&chrdevs_lock);
	kfree(cd);
	return ERR_PTR(ret);
}

void clear(struct char_device_struct **chrdevs)
{
	int i = 0;

	for (i = 0; i < CHRDEV_MAJOR_HASH_SIZE; i++)
		chrdevs[i] = 0x0;
}

void dump(const char *prefix, struct char_device_struct *cd, int should_fail)
{
	if (IS_ERR(cd)) {
		printf("%6s: %6i %6i %7s %6s\n", 
                       prefix, -1, -1, "NULL",
 		       should_fail ? "OK" : "FAIL");
		return;	
	}

	printf("%6s: %6i %6i %7s %6s\n", 
		prefix, cd->baseminor,  cd->baseminor + cd->minorct - 1, 
		cd->name, should_fail ? "FAIL" : "OK");
}

int main(int argc, char *argv[])
{
	struct char_device_struct *cd;

	/* First we test the case that a driver registers 0-3 and then
	 * another driver comes along and tries to take 1-4.  The second
	 * driver should be rejected.
	 */
	{
		printf("OVERLAPPING MINORS\n");
		printf("%6s  %6s %6s %7s %6s\n",
			"NAME", "MIN", "MAX", "DRIVER", "PASS");

		clear(chrdevs);
		cd = linus__register_chrdev_region(1, 0, 4, "first");
		dump("linus", cd, SHOULD_PASS);
		cd = linus__register_chrdev_region(1, 1, 4, "second");
		dump("linus", cd, SHOULD_FAIL);

		clear(chrdevs);
		cd = amos__register_chrdev_region(1, 0, 4, "first");
		dump("amos", cd, SHOULD_PASS);
		cd = amos__register_chrdev_region(1, 1, 4, "second");
		dump("amos", cd, SHOULD_FAIL);

		clear(chrdevs);
		cd = andrew__register_chrdev_region(1, 0, 4, "first");
		dump("andrew", cd, SHOULD_PASS);
		cd = andrew__register_chrdev_region(1, 1, 4, "second");
		dump("andrew", cd, SHOULD_FAIL);

		clear(chrdevs);
		cd = linas__register_chrdev_region(1, 0, 4, "first");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 1, 4, "second");
		dump("linas", cd, SHOULD_FAIL);

		clear(chrdevs);
		cd = amos2__register_chrdev_region(1, 0, 4, "first");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 1, 4, "second");
		dump("amos2", cd, SHOULD_FAIL);
	}

	/* Now we test the case that a driver registers 128-130 and then
	 * another driver comes along and asks for 3-5.  The second driver
	 * should NOT be rejected.
	 */
	{
		printf("\nNON-OVERLAPPING MINORS\n");
		printf("%6s  %6s %6s %7s %6s\n",
			"NAME", "MIN", "MAX", "DRIVER", "PASS");

		clear(chrdevs);
		cd = linus__register_chrdev_region(1, 128, 3, "first");
		dump("linus", cd, SHOULD_PASS);
		cd = linus__register_chrdev_region(1, 3, 3, "second");
		dump("linus", cd, SHOULD_PASS);

		clear(chrdevs);
		cd = amos__register_chrdev_region(1, 128, 3, "first");
		dump("amos", cd, SHOULD_PASS);
		cd = amos__register_chrdev_region(1, 3, 3, "second");
		dump("amos", cd, SHOULD_PASS);

		clear(chrdevs);
		cd = andrew__register_chrdev_region(1, 128, 3, "first");
		dump("andrew", cd, SHOULD_PASS);
		cd = andrew__register_chrdev_region(1, 3, 3, "second");
		dump("andrew", cd, SHOULD_PASS);

		clear(chrdevs);
		cd = linas__register_chrdev_region(1, 128, 3, "first");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 3, 3, "second");
		dump("linas", cd, SHOULD_PASS);

		clear(chrdevs);
		cd = amos2__register_chrdev_region(1, 128, 3, "first");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 3, 3, "second");
		dump("amos2", cd, SHOULD_PASS);
	}

	/* Since it looks like Linas' patch stacked on Amos' patch, which 
	 * is expressed as linus herein, is the correct solution, let's 
	 * hammer it with a few more corner cases.  We find that it has
	 * a false postive in the (10-12) + (9-9) case, so rewrite the code
	 * to make it clearer (called amos2 herein), which passes all the
	 * corner cases we know about.
	 */
	{
		printf("\nCORNER CASES\n");
		printf("%6s  %6s %6s %7s %6s\n",
			"NAME", "MIN", "MAX", "DRIVER", "PASS");

		clear(chrdevs);
		cd = linas__register_chrdev_region(1, 0, 3, "first");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 10, 3, "second");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 5, 3, "third");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 6, 3, "fourth");
		dump("linas", cd, SHOULD_FAIL);
		cd = linas__register_chrdev_region(1, 9, 2, "fifth");
		dump("linas", cd, SHOULD_FAIL);
		cd = linas__register_chrdev_region(1, 9, 1, "sixth");
		dump("linas", cd, SHOULD_PASS);
		cd = linas__register_chrdev_region(1, 13, 1, "seventh");
		dump("linas", cd, SHOULD_PASS);

		clear(chrdevs);
		cd = amos2__register_chrdev_region(1, 0, 3, "first");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 10, 3, "second");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 5, 3, "third");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 6, 3, "fourth");
		dump("amos2", cd, SHOULD_FAIL);
		cd = amos2__register_chrdev_region(1, 9, 2, "fifth");
		dump("amos2", cd, SHOULD_FAIL);
		cd = amos2__register_chrdev_region(1, 9, 1, "sixth");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 13, 1, "seventh");
		dump("amos2", cd, SHOULD_PASS);

		clear(chrdevs);
		cd = amos2__register_chrdev_region(1, 64, 64, "64-127");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 0, 64, "0-63");
		dump("amos2", cd, SHOULD_PASS);
		cd = amos2__register_chrdev_region(1, 32, 32, "32-63");
		dump("amos2", cd, SHOULD_FAIL);
	}

	return 0;
}

---

Re: [PATCH] Chardev checking of overlapping ranges is incorrect.

[Linas Vepstas]

On Tue, Aug 08, 2006 at 06:20:41PM -0400, Amos Waterland wrote:
> > 
> > Actually, there's still a problem. An added device could still 
> > overlap with a previously added device and not be detected. 
> > We should keep the devices in order, and check that the region
> > fits in between the last and the next device.  So, for example,
> > the following will make the latest patch accept an invalid region:
> > 
> > First, add maj=x, minor=64-127
> > Next, add  maj=x, minor=0-63
> > Next, add  maj=x, minor=32-63
> > 
> > When going to insert the third chardev, the for-loop will catch 
> > the first elt in the chain, do the bounds-check, and add it
> > without complaint.  I'll try a patch shortly.
> 
> Are you sure?  I do not see how that can happen.  

On closer examination, indeed, this cannot happen.  I was presuming an
order dependence when there wasn't one. I am now older and wiser: 
although I had to write my own patch to become that. 

I beleive there's still an off-by-one error:
Presume list contains
  maj=x, minor=0-64  (and nothing else)
Go to add
  maj=x, minor=64-127

The conditions to break out of the for-loop are never met, so
the loop terminates naturally, with *cp null, (or with a higher 
major number), and the new interval is added when it should not 
have been.

I beleive the patch below avoids this.  Perhaps it might be 
easier to understand? I have not run your test harness on it.

Signed-off-by: Linas Vepstas <linas@austin.ibm.com>

----
 fs/char_dev.c |   34 ++++++++++++++++++++++++++--------
 1 file changed, 26 insertions(+), 8 deletions(-)

Index: linux-2.6.18-rc3-mm2/fs/char_dev.c
===================================================================
--- linux-2.6.18-rc3-mm2.orig/fs/char_dev.c	2006-08-08 16:52:47.000000000 -0500
+++ linux-2.6.18-rc3-mm2/fs/char_dev.c	2006-08-08 20:07:35.000000000 -0500
@@ -76,6 +76,7 @@ __register_chrdev_region(unsigned int ma
 			   int minorct, const char *name)
 {
 	struct char_device_struct *cd, **cp;
+	int prev_top, curr_top;
 	int ret = 0;
 	int i;
 
@@ -107,18 +108,35 @@ __register_chrdev_region(unsigned int ma
 
 	i = major_to_index(major);
 
-	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
-		if ((*cp)->major > major ||
-		    ((*cp)->major == major &&
-		     (((*cp)->baseminor >= baseminor) ||
-		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
+	prev_top = -1;
+	curr_top = baseminor + minorct - 1;
+
+	/* Insert into list, with sort order of low to high. */
+	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next) {
+		if ((*cp)->major > major)
 			break;
-	if (*cp && (*cp)->major == major &&
-	    (((*cp)->baseminor < baseminor + minorct) ||
-	     ((*cp)->baseminor + (*cp)->minorct > baseminor))) {
+		if((*cp)->major == major) {
+
+			/* If it fits between this and the previous, accept it. */
+			if (((*cp)->baseminor > curr_top) &&
+				 (prev_top < (int) baseminor))
+				break;
+
+			/* If it overlaps this interval, reject it */
+			prev_top = (*cp)->baseminor + (*cp)->minorct - 1;
+			if (prev_top >= (int) baseminor) {
+				ret = -EBUSY;
+				goto out;
+			}
+		}
+	}
+
+	/* If it overlaps this interval, reject it */
+	if ((*cp) && (curr_top >= (*cp)->baseminor)) {
 		ret = -EBUSY;
 		goto out;
 	}
+
 	cd->next = *cp;
 	*cp = cd;
 	mutex_unlock(&chrdevs_lock);

Re: [PATCH] Chardev checking of overlapping ranges is incorrect.

[Amos Waterland]

On Tue, Aug 08, 2006 at 08:15:19PM -0500, Linas Vepstas wrote:
> On Tue, Aug 08, 2006 at 06:20:41PM -0400, Amos Waterland wrote:
> > Are you sure?  I do not see how that can happen.  
> 
> On closer examination, indeed, this cannot happen.  I was presuming an
> order dependence when there wasn't one. I am now older and wiser: 
> although I had to write my own patch to become that. 
> 
> I beleive there's still an off-by-one error:
> Presume list contains
>   maj=x, minor=0-64  (and nothing else)
> Go to add
>   maj=x, minor=64-127
> 
> The conditions to break out of the for-loop are never met, so
> the loop terminates naturally, with *cp null, (or with a higher 
> major number), and the new interval is added when it should not 
> have been.

The condition to break out of the for-loop is in fact met, specifically
the check that: (*cp)->baseminor + (*cp)->minorct > baseminor.  In your
example, this is: 0 + 65 > 64.  This is determined by inspection and
verified by putting your proposed sequence through the harness.

Andrew, I believe this is ready for submission.

---

The code in __register_chrdev_region checks that if the driver wishing
to register has the same major as an existing driver the new minor range
is strictly less than the existing minor range.  However, it does not
also check that the new minor range is strictly greater than the
existing minor range.  That is, if driver X has registered with major=x
and minor=0-3, __register_chrdev_region will allow driver Y to register
with major=x and minor=1-4.  

Signed-off-by: Amos Waterland <apw@us.ibm.com>

---

 char_dev.c |   28 +++++++++++++++++++++++-----
 1 file changed, 23 insertions(+), 5 deletions(-)

diff --git a/fs/char_dev.c b/fs/char_dev.c
index 3483d3c..e13157f 100644
--- a/fs/char_dev.c
+++ b/fs/char_dev.c
@@ -109,13 +109,31 @@ __register_chrdev_region(unsigned int ma
 
 	for (cp = &chrdevs[i]; *cp; cp = &(*cp)->next)
 		if ((*cp)->major > major ||
-		    ((*cp)->major == major && (*cp)->baseminor >= baseminor))
+		    ((*cp)->major == major && 
+		     (((*cp)->baseminor >= baseminor) ||
+		      ((*cp)->baseminor + (*cp)->minorct > baseminor))))
 			break;
-	if (*cp && (*cp)->major == major &&
-	    (*cp)->baseminor < baseminor + minorct) {
-		ret = -EBUSY;
-		goto out;
+
+	/* Check for overlapping minor ranges.  */
+	if (*cp && (*cp)->major == major) {
+		int old_min = (*cp)->baseminor;
+		int old_max = (*cp)->baseminor + (*cp)->minorct - 1;
+		int new_min = baseminor;
+		int new_max = baseminor + minorct - 1;
+
+		/* New driver overlaps from the left.  */
+		if (new_max >= old_min && new_max <= old_max) {
+			ret = -EBUSY;
+			goto out;
+		}
+
+		/* New driver overlaps from the right.  */
+		if (new_min <= old_max && new_min >= old_min) {
+			ret = -EBUSY;
+			goto out;
+		}
 	}
+
 	cd->next = *cp;
 	*cp = cd;
 	mutex_unlock(&chrdevs_lock);