Adding Reed-Solomon Personality to MD, need help/advice

Adding Reed-Solomon Personality to MD, need help/advice

[Nathan Lewis]

As part of my Master's thesis, I am working on adding a Reed-Solomon 
personality to the existing linux RAID structure and I would like some 
assistance.  I'll try to keep this as brief as possible, but I apologize if 
it gets long-winded.

So far, I've managed to add and register a personality with md, which 
involved a few minor changes to md.c and related header files, a few 
changes to mdadm to allow me to access things from userland.  I've 
discovered the 9 functions I need to implement (make_request, run, stop, 
etc), and managed to "successfully" create an md device using only stub 
functions.  So far so good.  Just for reference, I'm using kernel 2.4.22.

However, I can't really find concise documentation on exactly what those 9 
functions are supposed to do, and under what restrictions they must do them 
in.  I've been studying Rubini and Corbet's _Linux Device Drivers_ book, 
which goes into great detail on the responsibilities of a block device 
driver, and even covers the make_request function.  For now, that's what 
I'm focusing on anyway.

Anyway, here's my first real question:  the buffer_head bh passed into 
make_request obviously contains a request for that particular 
device.  However, this buffer_head could be the head of a linked list, with 
the next element located at b_reqnext.  However, all of the code I can find 
that uses make_request ignores bh->b_reqnext.  Is it guaranteed to be the 
only request when bypassing __make_request?  Also, the request_queue_t q is 
also ignored.  I assume this is there for use by __make_request (since it 
isn't even passed to <personality>_make_request).

Second question:  Since <personality>_make_request doesn't alter the 
request_queue_t q, it need not worry about the io_request_lock that is 
stressed in the Rubini book, correct?  I think I only have to worry about 
locks for any internal structures/buffers I use/create.

Third question:  The raid5 thread is registered with the md 
driver.  Besides the code in raid5.c, what else can wake up this 
thread?  Anything?

That's probably enough for now.  I'm sure I'll have more questions down the 
line, but I need a thorough understanding of what is there before I can add 
anything to it.

Thanks,
--Nathan Lewis

nathapl@cs.okstate.edu

Re: Adding Reed-Solomon Personality to MD, need help/advice

[H. Peter Anvin]

Followup to:  <6.0.1.1.2.20040130235924.03f39710@mail.athenet.net>
By author:    Nathan Lewis <nathapl@cs.okstate.edu>
In newsgroup: linux.dev.raid
>
> As part of my Master's thesis, I am working on adding a Reed-Solomon 
> personality to the existing linux RAID structure and I would like some 
> assistance.  I'll try to keep this as brief as possible, but I apologize if 
> it gets long-winded.
> 

I'm curious what... what is the intended mode of operation of your R-S
personality?

>
> So far, I've managed to add and register a personality with md, which 
> involved a few minor changes to md.c and related header files, a few 
> changes to mdadm to allow me to access things from userland.  I've 
> discovered the 9 functions I need to implement (make_request, run, stop, 
> etc), and managed to "successfully" create an md device using only stub 
> functions.  So far so good.  Just for reference, I'm using kernel 2.4.22.
> 

I would advice you to try a 2.6 kernel instead.  You might find it
useful to compare raid5.c to raid6main.c in those kernels.

	-hpa
-- 
PGP public key available - finger hpa@zytor.com
Key fingerprint: 2047/2A960705 BA 03 D3 2C 14 A8 A8 BD  1E DF FE 69 EE 35 BD 74
"The earth is but one country, and mankind its citizens."  --  Bahá'u'lláh
Just Say No to Morden * The Shadows were defeated -- Babylon 5 is renewed!!
-
To unsubscribe from this list: send the line "unsubscribe linux-raid" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding Reed-Solomon Personality to MD, need help/advice

[Neil Brown]

On Saturday January 31, nathapl@cs.okstate.edu wrote:
> As part of my Master's thesis, I am working on adding a Reed-Solomon 
> personality to the existing linux RAID structure and I would like some 
> assistance.  I'll try to keep this as brief as possible, but I apologize if 
> it gets long-winded.
> 
> So far, I've managed to add and register a personality with md, which 
> involved a few minor changes to md.c and related header files, a few 
> changes to mdadm to allow me to access things from userland.  I've 
> discovered the 9 functions I need to implement (make_request, run, stop, 
> etc), and managed to "successfully" create an md device using only stub 
> functions.  So far so good.  Just for reference, I'm using kernel
> 2.4.22.

I strongly agree with Peter.  Base your work on 2.6, not 2.4.  The
raid code is much cleaner in 2.6.

> 
> However, I can't really find concise documentation on exactly what those 9 
> functions are supposed to do, and under what restrictions they must do them 
> in.  I've been studying Rubini and Corbet's _Linux Device Drivers_ book, 
> which goes into great detail on the responsibilities of a block device 
> driver, and even covers the make_request function.  For now, that's what 
> I'm focusing on anyway.

Good.  md/raid uses the make_request_fn function, not the request_fn
function like most device drivers use.  
> 
> Anyway, here's my first real question:  the buffer_head bh passed into 
> make_request obviously contains a request for that particular 
> device.  However, this buffer_head could be the head of a linked list, with 
> the next element located at b_reqnext.  However, all of the code I can find 
> that uses make_request ignores bh->b_reqnext.  Is it guaranteed to be the 
> only request when bypassing __make_request?  Also, the request_queue_t q is 
> also ignored.  I assume this is there for use by __make_request (since it 
> isn't even passed to <personality>_make_request).

The buffer_head, or bio in 2.6, passed into make_request is not the
head of a linked list.  b_reqnext is not defined at this point.  It is
there for the make_request function to use if it wants to.
The "standard" make_request function, called __make_request, uses it
to link adjacent buffer_heads or bios together into a single request.
Various raid make_request functions use it for other purposes or not
at all.

In 2.6, the "request_queue_t *q" is passed on to the make_request_fn
as it contains a pointer to the mddev stucture.

> 
> Second question:  Since <personality>_make_request doesn't alter the 
> request_queue_t q, it need not worry about the io_request_lock that is 
> stressed in the Rubini book, correct?  I think I only have to worry about 
> locks for any internal structures/buffers I use/create.

Correct.  The io_request_lock is only used by __make_request and
request_fn functions.  If you define a different make_request_fn (as
md/raid does) you can use the io_request_lock for something else, or
ignore it altogether.

> 
> Third question:  The raid5 thread is registered with the md 
> driver.  Besides the code in raid5.c, what else can wake up this 
> thread?  Anything?

No nothing  (except maybe a signal being sent to it).

> 
> That's probably enough for now.  I'm sure I'll have more questions down the 
> line, but I need a thorough understanding of what is there before I can add 
> anything to it.


I too would be interest to see just how you would apply reed-solomon
encoding to RAID.

NeilBrown

Re: Adding Reed-Solomon Personality to MD, need help/advice

[Nathan Lewis]

At 04:53 AM 1/31/2004, Neil Brown wrote:
>I strongly agree with Peter.  Base your work on 2.6, not 2.4.  The
>raid code is much cleaner in 2.6.

I'll take a look at 2.6 then and see what's different.  It may not be 
possible for me to use 2.6 due to restrictions on the test machines I'll be 
using.  I chose 2.4 because that's what was included in the distribution 
I'm using, it is what my professor is using on his machines, and it is the 
version covered by the Rubini book.  It seemed like a logical 
choice.  Where's the most comprehensive list of changes 2.4->2.6 dealing 
with block drivers and linux-raid?

>Good.  md/raid uses the make_request_fn function, not the request_fn
>function like most device drivers use.
>.....<snip>....

I really appreciate the answers to my questions.

>I too would be interest to see just how you would apply reed-solomon
>encoding to RAID.

In short, it is a distributed storage mechanism for a small (~50) group of 
workstations with a central coordinating server.  RS is needed for the high 
levels of redundancy possible.

Re: Adding Reed-Solomon Personality to MD, need help/advice

[Nathan Lewis]

Now that I've got working Reed Soloman code, I need to make a decision 
really quickly on whether to use 2.4 or 2.6.  I've got both, and it does 
look like the raid code is much cleaner in 2.6, and it also helps that 
there is raid6 for 2.6, which shows me approximately where I'd need to 
modify code to turn it into RS.  However, I really need some documentation 
on the bio structure.  The bio.h file is sorely lacking comments, and, of 
course, the Rubini book isn't going to help me.

Can someone point me at some documentation for the bio structure?


>I strongly agree with Peter.  Base your work on 2.6, not 2.4.  The
>raid code is much cleaner in 2.6.

Re: Adding Reed-Solomon Personality to MD, need help/advice

[Ming Zhang]

The new book Linux Kernel Development and 
http://lwn.net/Articles/driver-porting/

may give u some help.


ming

On Thu, 2004-02-12 at 23:35, Nathan Lewis wrote:
> Now that I've got working Reed Soloman code, I need to make a decision 
> really quickly on whether to use 2.4 or 2.6.  I've got both, and it does 
> look like the raid code is much cleaner in 2.6, and it also helps that 
> there is raid6 for 2.6, which shows me approximately where I'd need to 
> modify code to turn it into RS.  However, I really need some documentation 
> on the bio structure.  The bio.h file is sorely lacking comments, and, of 
> course, the Rubini book isn't going to help me.
> 
> Can someone point me at some documentation for the bio structure?
> 
> 
> >I strongly agree with Peter.  Base your work on 2.6, not 2.4.  The
> >raid code is much cleaner in 2.6.
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-raid" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding Reed-Solomon Personality to MD, need help/advice

[Nathan Lewis]

Thanks, that looks like exactly what I was looking for.

At 08:18 AM 2/13/2004, Ming Zhang wrote:
>The new book Linux Kernel Development and
>http://lwn.net/Articles/driver-porting/
>
>may give u some help.
>
>
>ming
>
>On Thu, 2004-02-12 at 23:35, Nathan Lewis wrote:
> > Now that I've got working Reed Soloman code, I need to make a decision
> > really quickly on whether to use 2.4 or 2.6.  I've got both, and it does
> > look like the raid code is much cleaner in 2.6, and it also helps that
> > there is raid6 for 2.6, which shows me approximately where I'd need to
> > modify code to turn it into RS.  However, I really need some documentation
> > on the bio structure.  The bio.h file is sorely lacking comments, and, of
> > course, the Rubini book isn't going to help me.
> >
> > Can someone point me at some documentation for the bio structure?
> >
> >
> > >I strongly agree with Peter.  Base your work on 2.6, not 2.4.  The
> > >raid code is much cleaner in 2.6.
> >
> > -
> > To unsubscribe from this list: send the line "unsubscribe linux-raid" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
>-
>To unsubscribe from this list: send the line "unsubscribe linux-raid" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding Reed-Solomon Personality to MD, need help/advice

[Mario 'BitKoenig' Holbe]

Hello,

Nathan Lewis <nathapl@cs.okstate.edu> wrote:
> As part of my Master's thesis, I am working on adding a Reed-Solomon 
> personality to the existing linux RAID structure and I would like some 

Is there any progress in implementing a generic Reed-Solomon personality
in MD since this mail from 31 Jan 2004?
Regarding the intention-question... for me, personally, it would be the
logical step inbetween raid5 resp. raid6 with survival of 1 resp. 2
simultaneous disk failures and raid10 with survival of n/2 simultaneous
disk failures. RaidRS would give users the chance to configure
redundancy and thus survivability exactly on their demands.
This would especially make sense when I see the raid5 configurations
with 14 and more devices which some users refer to on this list.
To be honest, I was thinking about such a personality myself, too, and
then was crawling the list's archive.


regards
   Mario
-- 
*axiom* welcher sensorische input bewirkte die output-aktion,
        den irc-chatter mit dem nick "dus" des irc-servers
        mittels eines kills zu verweisen?

Re: Adding Reed-Solomon Personality to MD, need help/advice

[H. Peter Anvin]

Followup to:  <dlsh2c$2h0$1@sea.gmane.org>
By author:    "Mario 'BitKoenig' Holbe" <Mario.Holbe@TU-Ilmenau.DE>
In newsgroup: linux.dev.raid
>
> Hello,
> 
> Nathan Lewis <nathapl@cs.okstate.edu> wrote:
> > As part of my Master's thesis, I am working on adding a Reed-Solomon 
> > personality to the existing linux RAID structure and I would like some 
> 
> Is there any progress in implementing a generic Reed-Solomon personality
> in MD since this mail from 31 Jan 2004?
> Regarding the intention-question... for me, personally, it would be the
> logical step inbetween raid5 resp. raid6 with survival of 1 resp. 2
> simultaneous disk failures and raid10 with survival of n/2 simultaneous
> disk failures. RaidRS would give users the chance to configure
> redundancy and thus survivability exactly on their demands.
> This would especially make sense when I see the raid5 configurations
> with 14 and more devices which some users refer to on this list.
> To be honest, I was thinking about such a personality myself, too, and
> then was crawling the list's archive.
> 

It's not really in-between; generic RS RAID would be many times slower
than either; however, unlike raid10 it could survive *any* m failures
where m is the number of redundancy drives.

The fundamental problem is that generic RS requires table lookups even
in the common case, whereas RAID-6 uses shortcuts to substantially
speed up the computation in the common case.  RAID-6 is an important
corner of the problem space, since it deals with the unfortunately
fairly common problem of "disk failure discovered during recovery"
with RAID-5.

That doesn't mean there couldn't be a problem space where it would
make sense (in fact, on the contrary), but it's still a substantial
engineering effort that would have to be justified.

Heck, I might even be persuaded to look for generic RS shortcuts if
someone tempted me enough...

	-hpa

Re: Adding Reed-Solomon Personality to MD, need help/advice

[Bill Rugolsky Jr.]

On Thu, Dec 29, 2005 at 10:40:33AM -0800, H. Peter Anvin wrote:
> It's not really in-between; generic RS RAID would be many times slower
> than either; however, unlike raid10 it could survive *any* m failures
> where m is the number of redundancy drives.
> 
> The fundamental problem is that generic RS requires table lookups even
> in the common case, whereas RAID-6 uses shortcuts to substantially
> speed up the computation in the common case.  RAID-6 is an important
> corner of the problem space, since it deals with the unfortunately
> fairly common problem of "disk failure discovered during recovery"
> with RAID-5.
> 
> That doesn't mean there couldn't be a problem space where it would
> make sense (in fact, on the contrary), but it's still a substantial
> engineering effort that would have to be justified.
> 
> Heck, I might even be persuaded to look for generic RS shortcuts if
> someone tempted me enough...

Funny, I was just thinking about this last night ...
 
The "obvious" case is distributed RAID (RAIS?), where one might
want something to survive 50% loss or more.  But as you know,
the generic RS suffers from the same read-modify-write latency as
all parity-based RAID levels except Daniel Phillips's RAID 3.5
[ http://sources.redhat.com/cluster/ddraid/ ].

For archival purposes though, slow writes might not be a big deal.
At the margin, this use case begins to overlap various p2p technologies.

Regards,

	Bill Rugolsky

Re: Adding Reed-Solomon Personality to MD, need help/advice

[Jeff Breidenbach]

> The fundamental problem is that generic RS requires table lookups even
> in the common case, whereas RAID-6 uses shortcuts to substantially
> speed up the computation in the common case.

If one wanted to support a typical 8-bit RS code (which supports a max of
256 drives, including ECC drives) it is already way too big to use a table. RS
is typically done with finite field math calculations which are -
relatively - fast
but they are much heavier than a parity calculation. Here is one commercial
benchmark, note the throughput numbers at the bottom of the page.

   http://www.4i2i.com/reed_solomon_codes.htm

I can easily imagine CPU being the bottleneck for a large RS RAID, especially
when run in degraded mode. Rakhi Motwani and I worked on a RS based,
RAID-like storage system, although not for magnetic disks. Search for
"Collocated DataGlyph Protocol" if you are interested. It was a lot of fun.

Cheers,
Jeff

Re: Adding Reed-Solomon Personality to MD, need help/advice

[H. Peter Anvin]

Jeff Breidenbach wrote:
>>The fundamental problem is that generic RS requires table lookups even
>>in the common case, whereas RAID-6 uses shortcuts to substantially
>>speed up the computation in the common case.
> 
> 
> If one wanted to support a typical 8-bit RS code (which supports a max of
> 256 drives, including ECC drives) it is already way too big to use a table. RS
> is typically done with finite field math calculations which are -
> relatively - fast
> but they are much heavier than a parity calculation. Here is one commercial
> benchmark, note the throughput numbers at the bottom of the page.
> 

Well, most of them are implemented via tables (GF log table, etc.)  They 
tend to perform poorly on modern hardware.

	-hpa

RE: Adding Reed-Solomon Personality to MD, need help/advice

[Bailey, Scott]

Interestingly, I was just browsing this paper
http://www.cs.utk.edu/%7Eplank/plank/papers/CS-05-569.html which appears
to be quite on-topic for this discussion. I admit my eyes glaze over
during intensive math discussions but it appears tuned RS might not be
as horrible as you'd think since apparently state-of-the-art now
provides tricks to avoid the Galois Field operations that used to be
required.

The thought that came to my mind was "how does md's RAID-6 personality
compare to EVENODD coding?"

Wondering if my home server will ever have enough storage for these
discussions to become non-academic for me, :-) 

	Scott


-----Original Message-----
From: linux-raid-owner@vger.kernel.org
[mailto:linux-raid-owner@vger.kernel.org] On Behalf Of H. Peter Anvin
Sent: Thursday, December 29, 2005 1:41 PM
To: linux-raid@vger.kernel.org
Subject: Re: Adding Reed-Solomon Personality to MD, need help/advice

Followup to:  <dlsh2c$2h0$1@sea.gmane.org>
By author:    "Mario 'BitKoenig' Holbe" <Mario.Holbe@TU-Ilmenau.DE>
In newsgroup: linux.dev.raid
>
> Hello,
> 
> Nathan Lewis <nathapl@cs.okstate.edu> wrote:
> > As part of my Master's thesis, I am working on adding a Reed-Solomon

> > personality to the existing linux RAID structure and I would like
some 
> 
> Is there any progress in implementing a generic Reed-Solomon
personality
> in MD since this mail from 31 Jan 2004?
> Regarding the intention-question... for me, personally, it would be
the
> logical step inbetween raid5 resp. raid6 with survival of 1 resp. 2
> simultaneous disk failures and raid10 with survival of n/2
simultaneous
> disk failures. RaidRS would give users the chance to configure
> redundancy and thus survivability exactly on their demands.
> This would especially make sense when I see the raid5 configurations
> with 14 and more devices which some users refer to on this list.
> To be honest, I was thinking about such a personality myself, too, and
> then was crawling the list's archive.
> 

It's not really in-between; generic RS RAID would be many times slower
than either; however, unlike raid10 it could survive *any* m failures
where m is the number of redundancy drives.

The fundamental problem is that generic RS requires table lookups even
in the common case, whereas RAID-6 uses shortcuts to substantially
speed up the computation in the common case.  RAID-6 is an important
corner of the problem space, since it deals with the unfortunately
fairly common problem of "disk failure discovered during recovery"
with RAID-5.

That doesn't mean there couldn't be a problem space where it would
make sense (in fact, on the contrary), but it's still a substantial
engineering effort that would have to be justified.

Heck, I might even be persuaded to look for generic RS shortcuts if
someone tempted me enough...

	-hpa

-
To unsubscribe from this list: send the line "unsubscribe linux-raid" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding Reed-Solomon Personality to MD, need help/advice

[Jeff Breidenbach]

Interesting paper, thanks. Unfortunately, decode bandwidth
when erasures are present (e.g. drives have failed) is not
discussed. This is by far the speed bottleneck for Reed-Solomon
and a potential hangup for a RS personality in md.

Jeff

Re: Adding Reed-Solomon Personality to MD, need help/advice

[Bill Davidsen]

Bailey, Scott wrote:

>Interestingly, I was just browsing this paper
>http://www.cs.utk.edu/%7Eplank/plank/papers/CS-05-569.html which appears
>to be quite on-topic for this discussion. I admit my eyes glaze over
>during intensive math discussions but it appears tuned RS might not be
>as horrible as you'd think since apparently state-of-the-art now
>provides tricks to avoid the Galois Field operations that used to be
>required.
>
>The thought that came to my mind was "how does md's RAID-6 personality
>compare to EVENODD coding?"
>
>Wondering if my home server will ever have enough storage for these
>discussions to become non-academic for me, :-) 
>
The problem is not having storage, it's having backup. The properties of 
backup are
- able to be moved to off-site storage
- cheap and fast enough to use regularly

Making storage more reliable is a desirable end, but it doesn't guard 
against many common failures such as controllers going bad and writing 
unreadable sectors all over before total failure, fire, flood, and 
software errors in the kernel code. While none of these is common in the 
sense of everyday, they are all common in the sense of "I never heard of 
that happening" response.

-- 
bill davidsen <davidsen@tmr.com>
  CTO TMR Associates, Inc
  Doing interesting things with small computers since 1979