lkml.org 
[lkml]   [2006]   [Aug]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    SubjectRe: [PATCH] Chardev checking of overlapping ranges is incorrect.
    From
    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 majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2006-08-09 00:23    [W:0.052 / U:0.372 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site