[PATCH] fixes for linked list bugs in block I/O code

[PATCH] fixes for linked list bugs in block I/O code

[Dave Peterson]

I found a couple of small linked list bugs in __make_request() in
drivers/block/ll_rw_blk.c.  The bugs exist in both kernels
2.4.20 and 2.5.69.  Therefore I have made patches for both
kernels.  The problem is that when inserting a new buffer_head
into the linked list of buffer_head structures maintained by
"struct request", the b_reqnext field is not initialized.

-Dave Peterson
 dsp@llnl.gov


========== START OF 2.4.20 PATCH FOR drivers/block/ll_rw_blk.c ===========
--- ll_rw_blk.c.old     Wed May  7 15:54:58 2003
+++ ll_rw_blk.c.new     Wed May  7 15:58:07 2003
@@ -973,6 +973,7 @@
                                insert_here = &req->queue;
                                break;
                        }
+                       bh->b_reqnext = req->bhtail->b_reqnext;
                        req->bhtail->b_reqnext = bh;
                        req->bhtail = bh;
                        req->nr_sectors = req->hard_nr_sectors += count;
@@ -1061,6 +1062,7 @@
        req->waiting = NULL;
        req->bh = bh;
        req->bhtail = bh;
+       bh->b_reqnext = NULL;
        req->rq_dev = bh->b_rdev;
        req->start_time = jiffies;
        req_new_io(req, 0, count);
========== END OF 2.4.20 PATCH FOR drivers/block/ll_rw_blk.c =============


========== START OF 2.5.69 PATCH FOR drivers/block/ll_rw_blk.c ===========
--- ll_rw_blk.c.old     Wed May  7 15:55:18 2003
+++ ll_rw_blk.c.new     Wed May  7 16:01:56 2003
@@ -1721,6 +1721,7 @@
                                break;
                        }

+                       bio->bi_next = req->biotail->bi_next;
                        req->biotail->bi_next = bio;
                        req->biotail = bio;
                        req->nr_sectors = req->hard_nr_sectors += nr_sectors;
@@ -1811,6 +1812,7 @@
        req->buffer = bio_data(bio);    /* see ->buffer comment above */
        req->waiting = NULL;
        req->bio = req->biotail = bio;
+       bio->bi_next = NULL;
        req->rq_disk = bio->bi_bdev->bd_disk;
        req->start_time = jiffies;
        add_request(q, req, insert_here);
========== END OF 2.5.69 PATCH FOR drivers/block/ll_rw_blk.c =============

Re: [PATCH] fixes for linked list bugs in block I/O code

[Bartlomiej Zolnierkiewicz]

On Wed, 7 May 2003, Dave Peterson wrote:

> I found a couple of small linked list bugs in __make_request() in
> drivers/block/ll_rw_blk.c.  The bugs exist in both kernels
> 2.4.20 and 2.5.69.  Therefore I have made patches for both
> kernels.  The problem is that when inserting a new buffer_head
> into the linked list of buffer_head structures maintained by
> "struct request", the b_reqnext field is not initialized.
>
> -Dave Peterson
>  dsp@llnl.gov
>
>
> ========== START OF 2.4.20 PATCH FOR drivers/block/ll_rw_blk.c ===========
> --- ll_rw_blk.c.old     Wed May  7 15:54:58 2003
> +++ ll_rw_blk.c.new     Wed May  7 15:58:07 2003
> @@ -973,6 +973,7 @@
>                                 insert_here = &req->queue;
>                                 break;
>                         }
> +                       bh->b_reqnext = req->bhtail->b_reqnext;
>                         req->bhtail->b_reqnext = bh;
>                         req->bhtail = bh;
>                         req->nr_sectors = req->hard_nr_sectors += count;
> @@ -1061,6 +1062,7 @@
>         req->waiting = NULL;
>         req->bh = bh;
>         req->bhtail = bh;
> +       bh->b_reqnext = NULL;
>         req->rq_dev = bh->b_rdev;
>         req->start_time = jiffies;
>         req_new_io(req, 0, count);
> ========== END OF 2.4.20 PATCH FOR drivers/block/ll_rw_blk.c =============
>
>
> ========== START OF 2.5.69 PATCH FOR drivers/block/ll_rw_blk.c ===========
> --- ll_rw_blk.c.old     Wed May  7 15:55:18 2003
> +++ ll_rw_blk.c.new     Wed May  7 16:01:56 2003
> @@ -1721,6 +1721,7 @@
>                                 break;
>                         }
>
> +                       bio->bi_next = req->biotail->bi_next;

