Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-21 Thread Jonathan Corbet 
On Wed, 21 Feb 2018 14:29:06 -0800
Kees Cook  wrote:

> >> I wonder if this might be more readable by splitting the kernel-doc
> >> changes from the bitmap changes? I.e. fix all the kernel-doc in one
> >> patch, and in the following, make the bitmap changes. Maybe it's such
> >> a small part that it doesn't matter, though?  
> >
> > I had the same thought, but then I would have made most of the kerneldoc
> > changes to something that would be altered by the following patch,
> > because it would have made little sense to fix only those parts that
> > would have survived.
> >
> > If it is really a problem to keep them together, I could put these
> > changes in a following patch. Would that be ok?  
> 
> Hmmm... I think keeping it as-is would be better than a trailing
> docs-only patch. Maybe Jon has an opinion?

I would be inclined to agree.  Putting docs changes with the associated
code changes helps to document the patch itself, among other things.  I
wouldn't split them up.

jon

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-21 Thread Jonathan Corbet 
On Wed, 21 Feb 2018 14:29:06 -0800
Kees Cook  wrote:

> >> I wonder if this might be more readable by splitting the kernel-doc
> >> changes from the bitmap changes? I.e. fix all the kernel-doc in one
> >> patch, and in the following, make the bitmap changes. Maybe it's such
> >> a small part that it doesn't matter, though?  
> >
> > I had the same thought, but then I would have made most of the kerneldoc
> > changes to something that would be altered by the following patch,
> > because it would have made little sense to fix only those parts that
> > would have survived.
> >
> > If it is really a problem to keep them together, I could put these
> > changes in a following patch. Would that be ok?  
> 
> Hmmm... I think keeping it as-is would be better than a trailing
> docs-only patch. Maybe Jon has an opinion?

I would be inclined to agree.  Putting docs changes with the associated
code changes helps to document the patch itself, among other things.  I
wouldn't split them up.

jon

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-21 Thread Kees Cook 
On Tue, Feb 20, 2018 at 9:07 AM, Igor Stoppa  wrote:
> On 13/02/18 01:52, Kees Cook wrote:
>> On Mon, Feb 12, 2018 at 8:52 AM, Igor Stoppa  wrote:
>>> @@ -738,14 +1031,16 @@ EXPORT_SYMBOL(devm_gen_pool_create);
>>>
>>>  #ifdef CONFIG_OF
>>>  /**
>>> - * of_gen_pool_get - find a pool by phandle property
>>> + * of_gen_pool_get() - find a pool by phandle property
>>>   * @np: device node
>>>   * @propname: property name containing phandle(s)
>>>   * @index: index into the phandle array
>>>   *
>>> - * Returns the pool that contains the chunk starting at the physical
>>> - * address of the device tree node pointed at by the phandle property,
>>> - * or NULL if not found.
>>> + * Return:
>>> + * * pool address  - it contains the chunk starting at the physical
>>> + *   address of the device tree node pointed at by
>>> + *   the phandle property
>>> + * * NULL  - otherwise
>>>   */
>>>  struct gen_pool *of_gen_pool_get(struct device_node *np,
>>> const char *propname, int index)
>>
>> I wonder if this might be more readable by splitting the kernel-doc
>> changes from the bitmap changes? I.e. fix all the kernel-doc in one
>> patch, and in the following, make the bitmap changes. Maybe it's such
>> a small part that it doesn't matter, though?
>
> I had the same thought, but then I would have made most of the kerneldoc
> changes to something that would be altered by the following patch,
> because it would have made little sense to fix only those parts that
> would have survived.
>
> If it is really a problem to keep them together, I could put these
> changes in a following patch. Would that be ok?

Hmmm... I think keeping it as-is would be better than a trailing
docs-only patch. Maybe Jon has an opinion?

-Kees

-- 
Kees Cook
Pixel Security

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-21 Thread Kees Cook 
On Tue, Feb 20, 2018 at 9:07 AM, Igor Stoppa  wrote:
> On 13/02/18 01:52, Kees Cook wrote:
>> On Mon, Feb 12, 2018 at 8:52 AM, Igor Stoppa  wrote:
>>> @@ -738,14 +1031,16 @@ EXPORT_SYMBOL(devm_gen_pool_create);
>>>
>>>  #ifdef CONFIG_OF
>>>  /**
>>> - * of_gen_pool_get - find a pool by phandle property
>>> + * of_gen_pool_get() - find a pool by phandle property
>>>   * @np: device node
>>>   * @propname: property name containing phandle(s)
>>>   * @index: index into the phandle array
>>>   *
>>> - * Returns the pool that contains the chunk starting at the physical
>>> - * address of the device tree node pointed at by the phandle property,
>>> - * or NULL if not found.
>>> + * Return:
>>> + * * pool address  - it contains the chunk starting at the physical
>>> + *   address of the device tree node pointed at by
>>> + *   the phandle property
>>> + * * NULL  - otherwise
>>>   */
>>>  struct gen_pool *of_gen_pool_get(struct device_node *np,
>>> const char *propname, int index)
>>
>> I wonder if this might be more readable by splitting the kernel-doc
>> changes from the bitmap changes? I.e. fix all the kernel-doc in one
>> patch, and in the following, make the bitmap changes. Maybe it's such
>> a small part that it doesn't matter, though?
>
> I had the same thought, but then I would have made most of the kerneldoc
> changes to something that would be altered by the following patch,
> because it would have made little sense to fix only those parts that
> would have survived.
>
> If it is really a problem to keep them together, I could put these
> changes in a following patch. Would that be ok?

Hmmm... I think keeping it as-is would be better than a trailing
docs-only patch. Maybe Jon has an opinion?

-Kees

-- 
Kees Cook
Pixel Security

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-20 Thread Igor Stoppa 
On 13/02/18 01:52, Kees Cook wrote:
> On Mon, Feb 12, 2018 at 8:52 AM, Igor Stoppa  wrote:
>> @@ -738,14 +1031,16 @@ EXPORT_SYMBOL(devm_gen_pool_create);
>>
>>  #ifdef CONFIG_OF
>>  /**
>> - * of_gen_pool_get - find a pool by phandle property
>> + * of_gen_pool_get() - find a pool by phandle property
>>   * @np: device node
>>   * @propname: property name containing phandle(s)
>>   * @index: index into the phandle array
>>   *
>> - * Returns the pool that contains the chunk starting at the physical
>> - * address of the device tree node pointed at by the phandle property,
>> - * or NULL if not found.
>> + * Return:
>> + * * pool address  - it contains the chunk starting at the physical
>> + *   address of the device tree node pointed at by
>> + *   the phandle property
>> + * * NULL  - otherwise
>>   */
>>  struct gen_pool *of_gen_pool_get(struct device_node *np,
>> const char *propname, int index)
> 
> I wonder if this might be more readable by splitting the kernel-doc
> changes from the bitmap changes? I.e. fix all the kernel-doc in one
> patch, and in the following, make the bitmap changes. Maybe it's such
> a small part that it doesn't matter, though?

I had the same thought, but then I would have made most of the kerneldoc
changes to something that would be altered by the following patch,
because it would have made little sense to fix only those parts that
would have survived.

If it is really a problem to keep them together, I could put these
changes in a following patch. Would that be ok?

--
igor

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-20 Thread Igor Stoppa 
On 13/02/18 01:52, Kees Cook wrote:
> On Mon, Feb 12, 2018 at 8:52 AM, Igor Stoppa  wrote:
>> @@ -738,14 +1031,16 @@ EXPORT_SYMBOL(devm_gen_pool_create);
>>
>>  #ifdef CONFIG_OF
>>  /**
>> - * of_gen_pool_get - find a pool by phandle property
>> + * of_gen_pool_get() - find a pool by phandle property
>>   * @np: device node
>>   * @propname: property name containing phandle(s)
>>   * @index: index into the phandle array
>>   *
>> - * Returns the pool that contains the chunk starting at the physical
>> - * address of the device tree node pointed at by the phandle property,
>> - * or NULL if not found.
>> + * Return:
>> + * * pool address  - it contains the chunk starting at the physical
>> + *   address of the device tree node pointed at by
>> + *   the phandle property
>> + * * NULL  - otherwise
>>   */
>>  struct gen_pool *of_gen_pool_get(struct device_node *np,
>> const char *propname, int index)
> 
> I wonder if this might be more readable by splitting the kernel-doc
> changes from the bitmap changes? I.e. fix all the kernel-doc in one
> patch, and in the following, make the bitmap changes. Maybe it's such
> a small part that it doesn't matter, though?

I had the same thought, but then I would have made most of the kerneldoc
changes to something that would be altered by the following patch,
because it would have made little sense to fix only those parts that
would have survived.

If it is really a problem to keep them together, I could put these
changes in a following patch. Would that be ok?

--
igor

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-12 Thread kbuild test robot 
Hi Igor,

Thank you for the patch! Yet something to improve:

[auto build test ERROR on linus/master]
[also build test ERROR on v4.16-rc1 next-20180212]
[if your patch is applied to the wrong git tree, please drop us a note to help 
improve the system]

url:
https://github.com/0day-ci/linux/commits/Igor-Stoppa/genalloc-track-beginning-of-allocations/20180212-192839
config: openrisc-allmodconfig (attached as .config)
compiler: or1k-linux-gcc (GCC) 6.0.0 20160327 (experimental)
reproduce:
wget 
https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O 
~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=openrisc 

All errors (new ones prefixed by >>):

   WARNING: modpost: missing MODULE_LICENSE() in 
drivers/media/platform/mtk-vcodec/mtk-vcodec-common.o
   see include/linux/module.h for more information
   WARNING: modpost: missing MODULE_LICENSE() in 
drivers/media/platform/tegra-cec/tegra_cec.o
   see include/linux/module.h for more information
>> ERROR: "gen_pool_best_fit" [drivers/tee/tee.ko] undefined!

---
0-DAY kernel test infrastructureOpen Source Technology Center
https://lists.01.org/pipermail/kbuild-all   Intel Corporation


.config.gz
Description: application/gzip

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-12 Thread kbuild test robot 
Hi Igor,

Thank you for the patch! Yet something to improve:

[auto build test ERROR on linus/master]
[also build test ERROR on v4.16-rc1 next-20180212]
[if your patch is applied to the wrong git tree, please drop us a note to help 
improve the system]

