Re: [PATCH 1/4] scatterlist: new helper functions

Re: [PATCH 1/4] scatterlist: new helper functions

[Alex Dubov]

> 
> The functions that were added:
> 
> * sg_nents/sg_total_len - interate over sg list to figure

You've got a typo here.

> out its total len, number of entries.
> Useful for not keeping that information in side channels.
> 

> Allows to transparetly compare contents of the sg list to
> given linear

And here.

> buffer.
> If needed later, a function that compares two sgs can be
> added.
> 
> All of this code is used by my ms_block.c driver.
> 

I definitely find this useful.
But, of course, we need to ask somebody from the memory management
department to look at it, as this patch is intended to be not memorystick
specific.





      

[PATH 0/4] Memstick patches for 2.6.39

[Maxim Levitsky]

Hi,

This is a repost of my patches for 2.6.39 inclusion, which I hope not to
miss this time.

I addressed the comments on the scatterlist issues.

Andrew, please note that my richoh memstick driver is standalone, unchanged from previos versions
has many users which use the version I posted at ubuntu's Launchpad and happy with it.
Please include it regardless of other patches.

The other half of my work is support for legacy memorysticks which consists of 2 patches,
first that adds few functions to scatterlist.c, and the other patch that adds the driver.
Driver is also stable and tested.

Best regards,
	Maxim Levitsky

[PATCH 1/4] scatterlist: new helper functions

[Maxim Levitsky]

While developing memstick driver for legacy memsticks
I found the need in few helpers that I think should be
in common scatterlist library

The functions that were added:

* sg_nents/sg_total_len - iterate over scatterlist to figure
out total length of memory it covers / number of entries.

Usefull for small sg lists where there is no prefomance advantage of
storing this info in a special variable.

* sg_copy/sg_truncate - Allow to break scatterlists apart into smaller chunks.
sg_copy creates smaller scatterlist, spanning first 'len' bytes, while
sg_truncate edits the scatterlist in such way that it skips over 'len' bytes.


* sg_compare_to_buffer - another function to hide gory details of access
to sg list by CPU.
Allows to transparently compare contents of the sg list to given linear
buffer.
If needed later, a function that compares two sgs can be added.

All of this code is used by my ms_block.c driver.

Signed-off-by: Maxim Levitsky <maximlevitsky@gmail.com>
---
 include/linux/scatterlist.h |    8 ++
 lib/scatterlist.c           |  152 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 160 insertions(+), 0 deletions(-)

diff --git a/include/linux/scatterlist.h b/include/linux/scatterlist.h
index 9aaf5bf..88fc7a5 100644
--- a/include/linux/scatterlist.h
+++ b/include/linux/scatterlist.h
@@ -199,6 +199,12 @@ static inline void *sg_virt(struct scatterlist *sg)
 	return page_address(sg_page(sg)) + sg->offset;
 }
 
+struct scatterlist *sg_truncate(struct scatterlist *sg, int consumed);
+int sg_nents(struct scatterlist *sg);
+int sg_total_len(struct scatterlist *sg);
+int sg_copy(struct scatterlist *sg_from, struct scatterlist *sg_to,
+							int to_nents, int len);
+
 struct scatterlist *sg_next(struct scatterlist *);
 struct scatterlist *sg_last(struct scatterlist *s, unsigned int);
 void sg_init_table(struct scatterlist *, unsigned int);
@@ -217,6 +223,8 @@ size_t sg_copy_from_buffer(struct scatterlist *sgl, unsigned int nents,
 			   void *buf, size_t buflen);
 size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents,
 			 void *buf, size_t buflen);
+bool sg_compare_to_buffer(struct scatterlist *sg, unsigned int nents,
+							u8 *buffer, size_t len);
 
 /*
  * Maximum number of entries that will be allocated in one piece, if
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index 4ceb05d..941195d 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -39,6 +39,76 @@ struct scatterlist *sg_next(struct scatterlist *sg)
 EXPORT_SYMBOL(sg_next);
 
 /**
+ * sg_truncate - remove 'consumed' bytes from head of a scatterlist
+ * @sg:		The current sg entry
+ * @consumed:	How much bytes to remove
+ */
+struct scatterlist *sg_truncate(struct scatterlist *sg, int consumed)
+{
+	while (consumed >= sg->length) {
+		consumed -= sg->length;
+
+		sg = sg_next(sg);
+		if (!sg)
+			break;
+	}
+
+	WARN_ON(!sg && consumed);
+
+	if (!sg)
+		return NULL;
+
+	sg->offset += consumed;
+	sg->length -= consumed;
+
+	if (sg->offset >= PAGE_SIZE) {
+		struct page *page =
+			nth_page(sg_page(sg), sg->offset / PAGE_SIZE);
+		sg_set_page(sg, page, sg->length, sg->offset % PAGE_SIZE);
+	}
+
+	return sg;
+}
+EXPORT_SYMBOL(sg_truncate);
+
+/**
+ * sg_nents - calculate number of sg entries in sg list
+ * @sg:		The current sg entry
+ *
+ * Allows to calculate dynamically the length of the sg table, based on
+ * assumption that last entry is correctly marked by sg_mark_end
+ */
+int sg_nents(struct scatterlist *sg)
+{
+	int nents = 0;
+	while (sg) {
+		nents++;
+		sg = sg_next(sg);
+	}
+
+	return nents;
+}
+EXPORT_SYMBOL(sg_nents);
+
+/**
+ * sg_total_len - calculate total length of scatterlist
+ * @sg:		The current sg entry
+ *
+ * Dynamically calculate total number of bytes in an scatterlist
+ * based on assumption that last entry is correctly marked by sg_mark_end
+ */
+int sg_total_len(struct scatterlist *sg)
+{
+	int len = 0;
+	while (sg) {
+		len += sg->length;
+		sg = sg_next(sg);
+	}
+	return len;
+}
+EXPORT_SYMBOL(sg_total_len);
+
+/**
  * sg_last - return the last scatterlist entry in a list
  * @sgl:	First entry in the scatterlist
  * @nents:	Number of entries in the scatterlist
@@ -110,6 +180,47 @@ void sg_init_one(struct scatterlist *sg, const void *buf, unsigned int buflen)
 }
 EXPORT_SYMBOL(sg_init_one);
 
+/**
+ * sg_copy - copies sg entries from sg_from to sg_to, such
+ * as sg_to covers first 'len' bytes from sg_from.
+ * @sg_from:	SG list to copy entries from
+ * @sg_to:	SG list to write entries to
+ * @to_nents:	number of usable entries in 'sg_to'
+ * @len:	maximum number of bytes the 'sg_to' will cover
+ *
+ * Returns actual number of bytes covered by sg_to
+ */
+int sg_copy(struct scatterlist *sg_from, struct scatterlist *sg_to,
+							int to_nents, int len)
+{
+	int copied = 0;
+
+	while (len > sg_from->length && to_nents--) {
+
+		len -= sg_from->length;
+		copied += sg_from->length;
+
+		sg_set_page(sg_to, sg_page(sg_from),
+				sg_from->length, sg_from->offset);
+
+		if (sg_is_last(sg_from) || !len) {
+			sg_mark_end(sg_to);
+			return copied;
+		}
+
+		sg_from = sg_next(sg_from);
+		sg_to = sg_next(sg_to);
+	}
+
+	if (to_nents) {
+		sg_set_page(sg_to, sg_page(sg_from), len, sg_from->offset);
+		sg_mark_end(sg_to);
+	}
+
+	return copied;
+}
+EXPORT_SYMBOL(sg_copy);
+
 /*
  * The default behaviour of sg_alloc_table() is to use these kmalloc/kfree
  * helpers.
@@ -517,3 +628,44 @@ size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents,
 	return sg_copy_buffer(sgl, nents, buf, buflen, 1);
 }
 EXPORT_SYMBOL(sg_copy_to_buffer);
+
+
+/**
+ * sg_compare_to_buffer - compare contents of the data pointed by sg table
+ * to a kernel ram buffer
+ *
+ * @sg:		The current sg entry
+ * @buffer:	Linear kernel buffer to compare with
+ * @len:	Length of that buffer
+ *
+ * Returns 0 if equal and memcmp compliant result otherwise
+ */
+bool sg_compare_to_buffer(struct scatterlist *sg, unsigned int nents,
+							u8 *buffer, size_t len)
+{
+	unsigned long flags;
+	int retval = 0;
+	struct sg_mapping_iter miter;
+
+	local_irq_save(flags);
+	sg_miter_start(&miter, sg, nents, SG_MITER_ATOMIC | SG_MITER_FROM_SG);
+
+	while (sg_miter_next(&miter) && len > 0) {
+
+		int cmplen = min(miter.length, len);
+		retval = memcmp(miter.addr, buffer, cmplen);
+		if (retval)
+			break;
+
+		buffer += cmplen;
+		len -= cmplen;
+	}
+
+	if (!retval && len)
+		retval = -1;
+
+	sg_miter_stop(&miter);
+	local_irq_restore(flags);
+	return retval;
+}
+EXPORT_SYMBOL(sg_compare_to_buffer);
-- 
1.7.1