This is simply wrong, look at the line below.

>                         req->biotail->bi_next = bio;

req->bio - first bio
req->bio->bi_next - next bio
...
req->biotail - last bio

so req->biotail->bi_next should be NULL

>                         req->biotail = bio;
>                         req->nr_sectors = req->hard_nr_sectors += nr_sectors;
> @@ -1811,6 +1812,7 @@
>         req->buffer = bio_data(bio);    /* see ->buffer comment above */
>         req->waiting = NULL;
>         req->bio = req->biotail = bio;
> +       bio->bi_next = NULL;

No need for that, look at bio_init() in fs/bio.c.

>         req->rq_disk = bio->bi_bdev->bd_disk;
>         req->start_time = jiffies;
>         add_request(q, req, insert_here);
> ========== END OF 2.5.69 PATCH FOR drivers/block/ll_rw_blk.c =============

--
Bartlomiej

Re: [PATCH] fixes for linked list bugs in block I/O code

[Dave Peterson]

On Wednesday 07 May 2003 04:42 pm, Bartlomiej Zolnierkiewicz wrote:
> > ========== START OF 2.5.69 PATCH FOR drivers/block/ll_rw_blk.c
> > =========== --- ll_rw_blk.c.old     Wed May  7 15:55:18 2003
> > +++ ll_rw_blk.c.new     Wed May  7 16:01:56 2003
> > @@ -1721,6 +1721,7 @@
> >                                 break;
> >                         }
> >
> > +                       bio->bi_next = req->biotail->bi_next;
>
> This is simply wrong, look at the line below.
>
> >                         req->biotail->bi_next = bio;
>
> req->bio - first bio
> req->bio->bi_next - next bio
> ...
> req->biotail - last bio
>
> so req->biotail->bi_next should be NULL

I believe it is correct.  Assuming that the list is initially in a
sane state, req->biotail->bi_next will be NULL immediately before
executing the statement that I added.  Therefore, my fix will set
bio->bi_next to NULL, which is what we want because bio becomes the
new end of the list.

> >                         req->biotail = bio;
> >                         req->nr_sectors = req->hard_nr_sectors +=
> > nr_sectors; @@ -1811,6 +1812,7 @@
> >         req->buffer = bio_data(bio);    /* see ->buffer comment above */
> >         req->waiting = NULL;
> >         req->bio = req->biotail = bio;
> > +       bio->bi_next = NULL;
>
> No need for that, look at bio_init() in fs/bio.c.

Yes, it looks like bio_init has been added in the 2.5 kernels, solving
the problem.  However, this is still a bug in 2.4.20.

-Dave

Re: [PATCH] fixes for linked list bugs in block I/O code

[Bartlomiej Zolnierkiewicz]

On Wed, 7 May 2003, Dave Peterson wrote:

> On Wednesday 07 May 2003 04:42 pm, Bartlomiej Zolnierkiewicz wrote:
> > > ========== START OF 2.5.69 PATCH FOR drivers/block/ll_rw_blk.c
> > > =========== --- ll_rw_blk.c.old     Wed May  7 15:55:18 2003
> > > +++ ll_rw_blk.c.new     Wed May  7 16:01:56 2003
> > > @@ -1721,6 +1721,7 @@
> > >                                 break;
> > >                         }
> > >
> > > +                       bio->bi_next = req->biotail->bi_next;
> >
> > This is simply wrong, look at the line below.
> >
> > >                         req->biotail->bi_next = bio;
> >
> > req->bio - first bio
> > req->bio->bi_next - next bio
> > ...
> > req->biotail - last bio
> >
> > so req->biotail->bi_next should be NULL
>
> I believe it is correct.  Assuming that the list is initially in a
> sane state, req->biotail->bi_next will be NULL immediately before
> executing the statement that I added.  Therefore, my fix will set
> bio->bi_next to NULL, which is what we want because bio becomes the
> new end of the list.

Yes, but bio->bi_next is a NULL already.

> > >                         req->biotail = bio;
> > >                         req->nr_sectors = req->hard_nr_sectors +=
> > > nr_sectors; @@ -1811,6 +1812,7 @@
> > >         req->buffer = bio_data(bio);    /* see ->buffer comment above */
> > >         req->waiting = NULL;
> > >         req->bio = req->biotail = bio;
> > > +       bio->bi_next = NULL;
> >
> > No need for that, look at bio_init() in fs/bio.c.
>
> Yes, it looks like bio_init has been added in the 2.5 kernels, solving
> the problem.  However, this is still a bug in 2.4.20.