url:
https://github.com/0day-ci/linux/commits/Igor-Stoppa/genalloc-track-beginning-of-allocations/20180212-192839
config: openrisc-allmodconfig (attached as .config)
compiler: or1k-linux-gcc (GCC) 6.0.0 20160327 (experimental)
reproduce:
wget 
https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O 
~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=openrisc 

All errors (new ones prefixed by >>):

   WARNING: modpost: missing MODULE_LICENSE() in 
drivers/media/platform/mtk-vcodec/mtk-vcodec-common.o
   see include/linux/module.h for more information
   WARNING: modpost: missing MODULE_LICENSE() in 
drivers/media/platform/tegra-cec/tegra_cec.o
   see include/linux/module.h for more information
>> ERROR: "gen_pool_best_fit" [drivers/tee/tee.ko] undefined!

---
0-DAY kernel test infrastructureOpen Source Technology Center
https://lists.01.org/pipermail/kbuild-all   Intel Corporation


.config.gz
Description: application/gzip

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-12 Thread Kees Cook 
On Mon, Feb 12, 2018 at 8:52 AM, Igor Stoppa  wrote:
> @@ -738,14 +1031,16 @@ EXPORT_SYMBOL(devm_gen_pool_create);
>
>  #ifdef CONFIG_OF
>  /**
> - * of_gen_pool_get - find a pool by phandle property
> + * of_gen_pool_get() - find a pool by phandle property
>   * @np: device node
>   * @propname: property name containing phandle(s)
>   * @index: index into the phandle array
>   *
> - * Returns the pool that contains the chunk starting at the physical
> - * address of the device tree node pointed at by the phandle property,
> - * or NULL if not found.
> + * Return:
> + * * pool address  - it contains the chunk starting at the physical
> + *   address of the device tree node pointed at by
> + *   the phandle property
> + * * NULL  - otherwise
>   */
>  struct gen_pool *of_gen_pool_get(struct device_node *np,
> const char *propname, int index)

I wonder if this might be more readable by splitting the kernel-doc
changes from the bitmap changes? I.e. fix all the kernel-doc in one
patch, and in the following, make the bitmap changes. Maybe it's such
a small part that it doesn't matter, though?

-Kees

-- 
Kees Cook
Pixel Security

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-12 Thread Kees Cook 
On Mon, Feb 12, 2018 at 8:52 AM, Igor Stoppa  wrote:
> @@ -738,14 +1031,16 @@ EXPORT_SYMBOL(devm_gen_pool_create);
>
>  #ifdef CONFIG_OF
>  /**
> - * of_gen_pool_get - find a pool by phandle property
> + * of_gen_pool_get() - find a pool by phandle property
>   * @np: device node
>   * @propname: property name containing phandle(s)
>   * @index: index into the phandle array
>   *
> - * Returns the pool that contains the chunk starting at the physical
> - * address of the device tree node pointed at by the phandle property,
> - * or NULL if not found.
> + * Return:
> + * * pool address  - it contains the chunk starting at the physical
> + *   address of the device tree node pointed at by
> + *   the phandle property
> + * * NULL  - otherwise
>   */
>  struct gen_pool *of_gen_pool_get(struct device_node *np,
> const char *propname, int index)

I wonder if this might be more readable by splitting the kernel-doc
changes from the bitmap changes? I.e. fix all the kernel-doc in one
patch, and in the following, make the bitmap changes. Maybe it's such
a small part that it doesn't matter, though?

-Kees

-- 
Kees Cook
Pixel Security

[PATCH 1/6] genalloc: track beginning of allocations

2018-02-12 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Examples:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

This patch doubles the space reserved in the bitmap for each allocation,
to track their beginning.

For details, see the documentation inside lib/genalloc.c

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   4 +-
 lib/genalloc.c   | 631 ++-
 2 files changed, 465 insertions(+), 170 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 872f930f1b06..dcaa33e74b1c 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -32,7 +32,7 @@
 
 #include 
 #include 
-#include 
+#include 
 
 struct device;
 struct device_node;
@@ -76,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index ca06adc4f445..87f62f31b52f 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -26,6 +26,74 @@
  *
  * This source code is licensed under the GNU General Public License,
  * Version 2.  See the file COPYING for more details.
+ *
+ *
+ *
+ * Encoding of the bitmap tracking the allocations
+ * ---
+ *
+ * The bitmap is composed of units of allocations.
+ *
+ * Each unit of allocation is represented using 2 consecutive bits.
+ *
+ * This makes it possible to encode, for each unit of allocation,
+ * information about:
+ *  - allocation status (busy/free)
+ *  - beginning of a sequennce of allocation units (first / successive)
+ *
+ *
+ * Dictionary of allocation units (msb to the left, lsb to the right):
+ *
+ * 11: first allocation unit in the allocation
+ * 10: any subsequent allocation unit (if any) in the allocation
+ * 00: available allocation unit
+ * 01: invalid
+ *
+ * Example, using the same notation as above - MSb...LSb:
+ *
+ *  ...100010101011   <-- Read in this direction.
+ * \__|\__|\|\|\__|
+ *|   | | |   \___ 4 used allocation units
+ *|   | | \___ 3 empty allocation units
+ *|   | \_ 1 used allocation unit
+ *|   \___ 2 used allocation units
+ *\___ 2 empty allocation units
+ *
+ * The encoding allows for lockless operations, such as:
+ * - search for a sufficiently large range of allocation units
+ * - reservation of a selected range of allocation units
+ * - release of a specific allocation
+ *
+ * The alignment at which to perform the research for sequence of empty
+ * allocation units (marked as zeros in the bitmap) is 2^1.
+ *
+ * This means that an allocation can start only at even places
+ * (bit 0, bit 2, etc.) in the bitmap.
+ *
+ * Therefore, the number of zeroes to look for must be twice the number
+ * of desired allocation units.
+ *
+ * When it's time to free the memory associated to an allocation request,
+ * it's a matter of checking if the corresponding allocation unit is
+ * really the beginning of an allocation (both bits are set to 1).
+ *
+ * Looking for the ending can also be performed locklessly.
+ * It's sufficient to identify the first mapped allocation unit
+ * that is represented either as free (00) or busy (11).
+ * Even if the allocation status should change in the meanwhile, it
+ * doesn't matter, since it can only transition between free (00) and
+ * first-allocated (11).
+ *
+ * The parameter indicating to the *_free() function the size of the
+ * space that should be freed can be either set to 0, for automated
+ * assessment, or it can be specified explicitly.
+ *
+ * In case it is specified explicitly, the value is verified agaisnt what
+ * the library is tracking internally.
+

[PATCH 1/6] genalloc: track beginning of allocations

2018-02-12 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Examples:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

This patch doubles the space reserved in the bitmap for each allocation,
to track their beginning.

For details, see the documentation inside lib/genalloc.c

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   4 +-
 lib/genalloc.c   | 631 ++-
 2 files changed, 465 insertions(+), 170 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 872f930f1b06..dcaa33e74b1c 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -32,7 +32,7 @@
 
 #include 
 #include 
-#include 
+#include 
 
 struct device;
 struct device_node;
@@ -76,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index ca06adc4f445..87f62f31b52f 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -26,6 +26,74 @@
  *
  * This source code is licensed under the GNU General Public License,
  * Version 2.  See the file COPYING for more details.
+ *
+ *
+ *
+ * Encoding of the bitmap tracking the allocations
+ * ---
+ *
+ * The bitmap is composed of units of allocations.
+ *
+ * Each unit of allocation is represented using 2 consecutive bits.
+ *
+ * This makes it possible to encode, for each unit of allocation,
+ * information about:
+ *  - allocation status (busy/free)
+ *  - beginning of a sequennce of allocation units (first / successive)
+ *
+ *
+ * Dictionary of allocation units (msb to the left, lsb to the right):
+ *
+ * 11: first allocation unit in the allocation
+ * 10: any subsequent allocation unit (if any) in the allocation
+ * 00: available allocation unit
+ * 01: invalid
+ *
+ * Example, using the same notation as above - MSb...LSb:
+ *
+ *  ...100010101011   <-- Read in this direction.
+ * \__|\__|\|\|\__|
+ *|   | | |   \___ 4 used allocation units
+ *|   | | \___ 3 empty allocation units
+ *|   | \_ 1 used allocation unit
+ *|   \___ 2 used allocation units
+ *\___ 2 empty allocation units
+ *
+ * The encoding allows for lockless operations, such as:
+ * - search for a sufficiently large range of allocation units
+ * - reservation of a selected range of allocation units
+ * - release of a specific allocation
+ *
+ * The alignment at which to perform the research for sequence of empty
+ * allocation units (marked as zeros in the bitmap) is 2^1.
+ *
+ * This means that an allocation can start only at even places
+ * (bit 0, bit 2, etc.) in the bitmap.
+ *
+ * Therefore, the number of zeroes to look for must be twice the number
+ * of desired allocation units.
+ *
+ * When it's time to free the memory associated to an allocation request,
+ * it's a matter of checking if the corresponding allocation unit is
+ * really the beginning of an allocation (both bits are set to 1).
+ *
+ * Looking for the ending can also be performed locklessly.
+ * It's sufficient to identify the first mapped allocation unit
+ * that is represented either as free (00) or busy (11).
+ * Even if the allocation status should change in the meanwhile, it
+ * doesn't matter, since it can only transition between free (00) and
+ * first-allocated (11).
+ *
+ * The parameter indicating to the *_free() function the size of the
+ * space that should be freed can be either set to 0, for automated
+ * assessment, or it can be specified explicitly.
+ *
+ * In case it is specified explicitly, the value is verified agaisnt what
+ * the library is tracking internally.
+ *
+ * If ever needed,

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-12 Thread Mike Rapoport 
On Mon, Feb 12, 2018 at 01:17:01PM +0200, Igor Stoppa wrote:
> 
> 
> On 11/02/18 14:24, Mike Rapoport wrote:
> > On Sun, Feb 11, 2018 at 05:19:15AM +0200, Igor Stoppa wrote:
> [...]
> 
> >> +/**
> >> + * mem_to_units - convert references to memory into orders of allocation
> > 
> > Documentation/doc-guide/kernel-doc.rst recommends to to include brackets
> > for function comments. I haven't noticed any difference in the resulting
> > html, so I'm not sure if the brackets are actually required.
> 
> This is what I see in the example from mailine docs:
> 
> /**
>  * foobar() - Brief description of foobar.
>  * @argument1: Description of parameter argument1 of foobar.
>  * @argument2: Description of parameter argument2 of foobar.
>  *
>  * Longer description of foobar.
>  *
>  * Return: Description of return value of foobar.
>  */
> int foobar(int argument1, char *argument2)
> 
> 
> What are you referring to?
 