Re: [PATCH 1/4] scatterlist: new helper functions

[FUJITA Tomonori]

On Fri,  4 Mar 2011 06:16:50 +0200
Maxim Levitsky <maximlevitsky@gmail.com> wrote:

> While developing memstick driver for legacy memsticks
> I found the need in few helpers that I think should be
> in common scatterlist library
> 
> The functions that were added:
> 
> * sg_nents/sg_total_len - iterate over scatterlist to figure
> out total length of memory it covers / number of entries.

You should invent a data structure per I/O request, something like
msb_request structure. Then you can store nents and total_len in
that.

That's what block subsystems and drivers do. I took a look at your
driver but I can't see why your driver can't do the same.

Re: [PATCH 1/4] scatterlist: new helper functions

[Maxim Levitsky]

On Sun, 2011-03-06 at 16:29 +0900, FUJITA Tomonori wrote:
> On Fri,  4 Mar 2011 06:16:50 +0200
> Maxim Levitsky <maximlevitsky@gmail.com> wrote:
> 
> > While developing memstick driver for legacy memsticks
> > I found the need in few helpers that I think should be
> > in common scatterlist library
> > 
> > The functions that were added:
> > 
> > * sg_nents/sg_total_len - iterate over scatterlist to figure
> > out total length of memory it covers / number of entries.
> 
> You should invent a data structure per I/O request, something like
> msb_request structure. Then you can store nents and total_len in
> that.
> 
> That's what block subsystems and drivers do. I took a look at your
> driver but I can't see why your driver can't do the same.
I also need to break the request into small grained chunks.
If I invent such structure, I will end up writing these helpers for it.

The I have this lifetime of a request:

I get arbitary sized request from block layer (I can of course control
maximum size/number of segments in it, etc).

I break it into eraseblock sized chunks, and for each I translate the
the LBA, into flash address.

Then I break it into flash page sized requests (512 bytes), and yet its
better not to assume that such requests always contained in one sg
entry.

Worse than that, I have to pass an sg list that spans always one 512
page to lowlevel driver, because thats how Alex defined the interface.
 
Thats why I coded it this way.

Folks, really what the status of this, when to expect it to be merged?

If you think some of helper functions don't belong to scatterlist.c,
just tell me to move them back to ms_block.c.

Andrew, please note again that richoh lowlevel driver doesn't need any
helper functions, its patch is standalone and thus should be merged
regardless.

Best regards,
	Maxim Levitsky

Re: [PATCH 1/4] scatterlist: new helper functions

[FUJITA Tomonori]

On Sun, 06 Mar 2011 17:14:30 +0200
Maxim Levitsky <maximlevitsky@gmail.com> wrote:

> On Sun, 2011-03-06 at 16:29 +0900, FUJITA Tomonori wrote:
> > On Fri,  4 Mar 2011 06:16:50 +0200
> > Maxim Levitsky <maximlevitsky@gmail.com> wrote:
> > 
> > > While developing memstick driver for legacy memsticks
> > > I found the need in few helpers that I think should be
> > > in common scatterlist library
> > > 
> > > The functions that were added:
> > > 
> > > * sg_nents/sg_total_len - iterate over scatterlist to figure
> > > out total length of memory it covers / number of entries.
> > 
> > You should invent a data structure per I/O request, something like
> > msb_request structure. Then you can store nents and total_len in
> > that.
> > 
> > That's what block subsystems and drivers do. I took a look at your
> > driver but I can't see why your driver can't do the same.
> I also need to break the request into small grained chunks.
> If I invent such structure, I will end up writing these helpers for it.
> 
> The I have this lifetime of a request:
> 
> I get arbitary sized request from block layer (I can of course control
> maximum size/number of segments in it, etc).
> 
> I break it into eraseblock sized chunks, and for each I translate the
> the LBA, into flash address.
> 
> Then I break it into flash page sized requests (512 bytes), and yet its
> better not to assume that such requests always contained in one sg
> entry.
> 
> Worse than that, I have to pass an sg list that spans always one 512
> page to lowlevel driver, because thats how Alex defined the interface.

This restriction is due to hardware specification or the software
design (e.g. memstick layer)? If it is due to the latter, why can't
you fix that?

Why can't the block layer split requests for you? It's better to let
the block layer handle that.


> Folks, really what the status of this, when to expect it to be merged?
> 
> If you think some of helper functions don't belong to scatterlist.c,
> just tell me to move them back to ms_block.c.
> 
> Andrew, please note again that richoh lowlevel driver doesn't need any
> helper functions, its patch is standalone and thus should be merged
> regardless.

I think that we need to make the design of the driver easily
understandable to kernel developers and maintainable by them. I don't
think that this is 'standalone or not' issue.

Adding a doc about why the driver is designed in such odd way would be
helpful. But I still think that we could design the driver in a better
way.

Re: [PATCH 1/4] scatterlist: new helper functions

[Maxim Levitsky]

On Mon, 2011-03-07 at 06:49 +0900, FUJITA Tomonori wrote:
> On Sun, 06 Mar 2011 17:14:30 +0200
> Maxim Levitsky <maximlevitsky@gmail.com> wrote:
> 
> > On Sun, 2011-03-06 at 16:29 +0900, FUJITA Tomonori wrote:
> > > On Fri,  4 Mar 2011 06:16:50 +0200
> > > Maxim Levitsky <maximlevitsky@gmail.com> wrote:
> > > 
> > > > While developing memstick driver for legacy memsticks
> > > > I found the need in few helpers that I think should be
> > > > in common scatterlist library
> > > > 
> > > > The functions that were added:
> > > > 
> > > > * sg_nents/sg_total_len - iterate over scatterlist to figure
> > > > out total length of memory it covers / number of entries.
> > > 
> > > You should invent a data structure per I/O request, something like
> > > msb_request structure. Then you can store nents and total_len in
> > > that.
> > > 
> > > That's what block subsystems and drivers do. I took a look at your
> > > driver but I can't see why your driver can't do the same.
> > I also need to break the request into small grained chunks.
> > If I invent such structure, I will end up writing these helpers for it.
> > 
> > The I have this lifetime of a request:
> > 
> > I get arbitary sized request from block layer (I can of course control
> > maximum size/number of segments in it, etc).
> > 
> > I break it into eraseblock sized chunks, and for each I translate the
> > the LBA, into flash address.
> > 
> > Then I break it into flash page sized requests (512 bytes), and yet its
> > better not to assume that such requests always contained in one sg
> > entry.
> > 
> > Worse than that, I have to pass an sg list that spans always one 512
> > page to lowlevel driver, because thats how Alex defined the interface.
> 
> This restriction is due to hardware specification or the software
> design (e.g. memstick layer)? If it is due to the latter, why can't
> you fix that?

Yes.
I already tried addressing some shortcomings of memstick layer, no no, I
don't want to deal with its author, Alex Dubov again.
I think this code tries to be too clever/complex for the range of
devices/speeds it supports, but I rather leave it as is.


To be honest, the code in question is for >5 year old memstick standard
cards, thats hardly anybody uses.
It works, it is more or less simple, its not performance bound, its
testd, and thus I want to keep it as is _for_ now.


Why I break sg lists into chunks?
Because unlike vast majority of block devices, I need to do FTL in the
driver, thus its easier to work on eraseblock boundary.
Also unlike anything else, you can't just read/write a sector from a
memorystick (especially the legacy one), you have to perform full dance
of commands.

Not to mention error handling (like if you failed to write to block, you
must try to choose another one, etc...)

(Of course writes follow same rules as raw nand flash, thats is writes
only clear bits, and you can erase a eraseblock only).



> 
> Why can't the block layer split requests for you? It's better to let
> the block layer handle that.
You mean tell it not to give me more that one eraseblock to handle?
Could you explain that a bit more?


Anyway, could we merge the code?
I would happy to improve it later, but currently merge window is very
close, and the code is more or less agreed upon everyone, and written
more that 1/2 of year ago.

Andrew Morton, could you help me with this, Please?


Best regards,
	Maxim Levitsky

> 
> 
> > Folks, really what the status of this, when to expect it to be merged?
> > 
> > If you think some of helper functions don't belong to scatterlist.c,
> > just tell me to move them back to ms_block.c.
> > 
> > Andrew, please note again that richoh lowlevel driver doesn't need any
> > helper functions, its patch is standalone and thus should be merged
> > regardless.
> 
> I think that we need to make the design of the driver easily
> understandable to kernel developers and maintainable by them. I don't
> think that this is 'standalone or not' issue.
> 
> Adding a doc about why the driver is designed in such odd way would be
> helpful. But I still think that we could design the driver in a better
> way.

Re: [PATCH 1/4] scatterlist: new helper functions

[Maxim Levitsky]