Maybe. If so only second part of the patch is important.

Regards,
--
Bartlomiej

Re: [PATCH] fixes for linked list bugs in block I/O code

[Dave Peterson]

On Wednesday 07 May 2003 05:26 pm, Bartlomiej Zolnierkiewicz wrote:
> On Wed, 7 May 2003, Dave Peterson wrote:
> > On Wednesday 07 May 2003 04:42 pm, Bartlomiej Zolnierkiewicz wrote:
> > > > ========== START OF 2.5.69 PATCH FOR drivers/block/ll_rw_blk.c
> > > > =========== --- ll_rw_blk.c.old     Wed May  7 15:55:18 2003
> > > > +++ ll_rw_blk.c.new     Wed May  7 16:01:56 2003
> > > > @@ -1721,6 +1721,7 @@
> > > >                                 break;
> > > >                         }
> > > >
> > > > +                       bio->bi_next = req->biotail->bi_next;
> > >
> > > This is simply wrong, look at the line below.
> > >
> > > >                         req->biotail->bi_next = bio;
> > >
> > > req->bio - first bio
> > > req->bio->bi_next - next bio
> > > ...
> > > req->biotail - last bio
> > >
> > > so req->biotail->bi_next should be NULL
> >
> > I believe it is correct.  Assuming that the list is initially in a
> > sane state, req->biotail->bi_next will be NULL immediately before
> > executing the statement that I added.  Therefore, my fix will set
> > bio->bi_next to NULL, which is what we want because bio becomes the
> > new end of the list.
>
> Yes, but bio->bi_next is a NULL already.

I think assuming this is bad programming form.  You are assuming that
the memory allocator zeros out newly allocated memory.  Though your
assumption may be correct, it's always possible that this behavior will
change some day (perhaps for efficiency reasons), causing your code
to break.  In my opinion, the savings of a few cpu clock cycles that
you gain by omitting the initialization isn't worth compromising
the robustness of your code.

-Dave

Re: [PATCH] fixes for linked list bugs in block I/O code

[Bartlomiej Zolnierkiewicz]

On Wed, 7 May 2003, Dave Peterson wrote:

> On Wednesday 07 May 2003 05:26 pm, Bartlomiej Zolnierkiewicz wrote:
> > On Wed, 7 May 2003, Dave Peterson wrote:
> > > On Wednesday 07 May 2003 04:42 pm, Bartlomiej Zolnierkiewicz wrote:
> > > > > ========== START OF 2.5.69 PATCH FOR drivers/block/ll_rw_blk.c
> > > > > =========== --- ll_rw_blk.c.old     Wed May  7 15:55:18 2003
> > > > > +++ ll_rw_blk.c.new     Wed May  7 16:01:56 2003
> > > > > @@ -1721,6 +1721,7 @@
> > > > >                                 break;
> > > > >                         }
> > > > >
> > > > > +                       bio->bi_next = req->biotail->bi_next;
> > > >
> > > > This is simply wrong, look at the line below.
> > > >
> > > > >                         req->biotail->bi_next = bio;
> > > >
> > > > req->bio - first bio
> > > > req->bio->bi_next - next bio
> > > > ...
> > > > req->biotail - last bio
> > > >
> > > > so req->biotail->bi_next should be NULL
> > >
> > > I believe it is correct.  Assuming that the list is initially in a
> > > sane state, req->biotail->bi_next will be NULL immediately before
> > > executing the statement that I added.  Therefore, my fix will set
> > > bio->bi_next to NULL, which is what we want because bio becomes the
> > > new end of the list.
> >
> > Yes, but bio->bi_next is a NULL already.
>
> I think assuming this is bad programming form.  You are assuming that
> the memory allocator zeros out newly allocated memory.  Though your

No, it is not memory allocator but block layer.
Look at bio_init(), there is bio->bi_next = NULL explicitly.

> assumption may be correct, it's always possible that this behavior will
> change some day (perhaps for efficiency reasons), causing your code
> to break.  In my opinion, the savings of a few cpu clock cycles that
> you gain by omitting the initialization isn't worth compromising
> the robustness of your code.

Agreed, but not the case here (speaking 2.5).
Better add check for bio->bi_next != NULL to catch improper usage.

--
Bartlomiej

> -Dave

Re: [PATCH] fixes for linked list bugs in block I/O code

