Re: [PATCH v8.2 19/55] [media] media: convert links from array to list
Em Mon, 23 Nov 2015 17:37:54 +0200
Laurent Pinchart escreveu:
> Hi Mauro,
>
> (Resending as I've replied by mistake to the version of the patch you had
> sent
> to the media workshop list only)
(resending my answer to your previously sent review to the WS only ML.
The e-mail contents is the same as the previously sent one)
>
> Thank you for the patch.
>
Hi Laurent,
I'll be addressing the points below on separate patches, to avoid rebasing
it and causing the need for we all (me, Shuah, Javier, Sakari) to re-test
everything after patch 24 again. This way, if a regression happens, we know
what change to blame ;)
Regards,
Mauro
Em Mon, 23 Nov 2015 15:30:36 +0200
Laurent Pinchart escreveu:
> Hi Mauro,
>
> Thank you for the patch.
>
> On Monday 12 October 2015 13:43:13 Mauro Carvalho Chehab wrote:
> > The entire logic that represent graph links were developed on a
> > time where there were no needs to dynamic remove links. So,
> > although links are created/removed one by one via some
> > functions, they're stored as an array inside the entity struct.
> >
> > As the array may grow, there's a logic inside the code that
> > checks if the amount of space is not enough to store
> > the needed links. If it isn't the core uses krealloc()
> > to change the size of the link, with is bad, as it
> > leaves the memory fragmented.
>
> I agree with the change made in this patch, but I'm not sure if fragmentation
> is really the issue. I wouldn't be surprised if we ended up with more
> fragmented memory.
That would actually depend on how things get allocated/deallocated.
If we discover that fragmentation is actually increasing, we could
change the code later to use a lookaside cache.
>
> > So, convert links into a list.
> >
> > Also, currently, both source and sink entities need the link
> > at the graph traversal logic inside media_entity. So there's
> > a logic duplicating all links. That makes it to spend
> > twice the memory needed. This is not a big deal for today's
> > usage, where the number of links are not big.
> >
> > Yet, if during the MC workshop discussions, it was said that
> > IIO graphs could have up to 4,000 entities. So, we may
> > want to remove the duplication on some future. The problem
> > is that it would require a separate linked list to store
> > the backlinks inside the entity, or to use a more complex
> > algorithm to do graph backlink traversal, with is something
> > that the current graph traversal inside the core can't cope
> > with. So, let's postpone a such change if/when it is actually
> > needed.
>
> The media_link structure uses 44 bytes on 32-bit architectures and 84 bytes
> on
> 64-bit architecture. It will thus be allocated out of the 64-bytes and 96-
> bytes pools respectively. That's a 12.5% memory waste on 64-bit architectures
> and 31.25% on 32-bit architecture. If you're concerned about memory usage
> (and
> I think we all should) a linked list is less efficient than an array in this
> case (and even more so if you take the struct list_head into account).
I doubt that the amount of memory spent at the media controller
would actually cause impact, as the size of those structs are a
way smaller than the size of video buffers. Anyway, if we found
later that this would cause troubles, we can redesign it.
>
> > Change-Id: I558e8f87f200fe5f83ddaafe5560f91f0d906b63
>
> No need to infect mainline with gerrit nonsense :-)
I'm not using gerrit ;) I'm just adding this crap because the change ID
is a good way to detect if a patch is new or not. I have some scripts
that use those IDs to detect it, when working with this 80+ patch series.
In any case, the scripts I use to pull patches at the main tree will
remove those stuff.
>
> > Signed-off-by: Mauro Carvalho Chehab
> > ---
> > drivers/media/dvb-core/dvb_frontend.c | 9 +--
> > drivers/media/media-device.c | 25 +++---
> > drivers/media/media-entity.c | 128 ---
> > drivers/media/usb/au0828/au0828-core.c| 12 ++-
> > drivers/media/usb/au0828/au0828-video.c | 8 +-
> > drivers/media/usb/cx231xx/cx231xx-video.c | 8 +-
> > include/media/media-entity.h | 10 +--
> > 7 files changed, 97 insertions(+), 103 deletions(-)
>
> [snip]
>
> > diff --git a/drivers/media/media-device.c b/drivers/media/media-device.c
> > index 0d85c6c28004..3e649cacfc07 100644
> > --- a/drivers/media/media-device.c
> > +++ b/drivers/media/media-device.c
> > @@ -25,6 +25,7 @@
> > #include
> > #include
> > #include
> > +#include
>
> Could you please keep headers sorted alphabetically ?
Ok, I'll reorder on a later patch.
>
> > #include
> > #include
>
> [snip]
>
> > @@ -150,22 +151,21 @@ static long __media_device_enum_links(struct
> > media_device *mdev, }
> >
> > if (links->links) {
> > - struct media_link_desc __user *ulink;
> > - unsigned int l;
> > + struct media_
Re: [PATCH v8.2 19/55] [media] media: convert links from array to list
Hi Mauro,
(Resending as I've replied by mistake to the version of the patch you had sent
to the media workshop list only)
Thank you for the patch.
On Monday 12 October 2015 13:43:13 Mauro Carvalho Chehab wrote:
> The entire logic that represent graph links were developed on a
> time where there were no needs to dynamic remove links. So,
> although links are created/removed one by one via some
> functions, they're stored as an array inside the entity struct.
>
> As the array may grow, there's a logic inside the code that
> checks if the amount of space is not enough to store
> the needed links. If it isn't the core uses krealloc()
> to change the size of the link, with is bad, as it
> leaves the memory fragmented.
I agree with the change made in this patch, but I'm not sure if fragmentation
is really the issue. I wouldn't be surprised if we ended up with more
fragmented memory.
> So, convert links into a list.
>
> Also, currently, both source and sink entities need the link
> at the graph traversal logic inside media_entity. So there's
> a logic duplicating all links. That makes it to spend
> twice the memory needed. This is not a big deal for today's
> usage, where the number of links are not big.
>
> Yet, if during the MC workshop discussions, it was said that
> IIO graphs could have up to 4,000 entities. So, we may
> want to remove the duplication on some future. The problem
> is that it would require a separate linked list to store
> the backlinks inside the entity, or to use a more complex
> algorithm to do graph backlink traversal, with is something
> that the current graph traversal inside the core can't cope
> with. So, let's postpone a such change if/when it is actually
> needed.
The media_link structure uses 44 bytes on 32-bit architectures and 84 bytes on
64-bit architecture. It will thus be allocated out of the 64-bytes and 96-
bytes pools respectively. That's a 12.5% memory waste on 64-bit architectures
and 31.25% on 32-bit architecture. If you're concerned about memory usage (and
I think we all should) a linked list is less efficient than an array in this
case (and even more so if you take the struct list_head into account).
> Change-Id: I558e8f87f200fe5f83ddaafe5560f91f0d906b63
No need to infect mainline with gerrit nonsense
> Signed-off-by: Mauro Carvalho Chehab
> ---
> drivers/media/dvb-core/dvb_frontend.c | 9 +--
> drivers/media/media-device.c | 25 +++---
> drivers/media/media-entity.c | 128 ---
> drivers/media/usb/au0828/au0828-core.c| 12 ++-
> drivers/media/usb/au0828/au0828-video.c | 8 +-
> drivers/media/usb/cx231xx/cx231xx-video.c | 8 +-
> include/media/media-entity.h | 10 +--
> 7 files changed, 97 insertions(+), 103 deletions(-)
[snip]
> diff --git a/drivers/media/media-device.c b/drivers/media/media-device.c
> index 0d85c6c28004..3e649cacfc07 100644
> --- a/drivers/media/media-device.c
> +++ b/drivers/media/media-device.c
> @@ -25,6 +25,7 @@
> #include
> #include
> #include
> +#include
Could you please keep headers sorted alphabetically ?
> #include
> #include
[snip]
> @@ -150,22 +151,21 @@ static long __media_device_enum_links(struct
> media_device *mdev, }
>
> if (links->links) {
> - struct media_link_desc __user *ulink;
> - unsigned int l;
> + struct media_link *ent_link;
> + struct media_link_desc __user *ulink = links->links;
Might be slightly nitpicking, but I think variables would be more coherent if
they were called
struct media_link_desc __user *ulink = links->links;
struct media_link *link;
...
>
> - for (l = 0, ulink = links->links; l < entity->num_links; l++)
{
> + list_for_each_entry(ent_link, &entity->links, list) {
> struct media_link_desc link;
and
struct media_link_desc klink;
here.
> /* Ignore backlinks. */
> - if (entity->links[l].source->entity != entity)
> + if (ent_link->source->entity != entity)
> continue;
> -
> memset(&link, 0, sizeof(link));
> - media_device_kpad_to_upad(entity->links[l].source,
> + media_device_kpad_to_upad(ent_link->source,
> &link.source);
> - media_device_kpad_to_upad(entity->links[l].sink,
> + media_device_kpad_to_upad(ent_link->sink,
> &link.sink);
> - link.flags = entity->links[l].flags;
> + link.flags = ent_link->flags;
> if (copy_to_user(ulink, &link, sizeof(*ulink)))
> return -EFAULT;
> ulink++;
> @@ -437,6 +437,7 @@ int __must_check media_devi
Re: [PATCH v8.2 19/55] [media] media: convert links from array to list
The entire logic that represent graph links were developed on a
time where there were no needs to dynamic remove links. So,
although links are created/removed one by one via some
functions, they're stored as an array inside the entity struct.
As the array may grow, there's a logic inside the code that
checks if the amount of space is not enough to store
the needed links. If it isn't the core uses krealloc()
to change the size of the link, with is bad, as it
leaves the memory fragmented.
So, convert links into a list.
Also, currently, both source and sink entities need the link
at the graph traversal logic inside media_entity. So there's
a logic duplicating all links. That makes it to spend
twice the memory needed. This is not a big deal for today's
usage, where the number of links are not big.
Yet, if during the MC workshop discussions, it was said that
IIO graphs could have up to 4,000 entities. So, we may
want to remove the duplication on some future. The problem
is that it would require a separate linked list to store
the backlinks inside the entity, or to use a more complex
algorithm to do graph backlink traversal, with is something
that the current graph traversal inside the core can't cope
with. So, let's postpone a such change if/when it is actually
needed.
Signed-off-by: Mauro Carvalho Chehab
diff --git a/drivers/media/dvb-core/dvb_frontend.c
b/drivers/media/dvb-core/dvb_frontend.c
index c38ef1a72b4a..2d06bcff0946 100644
--- a/drivers/media/dvb-core/dvb_frontend.c
+++ b/drivers/media/dvb-core/dvb_frontend.c
@@ -622,7 +622,7 @@ static int dvb_enable_media_tuner(struct dvb_frontend *fe)
struct media_device *mdev = adapter->mdev;
struct media_entity *entity, *source;
struct media_link *link, *found_link = NULL;
- int i, ret, n_links = 0, active_links = 0;
+ int ret, n_links = 0, active_links = 0;
fepriv->pipe_start_entity = NULL;
@@ -632,8 +632,7 @@ static int dvb_enable_media_tuner(struct dvb_frontend *fe)
entity = fepriv->dvbdev->entity;
fepriv->pipe_start_entity = entity;
- for (i = 0; i < entity->num_links; i++) {
- link = &entity->links[i];
+ list_for_each_entry(link, &entity->links, list) {
if (link->sink->entity == entity) {
found_link = link;
n_links++;
@@ -659,13 +658,11 @@ static int dvb_enable_media_tuner(struct dvb_frontend *fe)
source = found_link->source->entity;
fepriv->pipe_start_entity = source;
- for (i = 0; i < source->num_links; i++) {
+ list_for_each_entry(link, &source->links, list) {
struct media_entity *sink;
int flags = 0;
- link = &source->links[i];
sink = link->sink->entity;
-
if (sink == entity)
flags = MEDIA_LNK_FL_ENABLED;
diff --git a/drivers/media/media-device.c b/drivers/media/media-device.c
index 0d85c6c28004..3e649cacfc07 100644
--- a/drivers/media/media-device.c
+++ b/drivers/media/media-device.c
@@ -25,6 +25,7 @@
#include
#include
#include
+#include
#include
#include
@@ -150,22 +151,21 @@ static long __media_device_enum_links(struct media_device
*mdev,
}
if (links->links) {
- struct media_link_desc __user *ulink;
- unsigned int l;
+ struct media_link *ent_link;
+ struct media_link_desc __user *ulink = links->links;
- for (l = 0, ulink = links->links; l < entity->num_links; l++) {
+ list_for_each_entry(ent_link, &entity->links, list) {
struct media_link_desc link;
/* Ignore backlinks. */
- if (entity->links[l].source->entity != entity)
+ if (ent_link->source->entity != entity)
continue;
-
memset(&link, 0, sizeof(link));
- media_device_kpad_to_upad(entity->links[l].source,
+ media_device_kpad_to_upad(ent_link->source,
&link.source);
- media_device_kpad_to_upad(entity->links[l].sink,
+ media_device_kpad_to_upad(ent_link->sink,
&link.sink);
- link.flags = entity->links[l].flags;
+ link.flags = ent_link->flags;
if (copy_to_user(ulink, &link, sizeof(*ulink)))
return -EFAULT;
ulink++;
@@ -437,6 +437,7 @@ int __must_check media_device_register_entity(struct
media_device *mdev,
/* Warn if we apparently re-register an entity */
WARN_ON(entity->graph_obj.mdev != NULL);
entity->graph_obj.mdev = mdev;
+ INIT_LIST_HEAD(&entity->links);
spin_lock(&mdev->lock);
/* Ini
[PATCH v8.2 19/55] [media] media: convert links from array to list
The entire logic that represent graph links were developed on a
time where there were no needs to dynamic remove links. So,
although links are created/removed one by one via some
functions, they're stored as an array inside the entity struct.
As the array may grow, there's a logic inside the code that
checks if the amount of space is not enough to store
the needed links. If it isn't the core uses krealloc()
to change the size of the link, with is bad, as it
leaves the memory fragmented.
So, convert links into a list.
Also, currently, both source and sink entities need the link
at the graph traversal logic inside media_entity. So there's
a logic duplicating all links. That makes it to spend
twice the memory needed. This is not a big deal for today's
usage, where the number of links are not big.
Yet, if during the MC workshop discussions, it was said that
IIO graphs could have up to 4,000 entities. So, we may
want to remove the duplication on some future. The problem
is that it would require a separate linked list to store
the backlinks inside the entity, or to use a more complex
algorithm to do graph backlink traversal, with is something
that the current graph traversal inside the core can't cope
with. So, let's postpone a such change if/when it is actually
needed.
Signed-off-by: Mauro Carvalho Chehab
---
Sorry, I did some mess with my trees, and just re-sent the same
patch as before. That's the right one with Javier fixes.
Please ignore PATCH v8.1.
This version contains a few bug fixes folded on it, resulted
from Javier's tests. I won't be respinning the entire series
just due to that.
Javier: Thanks for that! I'll add you proper credits on
the final version.
diff --git a/drivers/media/dvb-core/dvb_frontend.c
b/drivers/media/dvb-core/dvb_frontend.c
index c38ef1a72b4a..2d06bcff0946 100644
--- a/drivers/media/dvb-core/dvb_frontend.c
+++ b/drivers/media/dvb-core/dvb_frontend.c
@@ -622,7 +622,7 @@ static int dvb_enable_media_tuner(struct dvb_frontend *fe)
struct media_device *mdev = adapter->mdev;
struct media_entity *entity, *source;
struct media_link *link, *found_link = NULL;
- int i, ret, n_links = 0, active_links = 0;
+ int ret, n_links = 0, active_links = 0;
fepriv->pipe_start_entity = NULL;
@@ -632,8 +632,7 @@ static int dvb_enable_media_tuner(struct dvb_frontend *fe)
entity = fepriv->dvbdev->entity;
fepriv->pipe_start_entity = entity;
- for (i = 0; i < entity->num_links; i++) {
- link = &entity->links[i];
+ list_for_each_entry(link, &entity->links, list) {
if (link->sink->entity == entity) {
found_link = link;
n_links++;
@@ -659,13 +658,11 @@ static int dvb_enable_media_tuner(struct dvb_frontend *fe)
source = found_link->source->entity;
fepriv->pipe_start_entity = source;
- for (i = 0; i < source->num_links; i++) {
+ list_for_each_entry(link, &source->links, list) {
struct media_entity *sink;
int flags = 0;
- link = &source->links[i];
sink = link->sink->entity;
-
if (sink == entity)
flags = MEDIA_LNK_FL_ENABLED;
diff --git a/drivers/media/media-device.c b/drivers/media/media-device.c
index 0d85c6c28004..3e649cacfc07 100644
--- a/drivers/media/media-device.c
+++ b/drivers/media/media-device.c
@@ -25,6 +25,7 @@
#include
#include
#include
+#include
#include
#include
@@ -150,22 +151,21 @@ static long __media_device_enum_links(struct media_device
*mdev,
}
if (links->links) {
- struct media_link_desc __user *ulink;
- unsigned int l;
+ struct media_link *ent_link;
+ struct media_link_desc __user *ulink = links->links;
- for (l = 0, ulink = links->links; l < entity->num_links; l++) {
+ list_for_each_entry(ent_link, &entity->links, list) {
struct media_link_desc link;
/* Ignore backlinks. */
- if (entity->links[l].source->entity != entity)
+ if (ent_link->source->entity != entity)
continue;
-
memset(&link, 0, sizeof(link));
- media_device_kpad_to_upad(entity->links[l].source,
+ media_device_kpad_to_upad(ent_link->source,
&link.source);
- media_device_kpad_to_upad(entity->links[l].sink,
+ media_device_kpad_to_upad(ent_link->sink,
&link.sink);
- link.flags = entity->links[l].flags;
+ link.flags = ent_link->flags;
if (copy_to_user(ulink, &link, sizeof(*ulink)))
return
