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;
}
---
-
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/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