[Dave Peterson]

On Wednesday 07 May 2003 06:17 pm, Bartlomiej Zolnierkiewicz wrote:
> > > Yes, but bio->bi_next is a NULL already.
> >
> > I think assuming this is bad programming form.  You are assuming that
> > the memory allocator zeros out newly allocated memory.  Though your
>
> No, it is not memory allocator but block layer.
> Look at bio_init(), there is bio->bi_next = NULL explicitly.

Ok, I agree: the patch is not needed for 2.5 (although I think it still
makes sense for 2.4.20).  Thanks for the correction.

-Dave

Re: [PATCH] fixes for linked list bugs in block I/O code

[Jens Axboe]

On Wed, May 07 2003, Dave Peterson wrote:
> I found a couple of small linked list bugs in __make_request() in
> drivers/block/ll_rw_blk.c.  The bugs exist in both kernels
> 2.4.20 and 2.5.69.  Therefore I have made patches for both
> kernels.  The problem is that when inserting a new buffer_head
> into the linked list of buffer_head structures maintained by
> "struct request", the b_reqnext field is not initialized.
> 
> -Dave Peterson
>  dsp@llnl.gov
> 
> 
> ========== START OF 2.4.20 PATCH FOR drivers/block/ll_rw_blk.c ===========
> --- ll_rw_blk.c.old     Wed May  7 15:54:58 2003
> +++ ll_rw_blk.c.new     Wed May  7 15:58:07 2003
> @@ -973,6 +973,7 @@
>                                 insert_here = &req->queue;
>                                 break;
>                         }
> +                       bh->b_reqnext = req->bhtail->b_reqnext;

This is convoluted nonsense, bhtail->b_reqnext is NULL by definition. So
a simple

	bh->b_reqnext = NULL;

is much clearer.

>                         req->bhtail->b_reqnext = bh;
>                         req->bhtail = bh;
>                         req->nr_sectors = req->hard_nr_sectors += count;
> @@ -1061,6 +1062,7 @@
>         req->waiting = NULL;
>         req->bh = bh;
>         req->bhtail = bh;
> +       bh->b_reqnext = NULL;
>         req->rq_dev = bh->b_rdev;
>         req->start_time = jiffies;
>         req_new_io(req, 0, count);

Bart already covered why 2.5 definitely does not need it. I dunno what
to say for 2.4, to me it looks like a BUG if you pass in a buffer_head
with uninitialized b_reqnext. Why should that member be any different?

In fact, from where did you see this buffer_head coming from? Who is
submitting IO on a not properly inited bh? To me, that sounds like not a
block layer bug but an fs bug.

-- 
Jens Axboe

Re: [PATCH] fixes for linked list bugs in block I/O code

[Dave Peterson]

On Wednesday 07 May 2003 11:29 pm, Jens Axboe wrote:
> This is convoluted nonsense, bhtail->b_reqnext is NULL by definition. So
> a simple
>
> 	bh->b_reqnext = NULL;
>
> is much clearer.

Ok, that's fine with me.  Setting it explicitly to NULL is also correct
and perhaps a bit more clear.

> >                         req->bhtail->b_reqnext = bh;
> >                         req->bhtail = bh;
> >                         req->nr_sectors = req->hard_nr_sectors += count;
> > @@ -1061,6 +1062,7 @@
> >         req->waiting = NULL;
> >         req->bh = bh;
> >         req->bhtail = bh;
> > +       bh->b_reqnext = NULL;
> >         req->rq_dev = bh->b_rdev;
> >         req->start_time = jiffies;
> >         req_new_io(req, 0, count);
>
> Bart already covered why 2.5 definitely does not need it. I dunno what
> to say for 2.4, to me it looks like a BUG if you pass in a buffer_head
> with uninitialized b_reqnext. Why should that member be any different?

Ok, agreed that 2.5 does not need the patch.

> In fact, from where did you see this buffer_head coming from? Who is
> submitting IO on a not properly inited bh? To me, that sounds like not a
> block layer bug but an fs bug.

I would argue that __make_request() is where the insertion of the buffer_head
into the request structure is performed, and setting the b_reqnext field of
the buffer_head to its proper value is an integral part of performing the
insertion.  Why not keep all of the insertion logic in one place rather than
distribuing it throughout the code and requiring all callers of
__make_request() to remember to initialize b_reqnext?  Localizing the
insertion logic makes the code clearer, more compact, and easier to maintain.

-Dave