I'm referring to "foobar() - brief description" vs "foobar - brief
description".

The generated html looks exactly the same in the browser, so I don't know
if the brackets are really required.

> [...]
> 
> >> + * @size: amount in bytes
> >> + * @order: power of 2 represented by each entry in the bitmap
> >> + *
> >> + * Returns the number of units representing the size.
> > 
> > Please s/Return/Return:/
> 
> :-( I thought I had fixed them all. thanks for spotting this.
> 
> [...]
> 
> >> + * Return: If two users alter the same bit, to one it will return
> >> + * remaining entries, to the other it will return 0.
> > 
> > And what if there are three or four concurrent users? ;-)
> > 
> > I believe that a more elaborate description about what happens with
> > concurrent attempts to alter the bitmap would be really helpful.
> 
> ok
> 
> --
> thanks, igor
> 

-- 
Sincerely yours,
Mike.

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-12 Thread Mike Rapoport 
On Mon, Feb 12, 2018 at 01:17:01PM +0200, Igor Stoppa wrote:
> 
> 
> On 11/02/18 14:24, Mike Rapoport wrote:
> > On Sun, Feb 11, 2018 at 05:19:15AM +0200, Igor Stoppa wrote:
> [...]
> 
> >> +/**
> >> + * mem_to_units - convert references to memory into orders of allocation
> > 
> > Documentation/doc-guide/kernel-doc.rst recommends to to include brackets
> > for function comments. I haven't noticed any difference in the resulting
> > html, so I'm not sure if the brackets are actually required.
> 
> This is what I see in the example from mailine docs:
> 
> /**
>  * foobar() - Brief description of foobar.
>  * @argument1: Description of parameter argument1 of foobar.
>  * @argument2: Description of parameter argument2 of foobar.
>  *
>  * Longer description of foobar.
>  *
>  * Return: Description of return value of foobar.
>  */
> int foobar(int argument1, char *argument2)
> 
> 
> What are you referring to?
 
I'm referring to "foobar() - brief description" vs "foobar - brief
description".

The generated html looks exactly the same in the browser, so I don't know
if the brackets are really required.

> [...]
> 
> >> + * @size: amount in bytes
> >> + * @order: power of 2 represented by each entry in the bitmap
> >> + *
> >> + * Returns the number of units representing the size.
> > 
> > Please s/Return/Return:/
> 
> :-( I thought I had fixed them all. thanks for spotting this.
> 
> [...]
> 
> >> + * Return: If two users alter the same bit, to one it will return
> >> + * remaining entries, to the other it will return 0.
> > 
> > And what if there are three or four concurrent users? ;-)
> > 
> > I believe that a more elaborate description about what happens with
> > concurrent attempts to alter the bitmap would be really helpful.
> 
> ok
> 
> --
> thanks, igor
> 

-- 
Sincerely yours,
Mike.

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-12 Thread Igor Stoppa 


On 11/02/18 14:24, Mike Rapoport wrote:
> On Sun, Feb 11, 2018 at 05:19:15AM +0200, Igor Stoppa wrote:
[...]

>> +/**
>> + * mem_to_units - convert references to memory into orders of allocation
> 
> Documentation/doc-guide/kernel-doc.rst recommends to to include brackets
> for function comments. I haven't noticed any difference in the resulting
> html, so I'm not sure if the brackets are actually required.

This is what I see in the example from mailine docs:

/**
 * foobar() - Brief description of foobar.
 * @argument1: Description of parameter argument1 of foobar.
 * @argument2: Description of parameter argument2 of foobar.
 *
 * Longer description of foobar.
 *
 * Return: Description of return value of foobar.
 */
int foobar(int argument1, char *argument2)


What are you referring to?

[...]

>> + * @size: amount in bytes
>> + * @order: power of 2 represented by each entry in the bitmap
>> + *
>> + * Returns the number of units representing the size.
> 
> Please s/Return/Return:/

:-( I thought I had fixed them all. thanks for spotting this.

[...]

>> + * Return: If two users alter the same bit, to one it will return
>> + * remaining entries, to the other it will return 0.
> 
> And what if there are three or four concurrent users? ;-)
> 
> I believe that a more elaborate description about what happens with
> concurrent attempts to alter the bitmap would be really helpful.

ok

--
thanks, igor

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-12 Thread Igor Stoppa 


On 11/02/18 14:24, Mike Rapoport wrote:
> On Sun, Feb 11, 2018 at 05:19:15AM +0200, Igor Stoppa wrote:
[...]

>> +/**
>> + * mem_to_units - convert references to memory into orders of allocation
> 
> Documentation/doc-guide/kernel-doc.rst recommends to to include brackets
> for function comments. I haven't noticed any difference in the resulting
> html, so I'm not sure if the brackets are actually required.

This is what I see in the example from mailine docs:

/**
 * foobar() - Brief description of foobar.
 * @argument1: Description of parameter argument1 of foobar.
 * @argument2: Description of parameter argument2 of foobar.
 *
 * Longer description of foobar.
 *
 * Return: Description of return value of foobar.
 */
int foobar(int argument1, char *argument2)


What are you referring to?

[...]

>> + * @size: amount in bytes
>> + * @order: power of 2 represented by each entry in the bitmap
>> + *
>> + * Returns the number of units representing the size.
> 
> Please s/Return/Return:/

:-( I thought I had fixed them all. thanks for spotting this.

[...]

>> + * Return: If two users alter the same bit, to one it will return
>> + * remaining entries, to the other it will return 0.
> 
> And what if there are three or four concurrent users? ;-)
> 
> I believe that a more elaborate description about what happens with
> concurrent attempts to alter the bitmap would be really helpful.

ok