On Mon, 2011-03-07 at 04:20 +0200, Maxim Levitsky wrote:
> On Mon, 2011-03-07 at 06:49 +0900, FUJITA Tomonori wrote:
> > On Sun, 06 Mar 2011 17:14:30 +0200
> > Maxim Levitsky <maximlevitsky@gmail.com> wrote:
> > 
> > > On Sun, 2011-03-06 at 16:29 +0900, FUJITA Tomonori wrote:
> > > > On Fri,  4 Mar 2011 06:16:50 +0200
> > > > Maxim Levitsky <maximlevitsky@gmail.com> wrote:
> > > > 
> > > > > While developing memstick driver for legacy memsticks
> > > > > I found the need in few helpers that I think should be
> > > > > in common scatterlist library
> > > > > 
> > > > > The functions that were added:
> > > > > 
> > > > > * sg_nents/sg_total_len - iterate over scatterlist to figure
> > > > > out total length of memory it covers / number of entries.
> > > > 
> > > > You should invent a data structure per I/O request, something like
> > > > msb_request structure. Then you can store nents and total_len in
> > > > that.
> > > > 
> > > > That's what block subsystems and drivers do. I took a look at your
> > > > driver but I can't see why your driver can't do the same.
> > > I also need to break the request into small grained chunks.
> > > If I invent such structure, I will end up writing these helpers for it.
> > > 
> > > The I have this lifetime of a request:
> > > 
> > > I get arbitary sized request from block layer (I can of course control
> > > maximum size/number of segments in it, etc).
> > > 
> > > I break it into eraseblock sized chunks, and for each I translate the
> > > the LBA, into flash address.
> > > 
> > > Then I break it into flash page sized requests (512 bytes), and yet its
> > > better not to assume that such requests always contained in one sg
> > > entry.
> > > 
> > > Worse than that, I have to pass an sg list that spans always one 512
> > > page to lowlevel driver, because thats how Alex defined the interface.
> > 
> > This restriction is due to hardware specification or the software
> > design (e.g. memstick layer)? If it is due to the latter, why can't
> > you fix that?
> 
> Yes.
> I already tried addressing some shortcomings of memstick layer, no no, I
> don't want to deal with its author, Alex Dubov again.
> I think this code tries to be too clever/complex for the range of
> devices/speeds it supports, but I rather leave it as is.
> 
> 
> To be honest, the code in question is for >5 year old memstick standard
> cards, thats hardly anybody uses.
> It works, it is more or less simple, its not performance bound, its
> testd, and thus I want to keep it as is _for_ now.
> 
> 
> Why I break sg lists into chunks?
> Because unlike vast majority of block devices, I need to do FTL in the
> driver, thus its easier to work on eraseblock boundary.
> Also unlike anything else, you can't just read/write a sector from a
> memorystick (especially the legacy one), you have to perform full dance
> of commands.
> 
> Not to mention error handling (like if you failed to write to block, you
> must try to choose another one, etc...)
> 
> (Of course writes follow same rules as raw nand flash, thats is writes
> only clear bits, and you can erase a eraseblock only).
> 
> 
> 
> > 
> > Why can't the block layer split requests for you? It's better to let
> > the block layer handle that.
> You mean tell it not to give me more that one eraseblock to handle?
> Could you explain that a bit more?
> 
> 
> Anyway, could we merge the code?
> I would happy to improve it later, but currently merge window is very
> close, and the code is more or less agreed upon everyone, and written
> more that 1/2 of year ago.
> 
> Andrew Morton, could you help me with this, Please?
Ping (I really worry about this).

> 
> 
> Best regards,
> 	Maxim Levitsky
> 
> > 
> > 
> > > Folks, really what the status of this, when to expect it to be merged?
> > > 
> > > If you think some of helper functions don't belong to scatterlist.c,
> > > just tell me to move them back to ms_block.c.
> > > 
> > > Andrew, please note again that richoh lowlevel driver doesn't need any
> > > helper functions, its patch is standalone and thus should be merged
> > > regardless.
> > 
> > I think that we need to make the design of the driver easily
> > understandable to kernel developers and maintainable by them. I don't
> > think that this is 'standalone or not' issue.
> > 
> > Adding a doc about why the driver is designed in such odd way would be
> > helpful. But I still think that we could design the driver in a better
> > way.
> 
> 

Re: [PATCH 1/4] scatterlist: new helper functions

[Andrew Morton]

On Mon, 07 Mar 2011 04:20:37 +0200 Maxim Levitsky <maximlevitsky@gmail.com> wrote:

> On Mon, 2011-03-07 at 06:49 +0900, FUJITA Tomonori wrote:
> > On Sun, 06 Mar 2011 17:14:30 +0200
> > Maxim Levitsky <maximlevitsky@gmail.com> wrote:
> > 
> > > On Sun, 2011-03-06 at 16:29 +0900, FUJITA Tomonori wrote:
> > > > On Fri,  4 Mar 2011 06:16:50 +0200
> > > > Maxim Levitsky <maximlevitsky@gmail.com> wrote:
> > > > 
> > > > > While developing memstick driver for legacy memsticks
> > > > > I found the need in few helpers that I think should be
> > > > > in common scatterlist library
> > > > > 
> > > > > The functions that were added:
> > > > > 
> > > > > * sg_nents/sg_total_len - iterate over scatterlist to figure
> > > > > out total length of memory it covers / number of entries.
> > > > 
> > > > You should invent a data structure per I/O request, something like
> > > > msb_request structure. Then you can store nents and total_len in
> > > > that.
> > > > 
> > > > That's what block subsystems and drivers do. I took a look at your
> > > > driver but I can't see why your driver can't do the same.
> > > I also need to break the request into small grained chunks.
> > > If I invent such structure, I will end up writing these helpers for it.
> > > 
> > > The I have this lifetime of a request:
> > > 
> > > I get arbitary sized request from block layer (I can of course control
> > > maximum size/number of segments in it, etc).
> > > 
> > > I break it into eraseblock sized chunks, and for each I translate the
> > > the LBA, into flash address.
> > > 
> > > Then I break it into flash page sized requests (512 bytes), and yet its
> > > better not to assume that such requests always contained in one sg
> > > entry.
> > > 
> > > Worse than that, I have to pass an sg list that spans always one 512
> > > page to lowlevel driver, because thats how Alex defined the interface.
> > 
> > This restriction is due to hardware specification or the software
> > design (e.g. memstick layer)? If it is due to the latter, why can't
> > you fix that?
> 
> Yes.
> I already tried addressing some shortcomings of memstick layer, no no, I
> don't want to deal with its author, Alex Dubov again.
> I think this code tries to be too clever/complex for the range of
> devices/speeds it supports, but I rather leave it as is.
> 

I have to say, these aren't very good reasons for a particular
implementation!

> To be honest, the code in question is for >5 year old memstick standard
> cards, thats hardly anybody uses.
> It works, it is more or less simple, its not performance bound, its
> testd, and thus I want to keep it as is _for_ now.
> 
> 
> Why I break sg lists into chunks?
> Because unlike vast majority of block devices, I need to do FTL in the
> driver, thus its easier to work on eraseblock boundary.
> Also unlike anything else, you can't just read/write a sector from a
> memorystick (especially the legacy one), you have to perform full dance
> of commands.
> 
> Not to mention error handling (like if you failed to write to block, you
> must try to choose another one, etc...)
> 
> (Of course writes follow same rules as raw nand flash, thats is writes
> only clear bits, and you can erase a eraseblock only).