--
thanks, igor

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-11 Thread Mike Rapoport 
On Sun, Feb 11, 2018 at 05:19:15AM +0200, Igor Stoppa wrote:
> The genalloc library is only capable of tracking if a certain unit of
> allocation is in use or not.
> 
> It is not capable of discerning where the memory associated to an
> allocation request begins and where it ends.
> 
> The reason is that units of allocations are tracked by using a bitmap,
> where each bit represents that the unit is either allocated (1) or
> available (0).
> 
> The user of the API must keep track of how much space was requested, if
> it ever needs to be freed.
> 
> This can cause errors being undetected.
> Examples:
> * Only a subset of the memory provided to an allocation request is freed
> * The memory from a subsequent allocation is freed
> * The memory being freed doesn't start at the beginning of an
>   allocation.
> 
> The bitmap is used because it allows to perform lockless read/write
> access, where this is supported by hw through cmpxchg.
> Similarly, it is possible to scan the bitmap for a sufficiently long
> sequence of zeros, to identify zones available for allocation.
> 
> This patch doubles the space reserved in the bitmap for each allocation,
> to track their beginning.
> 
> For details, see the documentation inside lib/genalloc.c
> 
> Signed-off-by: Igor Stoppa 
> ---
>  include/linux/genalloc.h |   4 +-
>  lib/genalloc.c   | 527 
> ++-
>  2 files changed, 390 insertions(+), 141 deletions(-)
> 
> diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
> index 872f930f1b06..dcaa33e74b1c 100644
> --- a/include/linux/genalloc.h
> +++ b/include/linux/genalloc.h
> @@ -32,7 +32,7 @@
> 
>  #include 
>  #include 
> -#include 
> +#include 
> 
>  struct device;
>  struct device_node;
> @@ -76,7 +76,7 @@ struct gen_pool_chunk {
>   phys_addr_t phys_addr;  /* physical starting address of memory 
> chunk */
>   unsigned long start_addr;   /* start address of memory chunk */
>   unsigned long end_addr; /* end address of memory chunk 
> (inclusive) */
> - unsigned long bits[0];  /* bitmap for allocating memory chunk */
> + unsigned long entries[0];   /* bitmap for allocating memory chunk */
>  };
> 
>  /*
> diff --git a/lib/genalloc.c b/lib/genalloc.c
> index ca06adc4f445..044347163acb 100644
> --- a/lib/genalloc.c
> +++ b/lib/genalloc.c
> @@ -26,6 +26,74 @@
>   *
>   * This source code is licensed under the GNU General Public License,
>   * Version 2.  See the file COPYING for more details.
> + *
> + *
> + *
> + * Encoding of the bitmap tracking the allocations
> + * ---
> + *
> + * The bitmap is composed of units of allocations.
> + *
> + * Each unit of allocation is represented using 2 consecutive bits.
> + *
> + * This makes it possible to encode, for each unit of allocation,
> + * information about:
> + *  - allocation status (busy/free)
> + *  - beginning of a sequennce of allocation units (first / successive)
> + *
> + *
> + * Dictionary of allocation units (msb to the left, lsb to the right):
> + *
> + * 11: first allocation unit in the allocation
> + * 10: any subsequent allocation unit (if any) in the allocation
> + * 00: available allocation unit
> + * 01: invalid
> + *
> + * Example, using the same notation as above - MSb...LSb:
> + *
> + *  ...100010101011   <-- Read in this direction.
> + * \__|\__|\|\|\__|
> + *|   | | |   \___ 4 used allocation units
> + *|   | | \___ 3 empty allocation units
> + *|   | \_ 1 used allocation unit
> + *|   \___ 2 used allocation units
> + *\___ 2 empty allocation units
> + *
> + * The encoding allows for lockless operations, such as:
> + * - search for a sufficiently large range of allocation units
> + * - reservation of a selected range of allocation units
> + * - release of a specific allocation
> + *
> + * The alignment at which to perform the research for sequence of empty
> + * allocation units (marked as zeros in the bitmap) is 2^1.
> + *
> + * This means that an allocation can start only at even places
> + * (bit 0, bit 2, etc.) in the bitmap.
> + *
> + * Therefore, the number of zeroes to look for must be twice the number
> + * of desired allocation units.
> + *
> + * When it's time to free the memory associated to an allocation request,
> + * it's a matter of checking if the corresponding allocation unit is
> + * really the beginning of an allocation (both bits are set to 1).
> + *
> + * Looking for the ending can also be performed locklessly.
> + * It's sufficient to identify the first mapped allocation unit
> + * that is represented either as free (00) or busy (11).
> + * Even if the allocation status should change in the meanwhile, it
> + * doesn't matter, since it can only transition between free (00) and
> + * first-allocated (11).
> + *
> + *

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-11 Thread Mike Rapoport 
On Sun, Feb 11, 2018 at 05:19:15AM +0200, Igor Stoppa wrote:
> The genalloc library is only capable of tracking if a certain unit of
> allocation is in use or not.
> 
> It is not capable of discerning where the memory associated to an
> allocation request begins and where it ends.
> 
> The reason is that units of allocations are tracked by using a bitmap,
> where each bit represents that the unit is either allocated (1) or
> available (0).
> 
> The user of the API must keep track of how much space was requested, if
> it ever needs to be freed.
> 
> This can cause errors being undetected.
> Examples:
> * Only a subset of the memory provided to an allocation request is freed
> * The memory from a subsequent allocation is freed
> * The memory being freed doesn't start at the beginning of an
>   allocation.
> 
> The bitmap is used because it allows to perform lockless read/write
> access, where this is supported by hw through cmpxchg.
> Similarly, it is possible to scan the bitmap for a sufficiently long
> sequence of zeros, to identify zones available for allocation.
> 
> This patch doubles the space reserved in the bitmap for each allocation,
> to track their beginning.
> 
> For details, see the documentation inside lib/genalloc.c
> 
> Signed-off-by: Igor Stoppa 
> ---
>  include/linux/genalloc.h |   4 +-
>  lib/genalloc.c   | 527 
> ++-
>  2 files changed, 390 insertions(+), 141 deletions(-)
> 
> diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
> index 872f930f1b06..dcaa33e74b1c 100644
> --- a/include/linux/genalloc.h
> +++ b/include/linux/genalloc.h
> @@ -32,7 +32,7 @@
> 
>  #include 
>  #include 
> -#include 
> +#include 
> 
>  struct device;
>  struct device_node;
> @@ -76,7 +76,7 @@ struct gen_pool_chunk {
>   phys_addr_t phys_addr;  /* physical starting address of memory 
> chunk */
>   unsigned long start_addr;   /* start address of memory chunk */
>   unsigned long end_addr; /* end address of memory chunk 
> (inclusive) */
> - unsigned long bits[0];  /* bitmap for allocating memory chunk */
> + unsigned long entries[0];   /* bitmap for allocating memory chunk */
>  };
> 
>  /*
> diff --git a/lib/genalloc.c b/lib/genalloc.c
> index ca06adc4f445..044347163acb 100644
> --- a/lib/genalloc.c
> +++ b/lib/genalloc.c
> @@ -26,6 +26,74 @@
>   *
>   * This source code is licensed under the GNU General Public License,
>   * Version 2.  See the file COPYING for more details.
> + *
> + *
> + *
> + * Encoding of the bitmap tracking the allocations
> + * ---
> + *
> + * The bitmap is composed of units of allocations.
> + *
> + * Each unit of allocation is represented using 2 consecutive bits.
> + *
> + * This makes it possible to encode, for each unit of allocation,
> + * information about:
> + *  - allocation status (busy/free)
> + *  - beginning of a sequennce of allocation units (first / successive)
> + *
> + *
> + * Dictionary of allocation units (msb to the left, lsb to the right):
> + *
> + * 11: first allocation unit in the allocation
> + * 10: any subsequent allocation unit (if any) in the allocation
> + * 00: available allocation unit
> + * 01: invalid
> + *
> + * Example, using the same notation as above - MSb...LSb:
> + *
> + *  ...100010101011   <-- Read in this direction.
> + * \__|\__|\|\|\__|
> + *|   | | |   \___ 4 used allocation units
> + *|   | | \___ 3 empty allocation units
> + *|   | \_ 1 used allocation unit
> + *|   \___ 2 used allocation units
> + *\___ 2 empty allocation units
> + *
> + * The encoding allows for lockless operations, such as:
> + * - search for a sufficiently large range of allocation units
> + * - reservation of a selected range of allocation units
> + * - release of a specific allocation
> + *
> + * The alignment at which to perform the research for sequence of empty
> + * allocation units (marked as zeros in the bitmap) is 2^1.
> + *
> + * This means that an allocation can start only at even places
> + * (bit 0, bit 2, etc.) in the bitmap.
> + *
> + * Therefore, the number of zeroes to look for must be twice the number
> + * of desired allocation units.
> + *
> + * When it's time to free the memory associated to an allocation request,
> + * it's a matter of checking if the corresponding allocation unit is
> + * really the beginning of an allocation (both bits are set to 1).
> + *
> + * Looking for the ending can also be performed locklessly.
> + * It's sufficient to identify the first mapped allocation unit
> + * that is represented either as free (00) or busy (11).
> + * Even if the allocation status should change in the meanwhile, it
> + * doesn't matter, since it can only transition between free (00) and
> + * first-allocated (11).
> + *
> + * The parameter indicating

[PATCH 1/6] genalloc: track beginning of allocations

2018-02-10 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Examples:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

This patch doubles the space reserved in the bitmap for each allocation,
to track their beginning.

For details, see the documentation inside lib/genalloc.c

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   4 +-
 lib/genalloc.c   | 527 ++-
 2 files changed, 390 insertions(+), 141 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 872f930f1b06..dcaa33e74b1c 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -32,7 +32,7 @@
 
 #include 
 #include 
-#include 
+#include 
 
 struct device;
 struct device_node;
@@ -76,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index ca06adc4f445..044347163acb 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -26,6 +26,74 @@
  *
  * This source code is licensed under the GNU General Public License,
  * Version 2.  See the file COPYING for more details.
+ *
+ *
+ *
+ * Encoding of the bitmap tracking the allocations
+ * ---
+ *
+ * The bitmap is composed of units of allocations.
+ *
+ * Each unit of allocation is represented using 2 consecutive bits.
+ *
+ * This makes it possible to encode, for each unit of allocation,
+ * information about:
+ *  - allocation status (busy/free)
+ *  - beginning of a sequennce of allocation units (first / successive)
+ *
+ *
+ * Dictionary of allocation units (msb to the left, lsb to the right):
+ *
+ * 11: first allocation unit in the allocation
+ * 10: any subsequent allocation unit (if any) in the allocation
+ * 00: available allocation unit
+ * 01: invalid
+ *
+ * Example, using the same notation as above - MSb...LSb:
+ *
+ *  ...100010101011   <-- Read in this direction.
+ * \__|\__|\|\|\__|
+ *|   | | |   \___ 4 used allocation units
+ *|   | | \___ 3 empty allocation units
+ *|   | \_ 1 used allocation unit
+ *|   \___ 2 used allocation units
+ *\___ 2 empty allocation units
+ *
+ * The encoding allows for lockless operations, such as:
+ * - search for a sufficiently large range of allocation units
+ * - reservation of a selected range of allocation units
+ * - release of a specific allocation
+ *
+ * The alignment at which to perform the research for sequence of empty
+ * allocation units (marked as zeros in the bitmap) is 2^1.
+ *
+ * This means that an allocation can start only at even places
+ * (bit 0, bit 2, etc.) in the bitmap.
+ *
+ * Therefore, the number of zeroes to look for must be twice the number
+ * of desired allocation units.
+ *
+ * When it's time to free the memory associated to an allocation request,
+ * it's a matter of checking if the corresponding allocation unit is
+ * really the beginning of an allocation (both bits are set to 1).
+ *
+ * Looking for the ending can also be performed locklessly.
+ * It's sufficient to identify the first mapped allocation unit
+ * that is represented either as free (00) or busy (11).
+ * Even if the allocation status should change in the meanwhile, it
+ * doesn't matter, since it can only transition between free (00) and
+ * first-allocated (11).
+ *
+ * The parameter indicating to the *_free() function the size of the
+ * space that should be freed can be either set to 0, for automated
+ * assessment, or it can be specified explicitly.
+ *
+ * In case it is specified explicitly, the value is verified agaisnt what
+ * the library is tracking internally.
+

[PATCH 1/6] genalloc: track beginning of allocations

2018-02-10 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Examples:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

This patch doubles the space reserved in the bitmap for each allocation,
to track their beginning.

For details, see the documentation inside lib/genalloc.c

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   4 +-
 lib/genalloc.c   | 527 ++-
 2 files changed, 390 insertions(+), 141 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 872f930f1b06..dcaa33e74b1c 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -32,7 +32,7 @@
 
 #include 
 #include 
-#include 
+#include 
 
 struct device;
 struct device_node;
@@ -76,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index ca06adc4f445..044347163acb 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -26,6 +26,74 @@
  *
  * This source code is licensed under the GNU General Public License,
  * Version 2.  See the file COPYING for more details.
+ *
+ *
+ *
+ * Encoding of the bitmap tracking the allocations
+ * ---
+ *
+ * The bitmap is composed of units of allocations.
+ *
+ * Each unit of allocation is represented using 2 consecutive bits.
+ *
+ * This makes it possible to encode, for each unit of allocation,
+ * information about:
+ *  - allocation status (busy/free)
+ *  - beginning of a sequennce of allocation units (first / successive)
+ *
+ *
+ * Dictionary of allocation units (msb to the left, lsb to the right):
+ *
+ * 11: first allocation unit in the allocation
+ * 10: any subsequent allocation unit (if any) in the allocation
+ * 00: available allocation unit
+ * 01: invalid
+ *
+ * Example, using the same notation as above - MSb...LSb:
+ *
+ *  ...100010101011   <-- Read in this direction.
+ * \__|\__|\|\|\__|
+ *|   | | |   \___ 4 used allocation units
+ *|   | | \___ 3 empty allocation units
+ *|   | \_ 1 used allocation unit
+ *|   \___ 2 used allocation units
+ *\___ 2 empty allocation units
+ *
+ * The encoding allows for lockless operations, such as:
+ * - search for a sufficiently large range of allocation units
+ * - reservation of a selected range of allocation units
+ * - release of a specific allocation
+ *
+ * The alignment at which to perform the research for sequence of empty
+ * allocation units (marked as zeros in the bitmap) is 2^1.
+ *
+ * This means that an allocation can start only at even places
+ * (bit 0, bit 2, etc.) in the bitmap.
+ *
+ * Therefore, the number of zeroes to look for must be twice the number
+ * of desired allocation units.
+ *
+ * When it's time to free the memory associated to an allocation request,
+ * it's a matter of checking if the corresponding allocation unit is
+ * really the beginning of an allocation (both bits are set to 1).
+ *
+ * Looking for the ending can also be performed locklessly.
+ * It's sufficient to identify the first mapped allocation unit
+ * that is represented either as free (00) or busy (11).
+ * Even if the allocation status should change in the meanwhile, it
+ * doesn't matter, since it can only transition between free (00) and
+ * first-allocated (11).
+ *
+ * The parameter indicating to the *_free() function the size of the
+ * space that should be freed can be either set to 0, for automated
+ * assessment, or it can be specified explicitly.
+ *
+ * In case it is specified explicitly, the value is verified agaisnt what
+ * the library is tracking internally.
+ *
+ * If ever needed,

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-09 Thread Randy Dunlap 
On 02/09/2018 08:18 AM, Igor Stoppa wrote:
> 
> 
> On 05/02/18 00:34, Randy Dunlap wrote:
>> On 02/04/2018 08:47 AM, Igor Stoppa wrote:
> 
> [...]
> 
>> It would be good for a lot of this to be in a source file or the
>> pmalloc.rst documentation file instead of living only in the git repository.
> 
> This is actually about genalloc. The genalloc documentation is high
> level and mostly about the API, while this talks about the guts of the
> library. The part modified by the patch. This text doesn't seem to
> belong to the generic genalloc documentation.
> I will move it to the .c file, but isn't it too much text in a source file?

No, that will be fine.

thanks,
-- 
~Randy

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-09 Thread Randy Dunlap 
On 02/09/2018 08:18 AM, Igor Stoppa wrote:
> 
> 
> On 05/02/18 00:34, Randy Dunlap wrote:
>> On 02/04/2018 08:47 AM, Igor Stoppa wrote:
> 
> [...]
> 
>> It would be good for a lot of this to be in a source file or the
>> pmalloc.rst documentation file instead of living only in the git repository.
> 
> This is actually about genalloc. The genalloc documentation is high
> level and mostly about the API, while this talks about the guts of the
> library. The part modified by the patch. This text doesn't seem to
> belong to the generic genalloc documentation.
> I will move it to the .c file, but isn't it too much text in a source file?

No, that will be fine.

thanks,
-- 
~Randy

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-09 Thread Igor Stoppa 


On 05/02/18 00:34, Randy Dunlap wrote:
> On 02/04/2018 08:47 AM, Igor Stoppa wrote:

[...]

> It would be good for a lot of this to be in a source file or the
> pmalloc.rst documentation file instead of living only in the git repository.

This is actually about genalloc. The genalloc documentation is high
level and mostly about the API, while this talks about the guts of the
library. The part modified by the patch. This text doesn't seem to
belong to the generic genalloc documentation.
I will move it to the .c file, but isn't it too much text in a source file?

[...]

>> + * @order: pow of 2 represented by each entry in the bitmap
> 
>   power

ok

[...]

>> + * chunk_size - dimension of a chunk of memory
> 
> can this be more explicit about which dimension?

I'll put "size in bytes of a chunk of memory"


[...]

>> + * cleart_bits_ll - according to the mask, clears the bits specified by
> 
>   clear_bits_ll

yes :-(

[...]

>> - * bitmap_clear_ll - clear the specified number of bits at the specified 
>> position
>> + * alter_bitmap_ll - set or clear the entries associated to an allocation
> 
> with an allocation

ok


>> + * @alteration: selection if the bits selected should be set or cleared
> 
>indicates if

ok


[...]

>> +/* Prepare for writing the initial part of the allocation, from
>> + * starting entry, to the end of the UL bitmap element which
>> + * contains it. It might be larger than the actual allocation.
>> + */
> 
> Use kernel multi-line comment style.

ok, also for further occurrences

[...]

>> +index =  BITS_DIV_LONGS(start_bit);
> 
>   index = BITS_DIV_LONGS
> (only 1 space after '=')

oops, yes

--
thank you, igor

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-09 Thread Igor Stoppa 


On 05/02/18 00:34, Randy Dunlap wrote:
> On 02/04/2018 08:47 AM, Igor Stoppa wrote:

[...]

> It would be good for a lot of this to be in a source file or the
> pmalloc.rst documentation file instead of living only in the git repository.

This is actually about genalloc. The genalloc documentation is high
level and mostly about the API, while this talks about the guts of the
library. The part modified by the patch. This text doesn't seem to
belong to the generic genalloc documentation.
I will move it to the .c file, but isn't it too much text in a source file?

[...]

>> + * @order: pow of 2 represented by each entry in the bitmap
> 
>   power

ok

[...]

>> + * chunk_size - dimension of a chunk of memory
> 
> can this be more explicit about which dimension?

I'll put "size in bytes of a chunk of memory"


[...]

>> + * cleart_bits_ll - according to the mask, clears the bits specified by
> 
>   clear_bits_ll

yes :-(

[...]

>> - * bitmap_clear_ll - clear the specified number of bits at the specified 
>> position
>> + * alter_bitmap_ll - set or clear the entries associated to an allocation
> 
> with an allocation

ok


>> + * @alteration: selection if the bits selected should be set or cleared
> 
>indicates if

ok


[...]

>> +/* Prepare for writing the initial part of the allocation, from
>> + * starting entry, to the end of the UL bitmap element which
>> + * contains it. It might be larger than the actual allocation.
>> + */
> 
> Use kernel multi-line comment style.

ok, also for further occurrences

[...]

>> +index =  BITS_DIV_LONGS(start_bit);
> 
>   index = BITS_DIV_LONGS
> (only 1 space after '=')

oops, yes

--
thank you, igor

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-09 Thread Igor Stoppa 


On 05/02/18 05:45, Matthew Wilcox wrote:
> On Sun, Feb 04, 2018 at 02:34:08PM -0800, Randy Dunlap wrote:
>>> +/**
>>> + * cleart_bits_ll - according to the mask, clears the bits specified by
>>
>>   clear_bits_ll
> 
> 'make W=1' should catch this ... yes?
> 
> (hint: building with 'make C=1 W=1' finds all kinds of interesting issues
> in your code.  W=12 or W=123 finds too many false positives for my tastes)

ok, thank you, I will start using it

--
igor

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-09 Thread Igor Stoppa 


On 05/02/18 05:45, Matthew Wilcox wrote:
> On Sun, Feb 04, 2018 at 02:34:08PM -0800, Randy Dunlap wrote:
>>> +/**
>>> + * cleart_bits_ll - according to the mask, clears the bits specified by
>>
>>   clear_bits_ll
> 
> 'make W=1' should catch this ... yes?
> 
> (hint: building with 'make C=1 W=1' finds all kinds of interesting issues
> in your code.  W=12 or W=123 finds too many false positives for my tastes)

ok, thank you, I will start using it

--
igor

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-04 Thread Matthew Wilcox 
On Sun, Feb 04, 2018 at 02:34:08PM -0800, Randy Dunlap wrote:
> > +/**
> > + * cleart_bits_ll - according to the mask, clears the bits specified by
> 
>   clear_bits_ll

'make W=1' should catch this ... yes?

(hint: building with 'make C=1 W=1' finds all kinds of interesting issues
in your code.  W=12 or W=123 finds too many false positives for my tastes)

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-04 Thread Matthew Wilcox 
On Sun, Feb 04, 2018 at 02:34:08PM -0800, Randy Dunlap wrote:
> > +/**
> > + * cleart_bits_ll - according to the mask, clears the bits specified by
> 
>   clear_bits_ll

'make W=1' should catch this ... yes?

(hint: building with 'make C=1 W=1' finds all kinds of interesting issues
in your code.  W=12 or W=123 finds too many false positives for my tastes)

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-04 Thread Randy Dunlap 
On 02/04/2018 08:47 AM, Igor Stoppa wrote:
> The genalloc library is only capable of tracking if a certain unit of
> allocation is in use or not.
> 
> It is not capable of discerning where the memory associated to an
> allocation request begins and where it ends.
> 
> The reason is that units of allocations are tracked by using a bitmap,
> where each bit represents that the unit is either allocated (1) or
> available (0).
> 
> The user of the API must keep track of how much space was requested, if
> it ever needs to be freed.
> 
> This can cause errors being undetected.
> Ex:
> * Only a subset of the memory provided to an allocation request is freed
> * The memory from a subsequent allocation is freed
> * The memory being freed doesn't start at the beginning of an
>   allocation.
> 
> The bitmap is used because it allows to perform lockless read/write
> access, where this is supported by hw through cmpxchg.
> Similarly, it is possible to scan the bitmap for a sufficiently long
> sequence of zeros, to identify zones available for allocation.
> 
> --
> 
> This patch doubles the space reserved in the bitmap for each allocation.
> By using 2 bits per allocation, it is possible to encode also the
> information of where the allocation starts:
> (msb to the left, lsb to the right, in the following "dictionary")
> 
> 11: first allocation unit in the allocation
> 10: any subsequent allocation unit (if any) in the allocation
> 00: available allocation unit
> 01: invalid
> 
> Ex, with the same notation as above - MSb...LSb:
> 
>  ...100010101011   <-- Read in this direction.
> \__|\__|\|\|\__|
>|   | | |   \___ 4 used allocation units
>|   | | \___ 3 empty allocation units
>|   | \_ 1 used allocation unit
>|   \___ 2 used allocation units
>\___ 2 empty allocation units
> 
> Because of the encoding, the previous lockless operations are still
> possible. The only caveat is to change the parameter of the zero-finding
> function which establishes the alignment at which to perform the test
> for first zero.
> The original value of the parameter is 0, meaning that an allocation can
> start at any point in the bitmap, while the new value is 1, meaning that
> allocations can start only at even places (bit 0, bit 2, etc.)
> The number of zeroes to look for, must therefore be doubled.
> 
> When it's time to free the memory associated to an allocation request,
> it's a matter of checking if the corresponding allocation unit is really
> the beginning of an allocation (both bits are set to 1).
> Looking for the ending can also be performed locklessly.
> It's sufficient to identify the first mapped allocation unit
> that is represented either as free (00) or busy (11).
> Even if the allocation status should change in the meanwhile, it doesn't
> matter, since it can only transition between free (00) and
> first-allocated (11).
> 
> The parameter indicating to the *_free() function the size of the space
> that should be freed is not currently removed, to facilitate the
> transition, but it is verified, whenever it is not zero.
> If it is set to zero, then the free function will autonomously decide the
> size to be free, by scanning the bitmap.
> 
> About the implementation: the patch introduces the concept of "bitmap
> entry", which has a 1:1 mapping with allocation units, while the code
> being patched has a 1:1 mapping between allocation units and bits.
> 
> This means that, now, the bitmap can be extended (by following powers of
> 2), to track also other properties of the allocations, if ever needed.

It would be good for a lot of this to be in a source file or the
pmalloc.rst documentation file instead of living only in the git repository.

> 
> Signed-off-by: Igor Stoppa 
> ---
>  include/linux/genalloc.h |   4 +-
>  lib/genalloc.c   | 417 
> ---
>  2 files changed, 289 insertions(+), 132 deletions(-)
> 

> diff --git a/lib/genalloc.c b/lib/genalloc.c
> index ca06adc4f445..dde78307b093 100644
> --- a/lib/genalloc.c
> +++ b/lib/genalloc.c
> @@ -36,114 +36,221 @@
>  #include 
>  #include 
>  
> +#define ENTRY_ORDER 1UL
> +#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL)
> +#define ENTRY_HEAD ENTRY_MASK
> +#define ENTRY_UNUSED 0UL
> +#define BITS_PER_ENTRY (1U << ENTRY_ORDER)
> +#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER)
> +#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER)
> +#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG)
> +#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x)))
> +
> +#define ENTRIES_PER_LONG BITS_DIV_ENTRIES(BITS_PER_LONG)
> +
> +/* Binary pattern of 1010...1010 that spans one unsigned long. */
> +#define MASK (~0UL / 3 * 2)
> +
> +/**
> + * get_bitmap_entry - extracts the specified entry from the bitmap
> + * @map: pointer to a bitmap
> + * @entry_index: the index of the

Re: [PATCH 1/6] genalloc: track beginning of allocations

2018-02-04 Thread Randy Dunlap 
On 02/04/2018 08:47 AM, Igor Stoppa wrote:
> The genalloc library is only capable of tracking if a certain unit of
> allocation is in use or not.
> 
> It is not capable of discerning where the memory associated to an
> allocation request begins and where it ends.
> 
> The reason is that units of allocations are tracked by using a bitmap,
> where each bit represents that the unit is either allocated (1) or
> available (0).
> 
> The user of the API must keep track of how much space was requested, if
> it ever needs to be freed.
> 
> This can cause errors being undetected.
> Ex:
> * Only a subset of the memory provided to an allocation request is freed
> * The memory from a subsequent allocation is freed
> * The memory being freed doesn't start at the beginning of an
>   allocation.
> 
> The bitmap is used because it allows to perform lockless read/write
> access, where this is supported by hw through cmpxchg.
> Similarly, it is possible to scan the bitmap for a sufficiently long
> sequence of zeros, to identify zones available for allocation.
> 
> --
> 
> This patch doubles the space reserved in the bitmap for each allocation.
> By using 2 bits per allocation, it is possible to encode also the
> information of where the allocation starts:
> (msb to the left, lsb to the right, in the following "dictionary")
> 
> 11: first allocation unit in the allocation
> 10: any subsequent allocation unit (if any) in the allocation
> 00: available allocation unit
> 01: invalid
> 
> Ex, with the same notation as above - MSb...LSb:
> 
>  ...100010101011   <-- Read in this direction.
> \__|\__|\|\|\__|
>|   | | |   \___ 4 used allocation units
>|   | | \___ 3 empty allocation units
>|   | \_ 1 used allocation unit
>|   \___ 2 used allocation units
>\___ 2 empty allocation units
> 
> Because of the encoding, the previous lockless operations are still
> possible. The only caveat is to change the parameter of the zero-finding
> function which establishes the alignment at which to perform the test
> for first zero.
> The original value of the parameter is 0, meaning that an allocation can
> start at any point in the bitmap, while the new value is 1, meaning that
> allocations can start only at even places (bit 0, bit 2, etc.)
> The number of zeroes to look for, must therefore be doubled.
> 
> When it's time to free the memory associated to an allocation request,
> it's a matter of checking if the corresponding allocation unit is really
> the beginning of an allocation (both bits are set to 1).
> Looking for the ending can also be performed locklessly.
> It's sufficient to identify the first mapped allocation unit
> that is represented either as free (00) or busy (11).
> Even if the allocation status should change in the meanwhile, it doesn't
> matter, since it can only transition between free (00) and
> first-allocated (11).
> 
> The parameter indicating to the *_free() function the size of the space
> that should be freed is not currently removed, to facilitate the
> transition, but it is verified, whenever it is not zero.
> If it is set to zero, then the free function will autonomously decide the
> size to be free, by scanning the bitmap.
> 
> About the implementation: the patch introduces the concept of "bitmap
> entry", which has a 1:1 mapping with allocation units, while the code
> being patched has a 1:1 mapping between allocation units and bits.
> 
> This means that, now, the bitmap can be extended (by following powers of
> 2), to track also other properties of the allocations, if ever needed.

It would be good for a lot of this to be in a source file or the
pmalloc.rst documentation file instead of living only in the git repository.

> 
> Signed-off-by: Igor Stoppa 
> ---
>  include/linux/genalloc.h |   4 +-
>  lib/genalloc.c   | 417 
> ---
>  2 files changed, 289 insertions(+), 132 deletions(-)
> 

> diff --git a/lib/genalloc.c b/lib/genalloc.c
> index ca06adc4f445..dde78307b093 100644
> --- a/lib/genalloc.c
> +++ b/lib/genalloc.c
> @@ -36,114 +36,221 @@
>  #include 
>  #include 
>  
> +#define ENTRY_ORDER 1UL
> +#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL)
> +#define ENTRY_HEAD ENTRY_MASK
> +#define ENTRY_UNUSED 0UL
> +#define BITS_PER_ENTRY (1U << ENTRY_ORDER)
> +#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER)
> +#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER)
> +#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG)
> +#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x)))
> +
> +#define ENTRIES_PER_LONG BITS_DIV_ENTRIES(BITS_PER_LONG)
> +
> +/* Binary pattern of 1010...1010 that spans one unsigned long. */
> +#define MASK (~0UL / 3 * 2)
> +
> +/**
> + * get_bitmap_entry - extracts the specified entry from the bitmap
> + * @map: pointer to a bitmap
> + * @entry_index: the index of the desired entry in the

[PATCH 1/6] genalloc: track beginning of allocations

2018-02-04 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Ex:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

--

This patch doubles the space reserved in the bitmap for each allocation.
By using 2 bits per allocation, it is possible to encode also the
information of where the allocation starts:
(msb to the left, lsb to the right, in the following "dictionary")

11: first allocation unit in the allocation
10: any subsequent allocation unit (if any) in the allocation
00: available allocation unit
01: invalid

Ex, with the same notation as above - MSb...LSb:

 ...100010101011   <-- Read in this direction.
\__|\__|\|\|\__|
   |   | | |   \___ 4 used allocation units
   |   | | \___ 3 empty allocation units
   |   | \_ 1 used allocation unit
   |   \___ 2 used allocation units
   \___ 2 empty allocation units

Because of the encoding, the previous lockless operations are still
possible. The only caveat is to change the parameter of the zero-finding
function which establishes the alignment at which to perform the test
for first zero.
The original value of the parameter is 0, meaning that an allocation can
start at any point in the bitmap, while the new value is 1, meaning that
allocations can start only at even places (bit 0, bit 2, etc.)
The number of zeroes to look for, must therefore be doubled.

When it's time to free the memory associated to an allocation request,
it's a matter of checking if the corresponding allocation unit is really
the beginning of an allocation (both bits are set to 1).
Looking for the ending can also be performed locklessly.
It's sufficient to identify the first mapped allocation unit
that is represented either as free (00) or busy (11).
Even if the allocation status should change in the meanwhile, it doesn't
matter, since it can only transition between free (00) and
first-allocated (11).

The parameter indicating to the *_free() function the size of the space
that should be freed is not currently removed, to facilitate the
transition, but it is verified, whenever it is not zero.
If it is set to zero, then the free function will autonomously decide the
size to be free, by scanning the bitmap.

About the implementation: the patch introduces the concept of "bitmap
entry", which has a 1:1 mapping with allocation units, while the code
being patched has a 1:1 mapping between allocation units and bits.

This means that, now, the bitmap can be extended (by following powers of
2), to track also other properties of the allocations, if ever needed.

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   4 +-
 lib/genalloc.c   | 417 ---
 2 files changed, 289 insertions(+), 132 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 872f930f1b06..dcaa33e74b1c 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -32,7 +32,7 @@
 
 #include 
 #include 
-#include 
+#include 
 
 struct device;
 struct device_node;
@@ -76,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index ca06adc4f445..dde78307b093 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -36,114 +36,221 @@
 #include 
 #include 
 
+#define ENTRY_ORDER 1UL
+#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL)
+#define ENTRY_HEAD ENTRY_MASK
+#define ENTRY_UNUSED 0UL
+#define BITS_PER_ENTRY (1U << ENTRY_ORDER)
+#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER)
+#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER)
+#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG)
+#define ENTRIES_DIV_LONGS(x)

[PATCH 1/6] genalloc: track beginning of allocations

2018-02-04 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Ex:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

--

This patch doubles the space reserved in the bitmap for each allocation.
By using 2 bits per allocation, it is possible to encode also the
information of where the allocation starts:
(msb to the left, lsb to the right, in the following "dictionary")

11: first allocation unit in the allocation
10: any subsequent allocation unit (if any) in the allocation
00: available allocation unit
01: invalid

Ex, with the same notation as above - MSb...LSb:

 ...100010101011   <-- Read in this direction.
\__|\__|\|\|\__|
   |   | | |   \___ 4 used allocation units
   |   | | \___ 3 empty allocation units
   |   | \_ 1 used allocation unit
   |   \___ 2 used allocation units
   \___ 2 empty allocation units

Because of the encoding, the previous lockless operations are still
possible. The only caveat is to change the parameter of the zero-finding
function which establishes the alignment at which to perform the test
for first zero.
The original value of the parameter is 0, meaning that an allocation can
start at any point in the bitmap, while the new value is 1, meaning that
allocations can start only at even places (bit 0, bit 2, etc.)
The number of zeroes to look for, must therefore be doubled.

When it's time to free the memory associated to an allocation request,
it's a matter of checking if the corresponding allocation unit is really
the beginning of an allocation (both bits are set to 1).
Looking for the ending can also be performed locklessly.
It's sufficient to identify the first mapped allocation unit
that is represented either as free (00) or busy (11).
Even if the allocation status should change in the meanwhile, it doesn't
matter, since it can only transition between free (00) and
first-allocated (11).

The parameter indicating to the *_free() function the size of the space
that should be freed is not currently removed, to facilitate the
transition, but it is verified, whenever it is not zero.
If it is set to zero, then the free function will autonomously decide the
size to be free, by scanning the bitmap.

About the implementation: the patch introduces the concept of "bitmap
entry", which has a 1:1 mapping with allocation units, while the code
being patched has a 1:1 mapping between allocation units and bits.

This means that, now, the bitmap can be extended (by following powers of
2), to track also other properties of the allocations, if ever needed.

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   4 +-
 lib/genalloc.c   | 417 ---
 2 files changed, 289 insertions(+), 132 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 872f930f1b06..dcaa33e74b1c 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -32,7 +32,7 @@
 
 #include 
 #include 
-#include 
+#include 
 
 struct device;
 struct device_node;
@@ -76,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index ca06adc4f445..dde78307b093 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -36,114 +36,221 @@
 #include 
 #include 
 
+#define ENTRY_ORDER 1UL
+#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL)
+#define ENTRY_HEAD ENTRY_MASK
+#define ENTRY_UNUSED 0UL
+#define BITS_PER_ENTRY (1U << ENTRY_ORDER)
+#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER)
+#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER)
+#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG)
+#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x)))
+

[PATCH 1/6] genalloc: track beginning of allocations

2018-02-03 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Ex:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

--

This patch doubles the space reserved in the bitmap for each allocation.
By using 2 bits per allocation, it is possible to encode also the
information of where the allocation starts:
(msb to the left, lsb to the right, in the following "dictionary")

11: first allocation unit in the allocation
10: any subsequent allocation unit (if any) in the allocation
00: available allocation unit
01: invalid

Ex, with the same notation as above - MSb...LSb:

 ...100010101011   <-- Read in this direction.
\__|\__|\|\|\__|
   |   | | |   \___ 4 used allocation units
   |   | | \___ 3 empty allocation units
   |   | \_ 1 used allocation unit
   |   \___ 2 used allocation units
   \___ 2 empty allocation units

Because of the encoding, the previous lockless operations are still
possible. The only caveat is to change the parameter of the zero-finding
function which establishes the alignment at which to perform the test
for first zero.
The original value of the parameter is 0, meaning that an allocation can
start at any point in the bitmap, while the new value is 1, meaning that
allocations can start only at even places (bit 0, bit 2, etc.)
The number of zeroes to look for, must therefore be doubled.

When it's time to free the memory associated to an allocation request,
it's a matter of checking if the corresponding allocation unit is really
the beginning of an allocation (both bits are set to 1).
Looking for the ending can also be performed locklessly.
It's sufficient to identify the first mapped allocation unit
that is represented either as free (00) or busy (11).
Even if the allocation status should change in the meanwhile, it doesn't
matter, since it can only transition between free (00) and
first-allocated (11).

The parameter indicating to the *_free() function the size of the space
that should be freed is not currently removed, to facilitate the
transition, but it is verified, whenever it is not zero.
If it is set to zero, then the free function will autonomously decide the
size to be free, by scanning the bitmap.

About the implementation: the patch introduces the concept of "bitmap
entry", which has a 1:1 mapping with allocation units, while the code
being patched has a 1:1 mapping between allocation units and bits.

This means that, now, the bitmap can be extended (by following powers of
2), to track also other properties of the allocations, if ever needed.

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   4 +-
 lib/genalloc.c   | 417 ---
 2 files changed, 289 insertions(+), 132 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 872f930..dcaa33e 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -32,7 +32,7 @@
 
 #include 
 #include 
-#include 
+#include 
 
 struct device;
 struct device_node;
@@ -76,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index ca06adc..dde7830 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -36,114 +36,221 @@
 #include 
 #include 
 
+#define ENTRY_ORDER 1UL
+#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL)
+#define ENTRY_HEAD ENTRY_MASK
+#define ENTRY_UNUSED 0UL
+#define BITS_PER_ENTRY (1U << ENTRY_ORDER)
+#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER)
+#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER)
+#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG)
+#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x)))

[PATCH 1/6] genalloc: track beginning of allocations

2018-02-03 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Ex:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

--

This patch doubles the space reserved in the bitmap for each allocation.
By using 2 bits per allocation, it is possible to encode also the
information of where the allocation starts:
(msb to the left, lsb to the right, in the following "dictionary")

11: first allocation unit in the allocation
10: any subsequent allocation unit (if any) in the allocation
00: available allocation unit
01: invalid

Ex, with the same notation as above - MSb...LSb:

 ...100010101011   <-- Read in this direction.
\__|\__|\|\|\__|
   |   | | |   \___ 4 used allocation units
   |   | | \___ 3 empty allocation units
   |   | \_ 1 used allocation unit
   |   \___ 2 used allocation units
   \___ 2 empty allocation units

Because of the encoding, the previous lockless operations are still
possible. The only caveat is to change the parameter of the zero-finding
function which establishes the alignment at which to perform the test
for first zero.
The original value of the parameter is 0, meaning that an allocation can
start at any point in the bitmap, while the new value is 1, meaning that
allocations can start only at even places (bit 0, bit 2, etc.)
The number of zeroes to look for, must therefore be doubled.

When it's time to free the memory associated to an allocation request,
it's a matter of checking if the corresponding allocation unit is really
the beginning of an allocation (both bits are set to 1).
Looking for the ending can also be performed locklessly.
It's sufficient to identify the first mapped allocation unit
that is represented either as free (00) or busy (11).
Even if the allocation status should change in the meanwhile, it doesn't
matter, since it can only transition between free (00) and
first-allocated (11).

The parameter indicating to the *_free() function the size of the space
that should be freed is not currently removed, to facilitate the
transition, but it is verified, whenever it is not zero.
If it is set to zero, then the free function will autonomously decide the
size to be free, by scanning the bitmap.

About the implementation: the patch introduces the concept of "bitmap
entry", which has a 1:1 mapping with allocation units, while the code
being patched has a 1:1 mapping between allocation units and bits.

This means that, now, the bitmap can be extended (by following powers of
2), to track also other properties of the allocations, if ever needed.

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   4 +-
 lib/genalloc.c   | 417 ---
 2 files changed, 289 insertions(+), 132 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 872f930..dcaa33e 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -32,7 +32,7 @@
 
 #include 
 #include 
-#include 
+#include 
 
 struct device;
 struct device_node;
@@ -76,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index ca06adc..dde7830 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -36,114 +36,221 @@
 #include 
 #include 
 
+#define ENTRY_ORDER 1UL
+#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL)
+#define ENTRY_HEAD ENTRY_MASK
+#define ENTRY_UNUSED 0UL
+#define BITS_PER_ENTRY (1U << ENTRY_ORDER)
+#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER)
+#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER)
+#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG)
+#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x)))
+
+#define

[PATCH 1/6] genalloc: track beginning of allocations

2018-01-30 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Ex:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

--

This patch doubles the space reserved in the bitmap for each allocation.
By using 2 bits per allocation, it is possible to encode also the
information of where the allocation starts:
(msb to the left, lsb to the right, in the following "dictionary")

11: first allocation unit in the allocation
10: any subsequent allocation unit (if any) in the allocation
00: available allocation unit
01: invalid

Ex, with the same notation as above - MSb...LSb:

 ...100010101011   <-- Read in this direction.
\__|\__|\|\|\__|
   |   | | |   \___ 4 used allocation units
   |   | | \___ 3 empty allocation units
   |   | \_ 1 used allocation unit
   |   \___ 2 used allocation units
   \___ 2 empty allocation units

Because of the encoding, the previous lockless operations are still
possible. The only caveat is to change the parameter of the zero-finding
function which establishes the alignment at which to perform the test
for first zero.
The original value of the parameter is 0, meaning that an allocation can
start at any point in the bitmap, while the new value is 1, meaning that
allocations can start only at even places (bit 0, bit 2, etc.)
The number of zeroes to look for, must therefore be doubled.

When it's time to free the memory associated to an allocation request,
it's a matter of checking if the corresponding allocation unit is really
the beginning of an allocation (both bits are set to 1).
Looking for the ending can also be performed locklessly.
It's sufficient to identify the first mapped allocation unit
that is represented either as free (00) or busy (11).
Even if the allocation status should change in the meanwhile, it doesn't
matter, since it can only transition between free (00) and
first-allocated (11).

The parameter indicating to the *_free() function the size of the space
that should be freed is not currently removed, to facilitate the
transition, but it is verified, whenever it is not zero.
If it is set to zero, then the free function will autonomously decide the
size to be free, by scanning the bitmap.

About the implementation: the patch introduces the concept of "bitmap
entry", which has a 1:1 mapping with allocation units, while the code
being patched has a 1:1 mapping between allocation units and bits.

This means that, now, the bitmap can be extended (by following powers of
2), to track also other properties of the allocations, if ever needed.

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   2 +-
 lib/genalloc.c   | 417 ---
 2 files changed, 288 insertions(+), 131 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 872f930..0377681 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -76,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index ca06adc..dde7830 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -36,114 +36,221 @@
 #include 
 #include 
 
+#define ENTRY_ORDER 1UL
+#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL)
+#define ENTRY_HEAD ENTRY_MASK
+#define ENTRY_UNUSED 0UL
+#define BITS_PER_ENTRY (1U << ENTRY_ORDER)
+#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER)
+#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER)
+#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG)
+#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x)))
+
+#define ENTRIES_PER_LONG BITS_DIV_ENTRIES(BITS_PER_LONG)
+
+/* Binary pattern of 1010...1010 that

[PATCH 1/6] genalloc: track beginning of allocations

2018-01-30 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Ex:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

--

This patch doubles the space reserved in the bitmap for each allocation.
By using 2 bits per allocation, it is possible to encode also the
information of where the allocation starts:
(msb to the left, lsb to the right, in the following "dictionary")

11: first allocation unit in the allocation
10: any subsequent allocation unit (if any) in the allocation
00: available allocation unit
01: invalid

Ex, with the same notation as above - MSb...LSb:

 ...100010101011   <-- Read in this direction.
\__|\__|\|\|\__|
   |   | | |   \___ 4 used allocation units
   |   | | \___ 3 empty allocation units
   |   | \_ 1 used allocation unit
   |   \___ 2 used allocation units
   \___ 2 empty allocation units

Because of the encoding, the previous lockless operations are still
possible. The only caveat is to change the parameter of the zero-finding
function which establishes the alignment at which to perform the test
for first zero.
The original value of the parameter is 0, meaning that an allocation can
start at any point in the bitmap, while the new value is 1, meaning that
allocations can start only at even places (bit 0, bit 2, etc.)
The number of zeroes to look for, must therefore be doubled.

When it's time to free the memory associated to an allocation request,
it's a matter of checking if the corresponding allocation unit is really
the beginning of an allocation (both bits are set to 1).
Looking for the ending can also be performed locklessly.
It's sufficient to identify the first mapped allocation unit
that is represented either as free (00) or busy (11).
Even if the allocation status should change in the meanwhile, it doesn't
matter, since it can only transition between free (00) and
first-allocated (11).

The parameter indicating to the *_free() function the size of the space
that should be freed is not currently removed, to facilitate the
transition, but it is verified, whenever it is not zero.
If it is set to zero, then the free function will autonomously decide the
size to be free, by scanning the bitmap.

About the implementation: the patch introduces the concept of "bitmap
entry", which has a 1:1 mapping with allocation units, while the code
being patched has a 1:1 mapping between allocation units and bits.

This means that, now, the bitmap can be extended (by following powers of
2), to track also other properties of the allocations, if ever needed.

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   2 +-
 lib/genalloc.c   | 417 ---
 2 files changed, 288 insertions(+), 131 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 872f930..0377681 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -76,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index ca06adc..dde7830 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -36,114 +36,221 @@
 #include 
 #include 
 
+#define ENTRY_ORDER 1UL
+#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL)
+#define ENTRY_HEAD ENTRY_MASK
+#define ENTRY_UNUSED 0UL
+#define BITS_PER_ENTRY (1U << ENTRY_ORDER)
+#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER)
+#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER)
+#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG)
+#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x)))
+
+#define ENTRIES_PER_LONG BITS_DIV_ENTRIES(BITS_PER_LONG)
+
+/* Binary pattern of 1010...1010 that spans one unsigned long.

[PATCH 1/6] genalloc: track beginning of allocations

2018-01-24 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Ex:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

--

This patch doubles the space reserved in the bitmap for each allocation.
By using 2 bits per allocation, it is possible to encode also the
information of where the allocation starts:
(msb to the left, lsb to the right, in the following "dictionary")

11: first allocation unit in the allocation
10: any subsequent allocation unit (if any) in the allocation
00: available allocation unit
01: invalid

Ex, with the same notation as above - MSb...LSb:

 ...100010101011   <-- Read in this direction.
\__|\__|\|\|\__|
   |   | | |   \___ 4 used allocation units
   |   | | \___ 3 empty allocation units
   |   | \_ 1 used allocation unit
   |   \___ 2 used allocation units
   \___ 2 empty allocation units

Because of the encoding, the previous lockless operations are still
possible. The only caveat is to change the parameter of the zero-finding
function which establishes the alignment at which to perform the test
for first zero.
The original value of the parameter is 0, meaning that an allocation can
start at any point in the bitmap, while the new value is 1, meaning that
allocations can start only at even places (bit 0, bit 2, etc.)
The number of zeroes to look for, must therefore be doubled.

When it's time to free the memory associated to an allocation request,
it's a matter of checking if the corresponding allocation unit is really
the beginning of an allocation (both bits are set to 1).
Looking for the ending can also be performed locklessly.
It's sufficient to identify the first mapped allocation unit
that is represented either as free (00) or busy (11).
Even if the allocation status should change in the meanwhile, it doesn't
matter, since it can only transition between free (00) and
first-allocated (11).

The parameter indicating to the *_free() function the size of the space
that should be freed is not currently removed, to facilitate the
transition, but it is verified, whenever it is not zero.
If it is set to zero, then the free function will autonomously decide the
size to be free, by scanning the bitmap.

About the implementation: the patch introduces the concept of "bitmap
entry", which has a 1:1 mapping with allocation units, while the code
being patched has a 1:1 mapping between allocation units and bits.

This means that, now, the bitmap can be extended (by following powers of
2), to track also other properties of the allocations, if ever needed.

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   3 +-
 lib/genalloc.c   | 417 ---
 2 files changed, 289 insertions(+), 131 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 6dfec4d..a8fdabf 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -32,6 +32,7 @@
 
 #include 
 #include 
+#include 
 
 struct device;
 struct device_node;
@@ -75,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index 144fe6b..13bc8cf 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -36,114 +36,221 @@
 #include 
 #include 
 
+#define ENTRY_ORDER 1UL
+#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL)
+#define ENTRY_HEAD ENTRY_MASK
+#define ENTRY_UNUSED 0UL
+#define BITS_PER_ENTRY (1U << ENTRY_ORDER)
+#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER)
+#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER)
+#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG)
+#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x)))
+
+#define

[PATCH 1/6] genalloc: track beginning of allocations

2018-01-24 Thread Igor Stoppa 
The genalloc library is only capable of tracking if a certain unit of
allocation is in use or not.

It is not capable of discerning where the memory associated to an
allocation request begins and where it ends.

The reason is that units of allocations are tracked by using a bitmap,
where each bit represents that the unit is either allocated (1) or
available (0).

The user of the API must keep track of how much space was requested, if
it ever needs to be freed.

This can cause errors being undetected.
Ex:
* Only a subset of the memory provided to an allocation request is freed
* The memory from a subsequent allocation is freed
* The memory being freed doesn't start at the beginning of an
  allocation.

The bitmap is used because it allows to perform lockless read/write
access, where this is supported by hw through cmpxchg.
Similarly, it is possible to scan the bitmap for a sufficiently long
sequence of zeros, to identify zones available for allocation.

--

This patch doubles the space reserved in the bitmap for each allocation.
By using 2 bits per allocation, it is possible to encode also the
information of where the allocation starts:
(msb to the left, lsb to the right, in the following "dictionary")

11: first allocation unit in the allocation
10: any subsequent allocation unit (if any) in the allocation
00: available allocation unit
01: invalid

Ex, with the same notation as above - MSb...LSb:

 ...100010101011   <-- Read in this direction.
\__|\__|\|\|\__|
   |   | | |   \___ 4 used allocation units
   |   | | \___ 3 empty allocation units
   |   | \_ 1 used allocation unit
   |   \___ 2 used allocation units
   \___ 2 empty allocation units

Because of the encoding, the previous lockless operations are still
possible. The only caveat is to change the parameter of the zero-finding
function which establishes the alignment at which to perform the test
for first zero.
The original value of the parameter is 0, meaning that an allocation can
start at any point in the bitmap, while the new value is 1, meaning that
allocations can start only at even places (bit 0, bit 2, etc.)
The number of zeroes to look for, must therefore be doubled.

When it's time to free the memory associated to an allocation request,
it's a matter of checking if the corresponding allocation unit is really
the beginning of an allocation (both bits are set to 1).
Looking for the ending can also be performed locklessly.
It's sufficient to identify the first mapped allocation unit
that is represented either as free (00) or busy (11).
Even if the allocation status should change in the meanwhile, it doesn't
matter, since it can only transition between free (00) and
first-allocated (11).

The parameter indicating to the *_free() function the size of the space
that should be freed is not currently removed, to facilitate the
transition, but it is verified, whenever it is not zero.
If it is set to zero, then the free function will autonomously decide the
size to be free, by scanning the bitmap.

About the implementation: the patch introduces the concept of "bitmap
entry", which has a 1:1 mapping with allocation units, while the code
being patched has a 1:1 mapping between allocation units and bits.

This means that, now, the bitmap can be extended (by following powers of
2), to track also other properties of the allocations, if ever needed.

Signed-off-by: Igor Stoppa 
---
 include/linux/genalloc.h |   3 +-
 lib/genalloc.c   | 417 ---
 2 files changed, 289 insertions(+), 131 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 6dfec4d..a8fdabf 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -32,6 +32,7 @@
 
 #include 
 #include 
+#include 
 
 struct device;
 struct device_node;
@@ -75,7 +76,7 @@ struct gen_pool_chunk {
phys_addr_t phys_addr;  /* physical starting address of memory 
chunk */
unsigned long start_addr;   /* start address of memory chunk */
unsigned long end_addr; /* end address of memory chunk 
(inclusive) */
-   unsigned long bits[0];  /* bitmap for allocating memory chunk */
+   unsigned long entries[0];   /* bitmap for allocating memory chunk */
 };
 
 /*
diff --git a/lib/genalloc.c b/lib/genalloc.c
index 144fe6b..13bc8cf 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -36,114 +36,221 @@
 #include 
 #include 
 
+#define ENTRY_ORDER 1UL
+#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL)
+#define ENTRY_HEAD ENTRY_MASK
+#define ENTRY_UNUSED 0UL
+#define BITS_PER_ENTRY (1U << ENTRY_ORDER)
+#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER)
+#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER)
+#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG)
+#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x)))
+
+#define ENTRIES_PER_LONG