hm.  If you think there's little likelihood that other drivers will
need the new sg functions in the future then perhaps they should be
made private to the memstick driver, rather than bloating everyone's
kernels.  Which is, I think, the exact opposite of what I suggested
last year :(

Fujita-san, you've gone all quiet.  Do you believe that these functions
should be added to the sg API?

Thanks.

Re: [PATCH 1/4] scatterlist: new helper functions

[FUJITA Tomonori]

On Tue, 15 Mar 2011 17:44:59 -0700
Andrew Morton <akpm@linux-foundation.org> wrote:

> > > This restriction is due to hardware specification or the software
> > > design (e.g. memstick layer)? If it is due to the latter, why can't
> > > you fix that?
> > 
> > Yes.
> > I already tried addressing some shortcomings of memstick layer, no no, I
> > don't want to deal with its author, Alex Dubov again.
> > I think this code tries to be too clever/complex for the range of
> > devices/speeds it supports, but I rather leave it as is.
> > 
> 
> I have to say, these aren't very good reasons for a particular
> implementation!

Agreed. We need to fix it.


> > To be honest, the code in question is for >5 year old memstick standard
> > cards, thats hardly anybody uses.
> > It works, it is more or less simple, its not performance bound, its
> > testd, and thus I want to keep it as is _for_ now.
> > 
> > 
> > Why I break sg lists into chunks?
> > Because unlike vast majority of block devices, I need to do FTL in the
> > driver, thus its easier to work on eraseblock boundary.
> > Also unlike anything else, you can't just read/write a sector from a
> > memorystick (especially the legacy one), you have to perform full dance
> > of commands.
> > 
> > Not to mention error handling (like if you failed to write to block, you
> > must try to choose another one, etc...)
> > 
> > (Of course writes follow same rules as raw nand flash, thats is writes
> > only clear bits, and you can erase a eraseblock only).
> 
> hm.  If you think there's little likelihood that other drivers will
> need the new sg functions in the future then perhaps they should be
> made private to the memstick driver, rather than bloating everyone's
> kernels.  Which is, I think, the exact opposite of what I suggested
> last year :(
> 
> Fujita-san, you've gone all quiet.  Do you believe that these functions
> should be added to the sg API?

I don't think so.

Splitting (or merging) a request and playing with sg lists inside a
driver is a bad idea. Such should be done in the block layer.

I still don't see why the block layer can't do that for the driver.

I believe that the helper functions for such should not be added.

Re: [PATCH 1/4] scatterlist: new helper functions

[Alex Dubov]

> 
> I don't think so.
> 
> Splitting (or merging) a request and playing with sg lists
> inside a
> driver is a bad idea. Such should be done in the block
> layer.
> 
> I still don't see why the block layer can't do that for the
> driver.
> 
> I believe that the helper functions for such should not be
> added.
> 


In a particular case of flash-like devices, letting the block layer
split requests into memory sequential blocks too often results in
unnecessary fragmentation of writes/erases.

If only one sg entry is requested from the block layer, it will be (more
often than not) only 1 or 2 pages in length, even if total size of
prospective write request spans multiple erase blocks.

So there are really only two options for legacy memorystick driver:
1. Play with scatterlists explicitly.
2. Make it an MTD backend, rather then stand-alone block device.

The second option makes more sense, but it is not necessarily the optimal
approach for implementation of this particular media format.



      

Re: [PATCH 1/4] scatterlist: new helper functions

[FUJITA Tomonori]

On Tue, 15 Mar 2011 21:18:14 -0700 (PDT)
Alex Dubov <oakad@yahoo.com> wrote:

> 
> > 
> > I don't think so.
> > 
> > Splitting (or merging) a request and playing with sg lists
> > inside a
> > driver is a bad idea. Such should be done in the block
> > layer.
> > 
> > I still don't see why the block layer can't do that for the
> > driver.
> > 
> > I believe that the helper functions for such should not be
> > added.
> > 
> 
> 
> In a particular case of flash-like devices, letting the block layer
> split requests into memory sequential blocks too often results in
> unnecessary fragmentation of writes/erases.

Why?

Why can't the block layer split a request in the way the driver wants
to do?

That is, why can't the driver tell the block layer how to split a
request?


> If only one sg entry is requested from the block layer, it will be (more
> often than not) only 1 or 2 pages in length, even if total size of
> prospective write request spans multiple erase blocks.

In this case, what does the driver do? Why can't the block layer do
the same?


> So there are really only two options for legacy memorystick driver:
> 1. Play with scatterlists explicitly.
> 2. Make it an MTD backend, rather then stand-alone block device.
> 
> The second option makes more sense, but it is not necessarily the optimal
> approach for implementation of this particular media format.
> 
> 
> 
>       
> --
> 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/

Re: [PATCH 1/4] scatterlist: new helper functions

[Alex Dubov]

> 
> Why?
> 
> Why can't the block layer split a request in the way the
> driver wants
> to do?
> 
> That is, why can't the driver tell the block layer how to
> split a
> request?

What is needed is the ability to get fixed sized (in bytes) blocks from 
the block layer.

Last time I checked (it was a long time ago, admittedly) one could only
ask for a fixed number of sg entries, without any control on how many
bytes each sg entry references.

Is there a way to get data from the block layer in a fashion of:
"Give me 16k/32k/whatever in one sg entry if request is equal or larger
than this"?

If my knowledge is correct, MTD currently addresses this issue by
maintaining its own cache, which it uses to aggregate write requests until
it can write a whole erase block. While this is ok with old media
(legacy memory stick being an example of such), new flash chips can
have multi-megabyte sized erase blocks and can benefit from operations
(like copy and compare) directly on scatter list .



      

Re: [PATCH 1/4] scatterlist: new helper functions

[James Bottomley]

On Wed, 2011-03-16 at 20:46 -0700, Alex Dubov wrote:
> > 
> > Why?
> > 
> > Why can't the block layer split a request in the way the
> > driver wants
> > to do?
> > 
> > That is, why can't the driver tell the block layer how to
> > split a
> > request?
> 
> What is needed is the ability to get fixed sized (in bytes) blocks from 
> the block layer.
> 
> Last time I checked (it was a long time ago, admittedly) one could only
> ask for a fixed number of sg entries, without any control on how many
> bytes each sg entry references.
> 
> Is there a way to get data from the block layer in a fashion of:
> "Give me 16k/32k/whatever in one sg entry if request is equal or larger
> than this"?

Yes; we've always had it: it's blk_max_queue_hw_sectors().  No request
will go over that number times the sector size (of course, they may go
under).

> If my knowledge is correct, MTD currently addresses this issue by
> maintaining its own cache, which it uses to aggregate write requests until
> it can write a whole erase block. While this is ok with old media
> (legacy memory stick being an example of such), new flash chips can
> have multi-megabyte sized erase blocks and can benefit from operations
> (like copy and compare) directly on scatter list .

So this is where you want a minimum too.  What you likely want is to set
the logical block size to your erase block
(blk_queue_logical_block_size) and the physical block size to the actual
block size.  Then we'll try as hard as we can to send down blocks on an
erase boundary.  Of course, there are some that just won't fit (like fs
metadata) and you'll have to do a RMW for them.

James

Re: [PATCH 1/4] scatterlist: new helper functions

[Andrew Morton]

On Tue, 15 Mar 2011 21:18:14 -0700 (PDT)
Alex Dubov <oakad@yahoo.com> wrote:

> 
> > 
> > I don't think so.
> > 
> > Splitting (or merging) a request and playing with sg lists
> > inside a
> > driver is a bad idea. Such should be done in the block
> > layer.
> > 
> > I still don't see why the block layer can't do that for the
> > driver.
> > 
> > I believe that the helper functions for such should not be
> > added.
> > 
> 
> 
> In a particular case of flash-like devices, letting the block layer
> split requests into memory sequential blocks too often results in
> unnecessary fragmentation of writes/erases.
> 
> If only one sg entry is requested from the block layer, it will be (more
> often than not) only 1 or 2 pages in length, even if total size of
> prospective write request spans multiple erase blocks.
> 
> So there are really only two options for legacy memorystick driver:
> 1. Play with scatterlists explicitly.
> 2. Make it an MTD backend, rather then stand-alone block device.
> 
> The second option makes more sense, but it is not necessarily the optimal
> approach for implementation of this particular media format.
> 

Thanks.

Do you believe that any other driver is likely to ue the sg
infrastructure which this patch adds?  Should those additions be 
internal to the memstick code, at least for now?

Re: [PATCH 1/4] scatterlist: new helper functions

[Alex Dubov]

> 
> Do you believe that any other driver is likely to ue the
> sg
> infrastructure which this patch adds?  Should those
> additions be 
> internal to the memstick code, at least for now?
> 

Considering the comments from Fujita and James, I suppose it will be best
for now to fold the new sg functions into the memstick patch and
investigate how the block layer functionality can be used to a greater
utility at some later time.


      

Re: [PATCH 1/4] scatterlist: new helper functions

[Maxim Levitsky]

On Wed, 2011-03-16 at 23:41 -0700, Alex Dubov wrote:
> > 
> > Do you believe that any other driver is likely to ue the
> > sg
> > infrastructure which this patch adds?  Should those
> > additions be 
> > internal to the memstick code, at least for now?
> > 
> 
> Considering the comments from Fujita and James, I suppose it will be best
> for now to fold the new sg functions into the memstick patch and
> investigate how the block layer functionality can be used to a greater
> utility at some later time.

I am thinking the same thing.
If the unusual sg code is a problem, I'll think of something later to
improve it, heck I can even completely rip it off and just use kernel
pointers, relying on block core to bounce for high-mem situations.
Since its a driver for a legacy hardware, mostly provided for
completeness, the performance difference shouldn't be much.


I think its ok to merge the code with folded sg code _for_ now, and then
I will send patches to address this point you didn't like.


OK?

Best regards,
	Maxim Levitsky 

Re: [PATCH 1/4] scatterlist: new helper functions

[FUJITA Tomonori]

On Wed, 16 Mar 2011 23:41:13 -0700 (PDT)
Alex Dubov <oakad@yahoo.com> wrote:

> Considering the comments from Fujita and James, I suppose it will be best
> for now to fold the new sg functions into the memstick patch and
> investigate how the block layer functionality can be used to a greater
> utility at some later time.

I suspect that such 'some later time' never come (especially for old
hardware). So I would prefer to merge the properly designed driver
rather than the current hacky driver.

[PATCH V2 0/4]: MEMSTICK: My 2 drivers for 2.6.38 inclusion

[Maxim Levitsky]

Hi, this is pretty much same version  as I sent yestarday.
I did a proofread of the commit messages, did a review of ms_block.c
during which I found misspelled debug message, and verified
that my port to sg_mitter in code that fills the sg with 0xFF
really works. 

This is pretty much merge worthy.

patch 1 - only commit message change
patch 2 - unchanged
patch 3 - commit message change + trivial string change
patch 4 - fix for a typo in contents

[PATCH 1/4] scatterlist: new helper functions

[Maxim Levitsky]

While developing memstick driver for legacy memsticks
I found the need in few helpers that I think should be
in common scatterlist library

The functions that were added:

* sg_nents/sg_total_len - iterate over scatterlist to figure
out total length of memory it covers / number of entries.
Useful for not keeping that information in side channels.

* sg_copy/sg_advance - Allow to break scatterlists apart into smaller chunks.
sg_copy creates smaller scatterlist, spanning first 'len' bytes, while
sg_advance edits the scatterlist in such way that it skips over 'len' bytes.


* sg_compare_to_buffer - another function to hide gory details of access
to sg list by CPU.
Allows to transparently compare contents of the sg list to given linear
buffer.
If needed later, a function that compares two sgs can be added.

All of this code is used by my ms_block.c driver.

Signed-off-by: Maxim Levitsky <maximlevitsky@gmail.com>
---
 include/linux/scatterlist.h |    6 ++
 lib/scatterlist.c           |  137 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 143 insertions(+), 0 deletions(-)

diff --git a/include/linux/scatterlist.h b/include/linux/scatterlist.h
index 9aaf5bf..6305589 100644
--- a/include/linux/scatterlist.h
+++ b/include/linux/scatterlist.h
@@ -199,6 +199,11 @@ static inline void *sg_virt(struct scatterlist *sg)
 	return page_address(sg_page(sg)) + sg->offset;
 }
 
+struct scatterlist *sg_advance(struct scatterlist *sg, int consumed);
+int sg_nents(struct scatterlist *sg);
+int sg_total_len(struct scatterlist *sg);
+int sg_copy(struct scatterlist *sg_from, struct scatterlist *sg_to, int len);
+
 struct scatterlist *sg_next(struct scatterlist *);
 struct scatterlist *sg_last(struct scatterlist *s, unsigned int);
 void sg_init_table(struct scatterlist *, unsigned int);
@@ -217,6 +222,7 @@ size_t sg_copy_from_buffer(struct scatterlist *sgl, unsigned int nents,
 			   void *buf, size_t buflen);
 size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents,
 			 void *buf, size_t buflen);
+bool sg_compare_to_buffer(struct scatterlist *sg, u8 *buffer, size_t len);
 
 /*
  * Maximum number of entries that will be allocated in one piece, if
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index 4ceb05d..2f18938 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -39,6 +39,77 @@ struct scatterlist *sg_next(struct scatterlist *sg)
 EXPORT_SYMBOL(sg_next);
 
 /**
+ * sg_advance - advance scatterlist by 'consumed' bytes
+ * @sg - the current sg entry
+ * @consumed - how much bytes to advance
+ *
+ */
+struct scatterlist *sg_advance(struct scatterlist *sg, int consumed)
+{
+	while (consumed >= sg->length) {
+		consumed -= sg->length;
+
+		sg = sg_next(sg);
+		if (!sg)
+			break;
+	}
+
+	WARN_ON(!sg && consumed);
+
+	if (!sg)
+		return NULL;
+
+	sg->offset += consumed;
+	sg->length -= consumed;
+
+	if (sg->offset >= PAGE_SIZE) {
+		struct page *page =
+			nth_page(sg_page(sg), sg->offset / PAGE_SIZE);
+		sg_set_page(sg, page, sg->length, sg->offset % PAGE_SIZE);
+	}
+
+	return sg;
+}
+EXPORT_SYMBOL(sg_advance);
+
+/**
+ * sg_nents - calculate number of sg entries in sg list
+ * @sg - the current sg entry
+ *
+ * Allows to calculate dynamicly the lenght of the sg table, based on
+ * assumption that last entry is NULL
+ */
+int sg_nents(struct scatterlist *sg)
+{
+	int nents = 0;
+	while (sg) {
+		nents++;
+		sg = sg_next(sg);
+	}
+
+	return nents;
+}
+EXPORT_SYMBOL(sg_nents);
+
+/**
+ * sg_total_len - calculate total lenght of scatterlist
+ * @sg - the current sg entry
+ *
+ * Dynamicly calculate total number of bytes in a sg list
+ * based on assumption that list ends with a NULL entry
+ */
+int sg_total_len(struct scatterlist *sg)
+{
+	int len = 0;
+	while (sg) {
+		len += sg->length;
+		sg = sg_next(sg);
+	}
+	return len;
+}
+EXPORT_SYMBOL(sg_total_len);
+
+/**
  * sg_last - return the last scatterlist entry in a list
  * @sgl:	First entry in the scatterlist
  * @nents:	Number of entries in the scatterlist
@@ -110,6 +181,33 @@ void sg_init_one(struct scatterlist *sg, const void *buf, unsigned int buflen)
 }
 EXPORT_SYMBOL(sg_init_one);
 
+/**
+ * sg_copy - copies sg entries from sg_from to sg_to, such
+ * as sg_to covers first 'len' bytes from sg_from.
+ */
+int sg_copy(struct scatterlist *sg_from, struct scatterlist *sg_to, int len)
+{
+	while (len > sg_from->length) {
+		len -= sg_from->length;
+
+		sg_set_page(sg_to, sg_page(sg_from),
+				sg_from->length, sg_from->offset);
+
+		sg_to = sg_next(sg_to);
+		sg_from = sg_next(sg_from);
+
+		if (len && (!sg_from || !sg_to))
+			return -ENOMEM;
+	}
+
+	if (len)
+		sg_set_page(sg_to, sg_page(sg_from),
+				len, sg_from->offset);
+	sg_mark_end(sg_to);
+	return 0;
+}
+EXPORT_SYMBOL(sg_copy);
+
 /*
  * The default behaviour of sg_alloc_table() is to use these kmalloc/kfree
  * helpers.
@@ -517,3 +615,42 @@ size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents,
 	return sg_copy_buffer(sgl, nents, buf, buflen, 1);
 }
 EXPORT_SYMBOL(sg_copy_to_buffer);
+
+
+/**
+ * sg_compare_to_buffer - compare contents of the data pointeted by sg table
+ * to a kernel ram buffer
+ * @sg - the current sg entry
+ * @buffer - linear buffer to compare with
+ * @len - lenght of that buffer
+ */
+bool sg_compare_to_buffer(struct scatterlist *sg, u8 *buffer, size_t len)
+{
+	unsigned long flags;
+	int retval = 0;
+	struct sg_mapping_iter miter;
+
+	if (sg_total_len(sg) < len)
+		return 1;
+
+	local_irq_save(flags);
+	sg_miter_start(&miter, sg, sg_nents(sg),
+				SG_MITER_ATOMIC | SG_MITER_FROM_SG);
+
+	while (sg_miter_next(&miter) && len > 0) {
+
+		int cmplen = min(miter.length, len);
+		if (memcmp(miter.addr, buffer, cmplen)) {
+			retval = 1;
+			break;
+		}
+
+		buffer += cmplen;
+		len -= cmplen;
+	}
+
+	sg_miter_stop(&miter);
+	local_irq_restore(flags);
+	return retval;
+}
+EXPORT_SYMBOL(sg_compare_to_buffer);
-- 
1.7.1

Re: [PATCH 1/4] scatterlist: new helper functions

[Randy Dunlap]

On Wed, 12 Jan 2011 01:36:12 +0200 Maxim Levitsky wrote:

> While developing memstick driver for legacy memsticks
> I found the need in few helpers that I think should be
> in common scatterlist library
> 
> The functions that were added:
> 
> * sg_nents/sg_total_len - iterate over scatterlist to figure
> out total length of memory it covers / number of entries.
> Useful for not keeping that information in side channels.
> 
> * sg_copy/sg_advance - Allow to break scatterlists apart into smaller chunks.
> sg_copy creates smaller scatterlist, spanning first 'len' bytes, while
> sg_advance edits the scatterlist in such way that it skips over 'len' bytes.
> 
> 
> * sg_compare_to_buffer - another function to hide gory details of access
> to sg list by CPU.
> Allows to transparently compare contents of the sg list to given linear
> buffer.
> If needed later, a function that compares two sgs can be added.
> 
> All of this code is used by my ms_block.c driver.
> 
> ---
>  include/linux/scatterlist.h |    6 ++
>  lib/scatterlist.c           |  137 +++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 143 insertions(+), 0 deletions(-)


> diff --git a/lib/scatterlist.c b/lib/scatterlist.c
> index 4ceb05d..2f18938 100644
> --- a/lib/scatterlist.c
> +++ b/lib/scatterlist.c
> @@ -39,6 +39,77 @@ struct scatterlist *sg_next(struct scatterlist *sg)
>  EXPORT_SYMBOL(sg_next);
>  
>  /**
> + * sg_advance - advance scatterlist by 'consumed' bytes
> + * @sg - the current sg entry
> + * @consumed - how much bytes to advance

kernel-doc notation for parameters is like so:

 * @sg: the current sg entry

> + *

no empty line, please.

> + */
> +struct scatterlist *sg_advance(struct scatterlist *sg, int consumed)
> +{
> +	while (consumed >= sg->length) {
> +		consumed -= sg->length;
> +
> +		sg = sg_next(sg);
> +		if (!sg)
> +			break;
> +	}
> +
> +	WARN_ON(!sg && consumed);
> +
> +	if (!sg)
> +		return NULL;
> +
> +	sg->offset += consumed;
> +	sg->length -= consumed;
> +
> +	if (sg->offset >= PAGE_SIZE) {
> +		struct page *page =
> +			nth_page(sg_page(sg), sg->offset / PAGE_SIZE);
> +		sg_set_page(sg, page, sg->length, sg->offset % PAGE_SIZE);
> +	}
> +
> +	return sg;
> +}
> +EXPORT_SYMBOL(sg_advance);
> +
> +/**
> + * sg_nents - calculate number of sg entries in sg list
> + * @sg - the current sg entry

 * @sg:

> + *
> + * Allows to calculate dynamicly the lenght of the sg table, based on

                          dynamically the length

> + * assumption that last entry is NULL
> + */
> +int sg_nents(struct scatterlist *sg)
> +{
> +	int nents = 0;
> +	while (sg) {
> +		nents++;
> +		sg = sg_next(sg);
> +	}
> +
> +	return nents;
> +}
> +EXPORT_SYMBOL(sg_nents);
> +
> +/**
> + * sg_total_len - calculate total lenght of scatterlist

                                     length

> + * @sg - the current sg entry

 * @sg:

> + *
> + * Dynamicly calculate total number of bytes in a sg list

      Dynamically                               in an sg list

> + * based on assumption that list ends with a NULL entry
> + */
> +int sg_total_len(struct scatterlist *sg)
> +{
> +	int len = 0;
> +	while (sg) {
> +		len += sg->length;
> +		sg = sg_next(sg);
> +	}
> +	return len;
> +}
> +EXPORT_SYMBOL(sg_total_len);
> +
> +/**
>   * sg_last - return the last scatterlist entry in a list
>   * @sgl:	First entry in the scatterlist
>   * @nents:	Number of entries in the scatterlist
> @@ -110,6 +181,33 @@ void sg_init_one(struct scatterlist *sg, const void *buf, unsigned int buflen)
>  }
>  EXPORT_SYMBOL(sg_init_one);
>  
> +/**
> + * sg_copy - copies sg entries from sg_from to sg_to, such
> + * as sg_to covers first 'len' bytes from sg_from.

Add function parameters to kernel-doc, please.

> + */
> +int sg_copy(struct scatterlist *sg_from, struct scatterlist *sg_to, int len)
> +{
> +	while (len > sg_from->length) {
> +		len -= sg_from->length;
> +
> +		sg_set_page(sg_to, sg_page(sg_from),
> +				sg_from->length, sg_from->offset);
> +
> +		sg_to = sg_next(sg_to);
> +		sg_from = sg_next(sg_from);
> +
> +		if (len && (!sg_from || !sg_to))
> +			return -ENOMEM;
> +	}
> +
> +	if (len)
> +		sg_set_page(sg_to, sg_page(sg_from),
> +				len, sg_from->offset);
> +	sg_mark_end(sg_to);
> +	return 0;
> +}
> +EXPORT_SYMBOL(sg_copy);
> +
>  /*
>   * The default behaviour of sg_alloc_table() is to use these kmalloc/kfree
>   * helpers.
> @@ -517,3 +615,42 @@ size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents,
>  	return sg_copy_buffer(sgl, nents, buf, buflen, 1);
>  }
>  EXPORT_SYMBOL(sg_copy_to_buffer);
> +
> +
> +/**
> + * sg_compare_to_buffer - compare contents of the data pointeted by sg table

                                                          pointed to by sg table

> + * to a kernel ram buffer

                  RAM

> + * @sg - the current sg entry
> + * @buffer - linear buffer to compare with
> + * @len - lenght of that buffer

 * @sg:
 * @buffer:
 * @len: length

Returns 0 for equal or what??

> + */
> +bool sg_compare_to_buffer(struct scatterlist *sg, u8 *buffer, size_t len)
> +{


Thanks for adding the kernel-doc.

---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***

Re: [PATCH 1/4] scatterlist: new helper functions

[Andrew Morton]

On Tue, 11 Jan 2011 15:51:24 -0800
Randy Dunlap <rdunlap@xenotime.net> wrote:

> >  /**
> > + * sg_advance - advance scatterlist by 'consumed' bytes
> > + * @sg - the current sg entry
> > + * @consumed - how much bytes to advance
> 
> kernel-doc notation for parameters is like so:

I think I fixed most of this.  Probably missed some though.

Teach checkpatch to check kerneldoc ;)



From: Andrew Morton <akpm@linux-foundation.org>

fix general disaster in code comments

Cc: Alex Dubov <oakad@yahoo.com>
Cc: James Bottomley <James.Bottomley@HansenPartnership.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: Maxim Levitsky <maximlevitsky@gmail.com>
Cc: Tejun Heo <tj@kernel.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 lib/scatterlist.c |   31 ++++++++++++++++++-------------
 1 file changed, 18 insertions(+), 13 deletions(-)

diff -puN lib/scatterlist.c~scatterlist-new-helper-functions-fix lib/scatterlist.c
--- a/lib/scatterlist.c~scatterlist-new-helper-functions-fix
+++ a/lib/scatterlist.c
@@ -41,7 +41,7 @@ EXPORT_SYMBOL(sg_next);
 /**
  * sg_advance - advance scatterlist by 'consumed' bytes
  * @sg - the current sg entry
- * @consumed - how much bytes to advance
+ * @consumed - how many bytes to advance
  *
  */
 struct scatterlist *sg_advance(struct scatterlist *sg, int consumed)
@@ -76,8 +76,8 @@ EXPORT_SYMBOL(sg_advance);
  * sg_nents - calculate number of sg entries in sg list
  * @sg - the current sg entry
  *
- * Allows to calculate dynamicly the lenght of the sg table, based on
- * assumption that last entry is NULL
+ * Allows to calculate aldynamicly the length of the sg table, based on an
+ * assumption that the last entry is NULL
  */
 int sg_nents(struct scatterlist *sg)
 {
@@ -92,11 +92,11 @@ int sg_nents(struct scatterlist *sg)
 EXPORT_SYMBOL(sg_nents);
 
 /**
- * sg_total_len - calculate total lenght of scatterlist
+ * sg_total_len - calculate total length of scatterlist
  * @sg - the current sg entry
  *
- * Dynamicly calculate total number of bytes in a sg list
- * based on assumption that list ends with a NULL entry
+ * Dynamically calculate total number of bytes in a sg list
+ * based on an assumption that the list ends with a NULL entry
  */
 int sg_total_len(struct scatterlist *sg)
 {
@@ -182,8 +182,14 @@ void sg_init_one(struct scatterlist *sg,
 EXPORT_SYMBOL(sg_init_one);
 
 /**
- * sg_copy - copies sg entries from sg_from to sg_to, such
- * as sg_to covers first 'len' bytes from sg_from.
+ * sg_copy - copy sg entries
+ * @sg_from: source
+ * @sg_to: destination
+ *
+ * Copies from @sg_from to @sg_to.  @sg_to covers first 'len' bytes from
+ * @sg_from.
+ *
+ * Returns zero on success, else a -ve errno.
  */
 int sg_copy(struct scatterlist *sg_from, struct scatterlist *sg_to, int len)
 {
@@ -616,13 +622,12 @@ size_t sg_copy_to_buffer(struct scatterl
 }
 EXPORT_SYMBOL(sg_copy_to_buffer);
 
-
 /**
- * sg_compare_to_buffer - compare contents of the data pointeted by sg table
+ * sg_compare_to_buffer - compare contents of the data covered by an sg table
  * to a kernel ram buffer
- * @sg - the current sg entry
- * @buffer - linear buffer to compare with
- * @len - lenght of that buffer
+ * @sg: the current sg entry
+ * @buffer: linear buffer to compare with
+ * @len: length of that buffer
  */
 bool sg_compare_to_buffer(struct scatterlist *sg, u8 *buffer, size_t len)
 {
_

Re: [PATCH 1/4] scatterlist: new helper functions

[Randy Dunlap]

On Tue, 11 Jan 2011 15:55:11 -0800 Andrew Morton wrote:

> On Tue, 11 Jan 2011 15:51:24 -0800
> Randy Dunlap <rdunlap@xenotime.net> wrote:
> 
> > >  /**
> > > + * sg_advance - advance scatterlist by 'consumed' bytes
> > > + * @sg - the current sg entry
> > > + * @consumed - how much bytes to advance
> > 
> > kernel-doc notation for parameters is like so:
> 
> I think I fixed most of this.  Probably missed some though.
> 
> Teach checkpatch to check kerneldoc ;)
> 

ugh, no thanks.

> 
> 
> From: Andrew Morton <akpm@linux-foundation.org>
> 
> fix general disaster in code comments
> 
> Cc: Alex Dubov <oakad@yahoo.com>
> Cc: James Bottomley <James.Bottomley@HansenPartnership.com>
> Cc: Jens Axboe <axboe@kernel.dk>
> Cc: Maxim Levitsky <maximlevitsky@gmail.com>
> Cc: Tejun Heo <tj@kernel.org>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> ---
> 
>  lib/scatterlist.c |   31 ++++++++++++++++++-------------
>  1 file changed, 18 insertions(+), 13 deletions(-)
> 
> diff -puN lib/scatterlist.c~scatterlist-new-helper-functions-fix lib/scatterlist.c
> --- a/lib/scatterlist.c~scatterlist-new-helper-functions-fix
> +++ a/lib/scatterlist.c
> @@ -41,7 +41,7 @@ EXPORT_SYMBOL(sg_next);
>  /**
>   * sg_advance - advance scatterlist by 'consumed' bytes
>   * @sg - the current sg entry
> - * @consumed - how much bytes to advance
> + * @consumed - how many bytes to advance

 * @consumed: how many bytes to advance

>   *
>   */
>  struct scatterlist *sg_advance(struct scatterlist *sg, int consumed)
> @@ -76,8 +76,8 @@ EXPORT_SYMBOL(sg_advance);
>   * sg_nents - calculate number of sg entries in sg list
>   * @sg - the current sg entry

 * @sg:

>   *
> - * Allows to calculate dynamicly the lenght of the sg table, based on
> - * assumption that last entry is NULL
> + * Allows to calculate aldynamicly the length of the sg table, based on an
> + * assumption that the last entry is NULL
>   */
>  int sg_nents(struct scatterlist *sg)
>  {
> @@ -92,11 +92,11 @@ int sg_nents(struct scatterlist *sg)
>  EXPORT_SYMBOL(sg_nents);
>  
>  /**
> - * sg_total_len - calculate total lenght of scatterlist
> + * sg_total_len - calculate total length of scatterlist
>   * @sg - the current sg entry

 * @sg:

>   *
> - * Dynamicly calculate total number of bytes in a sg list
> - * based on assumption that list ends with a NULL entry
> + * Dynamically calculate total number of bytes in a sg list

preferably:
                                                  in an sg list

> + * based on an assumption that the list ends with a NULL entry
>   */
>  int sg_total_len(struct scatterlist *sg)
>  {
> @@ -182,8 +182,14 @@ void sg_init_one(struct scatterlist *sg,
>  EXPORT_SYMBOL(sg_init_one);
>  
>  /**
> - * sg_copy - copies sg entries from sg_from to sg_to, such
> - * as sg_to covers first 'len' bytes from sg_from.
> + * sg_copy - copy sg entries
> + * @sg_from: source
> + * @sg_to: destination
> + *
> + * Copies from @sg_from to @sg_to.  @sg_to covers first 'len' bytes from
> + * @sg_from.
> + *
> + * Returns zero on success, else a -ve errno.
>   */
>  int sg_copy(struct scatterlist *sg_from, struct scatterlist *sg_to, int len)
>  {
> @@ -616,13 +622,12 @@ size_t sg_copy_to_buffer(struct scatterl
>  }
>  EXPORT_SYMBOL(sg_copy_to_buffer);
>  
> -
>  /**
> - * sg_compare_to_buffer - compare contents of the data pointeted by sg table
> + * sg_compare_to_buffer - compare contents of the data covered by an sg table
>   * to a kernel ram buffer
> - * @sg - the current sg entry
> - * @buffer - linear buffer to compare with
> - * @len - lenght of that buffer
> + * @sg: the current sg entry
> + * @buffer: linear buffer to compare with
> + * @len: length of that buffer

Returns what??

>   */
>  bool sg_compare_to_buffer(struct scatterlist *sg, u8 *buffer, size_t len)
>  {
> _
> 


---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***

Re: [PATCH 1/4] scatterlist: new helper functions

[Maxim Levitsky]

On Tue, 2011-01-11 at 15:58 -0800, Randy Dunlap wrote:
> On Tue, 11 Jan 2011 15:55:11 -0800 Andrew Morton wrote:
> 
> > On Tue, 11 Jan 2011 15:51:24 -0800
> > Randy Dunlap <rdunlap@xenotime.net> wrote:
> > 
> > > >  /**
> > > > + * sg_advance - advance scatterlist by 'consumed' bytes
> > > > + * @sg - the current sg entry
> > > > + * @consumed - how much bytes to advance
> > > 
> > > kernel-doc notation for parameters is like so:
> > 
> > I think I fixed most of this.  Probably missed some though.
> > 
> > Teach checkpatch to check kerneldoc ;)
> > 
> 
> ugh, no thanks.
> 
> > 
> > 
> > From: Andrew Morton <akpm@linux-foundation.org>
> > 
> > fix general disaster in code comments
> > 
> > Cc: Alex Dubov <oakad@yahoo.com>
> > Cc: James Bottomley <James.Bottomley@HansenPartnership.com>
> > Cc: Jens Axboe <axboe@kernel.dk>
> > Cc: Maxim Levitsky <maximlevitsky@gmail.com>
> > Cc: Tejun Heo <tj@kernel.org>
> > Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> > ---
> > 
> >  lib/scatterlist.c |   31 ++++++++++++++++++-------------
> >  1 file changed, 18 insertions(+), 13 deletions(-)
> > 
> > diff -puN lib/scatterlist.c~scatterlist-new-helper-functions-fix lib/scatterlist.c
> > --- a/lib/scatterlist.c~scatterlist-new-helper-functions-fix
> > +++ a/lib/scatterlist.c
> > @@ -41,7 +41,7 @@ EXPORT_SYMBOL(sg_next);
> >  /**
> >   * sg_advance - advance scatterlist by 'consumed' bytes
> >   * @sg - the current sg entry
> > - * @consumed - how much bytes to advance
> > + * @consumed - how many bytes to advance
> 
>  * @consumed: how many bytes to advance
> 
> >   *
> >   */
> >  struct scatterlist *sg_advance(struct scatterlist *sg, int consumed)
> > @@ -76,8 +76,8 @@ EXPORT_SYMBOL(sg_advance);
> >   * sg_nents - calculate number of sg entries in sg list
> >   * @sg - the current sg entry
> 
>  * @sg:
> 
> >   *
> > - * Allows to calculate dynamicly the lenght of the sg table, based on
> > - * assumption that last entry is NULL
> > + * Allows to calculate aldynamicly the length of the sg table, based on an
> > + * assumption that the last entry is NULL
> >   */
> >  int sg_nents(struct scatterlist *sg)
> >  {
> > @@ -92,11 +92,11 @@ int sg_nents(struct scatterlist *sg)
> >  EXPORT_SYMBOL(sg_nents);
> >  
> >  /**
> > - * sg_total_len - calculate total lenght of scatterlist
> > + * sg_total_len - calculate total length of scatterlist
> >   * @sg - the current sg entry
> 
>  * @sg:
> 
> >   *
> > - * Dynamicly calculate total number of bytes in a sg list
> > - * based on assumption that list ends with a NULL entry
> > + * Dynamically calculate total number of bytes in a sg list
> 
> preferably:
>                                                   in an sg list
> 
> > + * based on an assumption that the list ends with a NULL entry
> >   */
> >  int sg_total_len(struct scatterlist *sg)
> >  {
> > @@ -182,8 +182,14 @@ void sg_init_one(struct scatterlist *sg,
> >  EXPORT_SYMBOL(sg_init_one);
> >  
> >  /**
> > - * sg_copy - copies sg entries from sg_from to sg_to, such
> > - * as sg_to covers first 'len' bytes from sg_from.
> > + * sg_copy - copy sg entries
> > + * @sg_from: source
> > + * @sg_to: destination
> > + *
> > + * Copies from @sg_from to @sg_to.  @sg_to covers first 'len' bytes from
> > + * @sg_from.
> > + *
> > + * Returns zero on success, else a -ve errno.
> >   */
> >  int sg_copy(struct scatterlist *sg_from, struct scatterlist *sg_to, int len)
> >  {
> > @@ -616,13 +622,12 @@ size_t sg_copy_to_buffer(struct scatterl
> >  }
> >  EXPORT_SYMBOL(sg_copy_to_buffer);
> >  
> > -
> >  /**
> > - * sg_compare_to_buffer - compare contents of the data pointeted by sg table
> > + * sg_compare_to_buffer - compare contents of the data covered by an sg table
> >   * to a kernel ram buffer
> > - * @sg - the current sg entry
> > - * @buffer - linear buffer to compare with
> > - * @len - lenght of that buffer
> > + * @sg: the current sg entry
> > + * @buffer: linear buffer to compare with
> > + * @len: length of that buffer
> 
> Returns what??
0 if equal and 1 otherwise.
Was too lazy to implement full strcmp compliance.
Is that needed?


All very fair comments.
Will check everything once again.
Thanks for a review!

Best regards,
	Maxim Levitsky

Re: [PATCH 1/4] scatterlist: new helper functions

[Randy Dunlap]

On Wed, 12 Jan 2011 04:52:29 +0200 Maxim Levitsky wrote:


> > >  /**
> > > - * sg_compare_to_buffer - compare contents of the data pointeted by sg table
> > > + * sg_compare_to_buffer - compare contents of the data covered by an sg table
> > >   * to a kernel ram buffer
> > > - * @sg - the current sg entry
> > > - * @buffer - linear buffer to compare with
> > > - * @len - lenght of that buffer
> > > + * @sg: the current sg entry
> > > + * @buffer: linear buffer to compare with
> > > + * @len: length of that buffer
> > 
> > Returns what??
> 0 if equal and 1 otherwise.
> Was too lazy to implement full strcmp compliance.
> Is that needed?

Not that I know of, just what the function returns was needed.


> All very fair comments.
> Will check everything once again.
> Thanks for a review!
> 
> Best regards,
> 	Maxim Levitsky
> 
> --

---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***

MEMSTICK: My 2 drivers for 2.6.38 inclusion

[Maxim Levitsky]

Hi,

The following patches hopefully address all comments on my code.

I would really be glad to see them in 2.6.38, as many users request me of doing so.

Best regards,
	Maxim Levitsky

[PATCH 1/4] scatterlist: new helper functions

[Maxim Levitsky]

While developing memstick driver for legacy memsticks
I found the need in few helpers that I think are ok
to have in common sg library

The functions that were added:

* sg_nents/sg_total_len - interate over sg list to figure
out its total len, number of entries.
Useful for not keeping that information in side channels.

* sg_copy/sg_advance - Alow to break sg lists apart into smaller chunks.
sg_copy creates smaller sg list spanning first 'len' bytes, while
sg_advance edits the sg list in such way that it skips over 'len' bytes.


* sg_compare_to_buffer - another function to hide gory details of access
to sg list by CPU.
Allows to transparetly compare contents of the sg list to given linear
buffer.
If needed later, a function that compares two sgs can be added.

All of this code is used by my ms_block.c driver.

Signed-off-by: Maxim Levitsky <maximlevitsky@gmail.com>
---
 include/linux/scatterlist.h |    6 ++
 lib/scatterlist.c           |  137 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 143 insertions(+), 0 deletions(-)

diff --git a/include/linux/scatterlist.h b/include/linux/scatterlist.h
index 9aaf5bf..6305589 100644
--- a/include/linux/scatterlist.h
+++ b/include/linux/scatterlist.h
@@ -199,6 +199,11 @@ static inline void *sg_virt(struct scatterlist *sg)
 	return page_address(sg_page(sg)) + sg->offset;
 }
 
+struct scatterlist *sg_advance(struct scatterlist *sg, int consumed);
+int sg_nents(struct scatterlist *sg);
+int sg_total_len(struct scatterlist *sg);
+int sg_copy(struct scatterlist *sg_from, struct scatterlist *sg_to, int len);
+
 struct scatterlist *sg_next(struct scatterlist *);
 struct scatterlist *sg_last(struct scatterlist *s, unsigned int);
 void sg_init_table(struct scatterlist *, unsigned int);
@@ -217,6 +222,7 @@ size_t sg_copy_from_buffer(struct scatterlist *sgl, unsigned int nents,
 			   void *buf, size_t buflen);
 size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents,
 			 void *buf, size_t buflen);
+bool sg_compare_to_buffer(struct scatterlist *sg, u8 *buffer, size_t len);
 
 /*
  * Maximum number of entries that will be allocated in one piece, if
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index 4ceb05d..2f18938 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -39,6 +39,77 @@ struct scatterlist *sg_next(struct scatterlist *sg)
 EXPORT_SYMBOL(sg_next);
 
 /**
+ * sg_advance - advance scatterlist by 'consumed' bytes
+ * @sg - the current sg entry
+ * @consumed - how much bytes to advance
+ *
+ */
+struct scatterlist *sg_advance(struct scatterlist *sg, int consumed)
+{
+	while (consumed >= sg->length) {
+		consumed -= sg->length;
+
+		sg = sg_next(sg);
+		if (!sg)
+			break;
+	}
+
+	WARN_ON(!sg && consumed);
+
+	if (!sg)
+		return NULL;
+
+	sg->offset += consumed;
+	sg->length -= consumed;
+
+	if (sg->offset >= PAGE_SIZE) {
+		struct page *page =
+			nth_page(sg_page(sg), sg->offset / PAGE_SIZE);
+		sg_set_page(sg, page, sg->length, sg->offset % PAGE_SIZE);
+	}
+
+	return sg;
+}
+EXPORT_SYMBOL(sg_advance);
+
+/**
+ * sg_nents - calculate number of sg entries in sg list
+ * @sg - the current sg entry
+ *
+ * Allows to calculate dynamicly the lenght of the sg table, based on
+ * assumption that last entry is NULL
+ */
+int sg_nents(struct scatterlist *sg)
+{
+	int nents = 0;
+	while (sg) {
+		nents++;
+		sg = sg_next(sg);
+	}
+
+	return nents;
+}
+EXPORT_SYMBOL(sg_nents);
+
+/**
+ * sg_total_len - calculate total lenght of scatterlist
+ * @sg - the current sg entry
+ *
+ * Dynamicly calculate total number of bytes in a sg list
+ * based on assumption that list ends with a NULL entry
+ */
+int sg_total_len(struct scatterlist *sg)
+{
+	int len = 0;
+	while (sg) {
+		len += sg->length;
+		sg = sg_next(sg);
+	}
+	return len;
+}
+EXPORT_SYMBOL(sg_total_len);
+
+/**
  * sg_last - return the last scatterlist entry in a list
  * @sgl:	First entry in the scatterlist
  * @nents:	Number of entries in the scatterlist
@@ -110,6 +181,33 @@ void sg_init_one(struct scatterlist *sg, const void *buf, unsigned int buflen)
 }
 EXPORT_SYMBOL(sg_init_one);
 
+/**
+ * sg_copy - copies sg entries from sg_from to sg_to, such
+ * as sg_to covers first 'len' bytes from sg_from.
+ */
+int sg_copy(struct scatterlist *sg_from, struct scatterlist *sg_to, int len)
+{
+	while (len > sg_from->length) {
+		len -= sg_from->length;
+
+		sg_set_page(sg_to, sg_page(sg_from),
+				sg_from->length, sg_from->offset);
+
+		sg_to = sg_next(sg_to);
+		sg_from = sg_next(sg_from);
+
+		if (len && (!sg_from || !sg_to))
+			return -ENOMEM;
+	}
+
+	if (len)
+		sg_set_page(sg_to, sg_page(sg_from),
+				len, sg_from->offset);
+	sg_mark_end(sg_to);
+	return 0;
+}
+EXPORT_SYMBOL(sg_copy);
+
 /*
  * The default behaviour of sg_alloc_table() is to use these kmalloc/kfree
  * helpers.
@@ -517,3 +615,42 @@ size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents,
 	return sg_copy_buffer(sgl, nents, buf, buflen, 1);
 }
 EXPORT_SYMBOL(sg_copy_to_buffer);
+
+
+/**
+ * sg_compare_to_buffer - compare contents of the data pointeted by sg table
+ * to a kernel ram buffer
+ * @sg - the current sg entry
+ * @buffer - linear buffer to compare with
+ * @len - lenght of that buffer
+ */
+bool sg_compare_to_buffer(struct scatterlist *sg, u8 *buffer, size_t len)
+{
+	unsigned long flags;
+	int retval = 0;
+	struct sg_mapping_iter miter;
+
+	if (sg_total_len(sg) < len)
+		return 1;
+
+	local_irq_save(flags);
+	sg_miter_start(&miter, sg, sg_nents(sg),
+				SG_MITER_ATOMIC | SG_MITER_FROM_SG);
+
+	while (sg_miter_next(&miter) && len > 0) {
+
+		int cmplen = min(miter.length, len);
+		if (memcmp(miter.addr, buffer, cmplen)) {
+			retval = 1;
+			break;
+		}
+
+		buffer += cmplen;
+		len -= cmplen;
+	}
+
+	sg_miter_stop(&miter);
+	local_irq_restore(flags);
+	return retval;
+}
+EXPORT_SYMBOL(sg_compare_to_buffer);
-- 
1.7.1