[v8.2,19/55,media] media: convert links from array to list
diff mbox

Message ID ba0462d54436f101880bd43fe217f47533bcbcf3.1441540862.git.mchehab@osg.samsung.com
State New
Headers show

Commit Message

Mauro Carvalho Chehab Sept. 6, 2015, 12:02 p.m. UTC
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 <mchehab@osg.samsung.com>

Comments

Laurent Pinchart Nov. 23, 2015, 3:37 p.m. UTC | #1
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 <mchehab@osg.samsung.com>
> ---
>  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 <linux/ioctl.h>
>  #include <linux/media.h>
>  #include <linux/types.h>
> +#include <linux/slab.h>

Could you please keep headers sorted alphabetically ?

>  #include <media/media-device.h>
>  #include <media/media-devnode.h>

[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_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);

I'd move this to media_entity_init(). I've spent time wondering how the code 
could work without crashing during testing as the list wasn't initialized in 
media_entity_init().

Speaking of testing, have you checked for memory leaks with kmemleak ? Given 
the extent of the rework I think this should really be tested.

> 
>       spin_lock(&mdev->lock);
>       /* Initialize media_gobj embedded at the entity */
> @@ -465,13 +466,17 @@ void media_device_unregister_entity(struct
> media_entity *entity) {
>       int i;
>       struct media_device *mdev = entity->graph_obj.mdev;
> +     struct media_link *link, *tmp;
> 
>       if (mdev == NULL)
>               return;
> 
>       spin_lock(&mdev->lock);
> -     for (i = 0; i < entity->num_links; i++)
> -             media_gobj_remove(&entity->links[i].graph_obj);
> +     list_for_each_entry_safe(link, tmp, &entity->links, list) {
> +             media_gobj_remove(&link->graph_obj);
> +             list_del(&link->list);
> +             kfree(link);

Shouldn't you remove the backlinks too ? How about calling 
__media_entity_remove_link() to centralize the link removal code ?

> +     }
>       for (i = 0; i < entity->num_pads; i++)
>               media_gobj_remove(&entity->pads[i].graph_obj);
>       media_gobj_remove(&entity->graph_obj);
> diff --git a/drivers/media/media-entity.c b/drivers/media/media-entity.c
> index 0926f08be981..d5efa0e2c88c 100644
> --- a/drivers/media/media-entity.c
> +++ b/drivers/media/media-entity.c
> @@ -221,21 +221,13 @@ int
>  media_entity_init(struct media_entity *entity, u16 num_pads,
>                 struct media_pad *pads)
>  {
> -     struct media_link *links;
> -     unsigned int max_links = num_pads;
>       unsigned int i;
> 
> -     links = kzalloc(max_links * sizeof(links[0]), GFP_KERNEL);
> -     if (links == NULL)
> -             return -ENOMEM;
> -

Now that the function doesn't allocate links anymore you should fix its 
kerneldoc that still mentions preallocation.

>       entity->group_id = 0;
> -     entity->max_links = max_links;
>       entity->num_links = 0;
>       entity->num_backlinks = 0;
>       entity->num_pads = num_pads;
>       entity->pads = pads;
> -     entity->links = links;
> 
>       for (i = 0; i < num_pads; i++) {
>               pads[i].entity = entity;
> @@ -249,7 +241,13 @@ EXPORT_SYMBOL_GPL(media_entity_init);
>  void
>  media_entity_cleanup(struct media_entity *entity)
>  {
> -     kfree(entity->links);
> +     struct media_link *link, *tmp;
> +
> +     list_for_each_entry_safe(link, tmp, &entity->links, list) {
> +             media_gobj_remove(&link->graph_obj);
> +             list_del(&link->list);
> +             kfree(link);
> +     }
>  }
>  EXPORT_SYMBOL_GPL(media_entity_cleanup);
> 
> @@ -275,7 +273,7 @@ static void stack_push(struct media_entity_graph *graph,
> return;
>       }
>       graph->top++;
> -     graph->stack[graph->top].link = 0;
> +     graph->stack[graph->top].link = (&entity->links)->next;

Anything wrong with entity->links.next ?

>       graph->stack[graph->top].entity = entity;
>  }
> 
> @@ -317,6 +315,7 @@ void media_entity_graph_walk_start(struct
> media_entity_graph *graph, }
>  EXPORT_SYMBOL_GPL(media_entity_graph_walk_start);
> 
> +

No need for an extra blank line.

>  /**
>   * media_entity_graph_walk_next - Get the next entity in the graph
>   * @graph: Media graph structure
> @@ -340,14 +339,16 @@ media_entity_graph_walk_next(struct media_entity_graph
> *graph) * top of the stack until no more entities on the level can be
>        * found.
>        */
> -     while (link_top(graph) < stack_top(graph)->num_links) {
> +     while (link_top(graph) != &(stack_top(graph)->links)) {

No need for parentheses around the second operand of !=.

>               struct media_entity *entity = stack_top(graph);
> -             struct media_link *link = &entity->links[link_top(graph)];
> +             struct media_link *link;
>               struct media_entity *next;
> 
> +             link = list_entry(link_top(graph), typeof(*link), list);
> +
>               /* The link is not enabled so we do not follow. */
>               if (!(link->flags & MEDIA_LNK_FL_ENABLED)) {
> -                     link_top(graph)++;
> +                     link_top(graph) = link_top(graph)->next;
>                       continue;
>               }

[snip]

> @@ -395,6 +396,7 @@ __must_check int media_entity_pipeline_start(struct
> media_entity *entity, struct media_device *mdev = entity->graph_obj.mdev;
>       struct media_entity_graph graph;
>       struct media_entity *entity_err = entity;
> +     struct media_link *link;

Nitpicking, I would have placed the variable declaration inside of the while 
loop, where i was declared.

>       int ret;
> 
>       mutex_lock(&mdev->graph_mutex);
> @@ -404,7 +406,6 @@ __must_check int media_entity_pipeline_start(struct
> media_entity *entity, while ((entity =
> media_entity_graph_walk_next(&graph))) {
>               DECLARE_BITMAP(active, entity->num_pads);
>               DECLARE_BITMAP(has_no_links, entity->num_pads);
> -             unsigned int i;
> 
>               entity->stream_count++;
>               WARN_ON(entity->pipe && entity->pipe != pipe);
> @@ -420,8 +421,7 @@ __must_check int media_entity_pipeline_start(struct
> media_entity *entity, bitmap_zero(active, entity->num_pads);
>               bitmap_fill(has_no_links, entity->num_pads);
> 
> -             for (i = 0; i < entity->num_links; i++) {
> -                     struct media_link *link = &entity->links[i];
> +             list_for_each_entry(link, &entity->links, list) {
>                       struct media_pad *pad = link->sink->entity == entity
>                                               ? link->sink : link->source;

[snip]

> +static void __media_entity_remove_link(struct media_entity *entity,
> +                                    struct media_link *link);
> +

No forward declaration please, let's reorder functions instead.

>  int
>  media_create_pad_link(struct media_entity *source, u16 source_pad,
>                        struct media_entity *sink, u16 sink_pad, u32 flags)

[snip]

> -void __media_entity_remove_links(struct media_entity *entity)
> +static void __media_entity_remove_link(struct media_entity *entity,
> +                                    struct media_link *link)

No need for a __ in the function name, there's not media_entity_remove_link() 
function.

>  {
> -     unsigned int i;
> +     struct media_link *rlink, *tmp;
> +     struct media_entity *remote;
> +     unsigned int r = 0;
> +
> +     if (link->source->entity == entity)
> +             remote = link->sink->entity;
> +     else
> +             remote = link->source->entity;
> 
> -     for (i = 0; i < entity->num_links; i++) {
> -             struct media_link *link = &entity->links[i];
> -             struct media_entity *remote;
> -             unsigned int r = 0;
> +     list_for_each_entry_safe(rlink, tmp, &remote->links, list) {
> +             if (rlink != link->reverse) {
> +                     r++;

The variable is incremented here but otherwise never used, you can remove it.

> +                     continue;
> +             }
> 
>               if (link->source->entity == entity)
> -                     remote = link->sink->entity;
> -             else
> -                     remote = link->source->entity;
> +                     remote->num_backlinks--;
> 
> -             while (r < remote->num_links) {
> -                     struct media_link *rlink = &remote->links[r];
> -
> -                     if (rlink != link->reverse) {
> -                             r++;
> -                             continue;
> -                     }
> +             if (--remote->num_links == 0)
> +                     break;
> 
> -                     if (link->source->entity == entity)
> -                             remote->num_backlinks--;
> +             /* Remove the remote link */

Shouldn't you call media_gobj_remove() ?

> +             list_del(&rlink->list);
> +             kfree(rlink);
> +     }

And here too ?

> +     list_del(&link->list);
> +     kfree(link);
> +}
> 
> -                     if (--remote->num_links == 0)
> -                             break;
> +void __media_entity_remove_links(struct media_entity *entity)
> +{
> +     struct media_link *link, *tmp;
> 
> -                     /* Insert last entry in place of the dropped link. */
> -                     *rlink = remote->links[remote->num_links];
> -             }
> -     }
> +     list_for_each_entry_safe(link, tmp, &entity->links, list)
> +             __media_entity_remove_link(entity, link);
> 
>       entity->num_links = 0;
>       entity->num_backlinks = 0;
Mauro Carvalho Chehab Nov. 23, 2015, 3:41 p.m. UTC | #2
Em Mon, 23 Nov 2015 17:37:54 +0200
Laurent Pinchart <laurent.pinchart@ideasonboard.com> 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 <laurent.pinchart@ideasonboard.com> 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 <mchehab@osg.samsung.com>
> > ---
> >  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 <linux/ioctl.h>
> >  #include <linux/media.h>
> >  #include <linux/types.h>
> > +#include <linux/slab.h>  
> 
> Could you please keep headers sorted alphabetically ?  

Ok, I'll reorder on a later patch.

>   
> >  #include <media/media-device.h>
> >  #include <media/media-devnode.h>  
> 
> [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;  

Nomenclatures tend to generate endless discussions ;)

IMO, calling it as "link" here is confusing, as it is not clear if
this is a Kernel or an Userspace "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;  

and calling it as "klink" is confusing to me ;) as this is the struct
defined at the userspace API, and not the struct defined at the
Kernelspace ABI.

Perhaps we could call those media_link_desc as "klink_desc" and
"ulink_desc", instead.

> 
> 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_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);  
> 
> I'd move this to media_entity_init(). I've spent time wondering how the code 
> could work without crashing during testing as the list wasn't initialized in 
> media_entity_init().  

I wrote this code lots of months ago... I guess there was a reason for this
to be here, and not there, but I can't remember why.

I'll give it a try.

> 
> Speaking of testing, have you checked for memory leaks with kmemleak ? Given 
> the extent of the rework I think this should really be tested.  

No, I didn't. I'm not sure if au0828 currently passes on kmemleak
or not. What I did is I checked that all created graph objects were
removed, via enabling the dynamic_prinks at the graph object init/remove
functions.

>   
> > 
> >  	spin_lock(&mdev->lock);
> >  	/* Initialize media_gobj embedded at the entity */
> > @@ -465,13 +466,17 @@ void media_device_unregister_entity(struct
> > media_entity *entity) {
> >  	int i;
> >  	struct media_device *mdev = entity->graph_obj.mdev;
> > +	struct media_link *link, *tmp;
> > 
> >  	if (mdev == NULL)
> >  		return;
> > 
> >  	spin_lock(&mdev->lock);
> > -	for (i = 0; i < entity->num_links; i++)
> > -		media_gobj_remove(&entity->links[i].graph_obj);
> > +	list_for_each_entry_safe(link, tmp, &entity->links, list) {
> > +		media_gobj_remove(&link->graph_obj);
> > +		list_del(&link->list);
> > +		kfree(link);  
> 
> Shouldn't you remove the backlinks too ? How about calling 
> __media_entity_remove_link() to centralize the link removal code ?  

Yes. I'll use __media_entity_remove_link() here.

>   
> > +	}
> >  	for (i = 0; i < entity->num_pads; i++)
> >  		media_gobj_remove(&entity->pads[i].graph_obj);
> >  	media_gobj_remove(&entity->graph_obj);
> > diff --git a/drivers/media/media-entity.c b/drivers/media/media-entity.c
> > index 0926f08be981..d5efa0e2c88c 100644
> > --- a/drivers/media/media-entity.c
> > +++ b/drivers/media/media-entity.c
> > @@ -221,21 +221,13 @@ int
> >  media_entity_init(struct media_entity *entity, u16 num_pads,
> >  		  struct media_pad *pads)
> >  {
> > -	struct media_link *links;
> > -	unsigned int max_links = num_pads;
> >  	unsigned int i;
> > 
> > -	links = kzalloc(max_links * sizeof(links[0]), GFP_KERNEL);
> > -	if (links == NULL)
> > -		return -ENOMEM;
> > -  
> 
> Now that the function doesn't allocate links anymore you should fix its 
> kerneldoc that still mentions preallocation.  

OK.

> >  	entity->group_id = 0;
> > -	entity->max_links = max_links;
> >  	entity->num_links = 0;
> >  	entity->num_backlinks = 0;
> >  	entity->num_pads = num_pads;
> >  	entity->pads = pads;
> > -	entity->links = links;
> > 
> >  	for (i = 0; i < num_pads; i++) {
> >  		pads[i].entity = entity;
> > @@ -249,7 +241,13 @@ EXPORT_SYMBOL_GPL(media_entity_init);
> >  void
> >  media_entity_cleanup(struct media_entity *entity)
> >  {
> > -	kfree(entity->links);
> > +	struct media_link *link, *tmp;
> > +
> > +	list_for_each_entry_safe(link, tmp, &entity->links, list) {
> > +		media_gobj_remove(&link->graph_obj);
> > +		list_del(&link->list);
> > +		kfree(link);
> > +	}
> >  }
> >  EXPORT_SYMBOL_GPL(media_entity_cleanup);
> > 
> > @@ -275,7 +273,7 @@ static void stack_push(struct media_entity_graph *graph,
> > return;
> >  	}
> >  	graph->top++;
> > -	graph->stack[graph->top].link = 0;
> > +	graph->stack[graph->top].link = (&entity->links)->next;  
> 
> Anything wrong with entity->links.next ?  

No, but I use a regex to find all the occurrences of the previous
struct ;)

I'll change it.

>   
> >  	graph->stack[graph->top].entity = entity;
> >  }
> > 
> > @@ -317,6 +315,7 @@ void media_entity_graph_walk_start(struct
> > media_entity_graph *graph, }
> >  EXPORT_SYMBOL_GPL(media_entity_graph_walk_start);
> > 
> > +  
> 
> No need for an extra blank line.  

OK.

> >  /**
> >   * media_entity_graph_walk_next - Get the next entity in the graph
> >   * @graph: Media graph structure
> > @@ -340,14 +339,16 @@ media_entity_graph_walk_next(struct media_entity_graph
> > *graph) * top of the stack until no more entities on the level can be
> >  	 * found.
> >  	 */
> > -	while (link_top(graph) < stack_top(graph)->num_links) {
> > +	while (link_top(graph) != &(stack_top(graph)->links)) {  
> 
> No need for parentheses around the second operand of !=.  

Ok, I'll remove it.

> >  		struct media_entity *entity = stack_top(graph);
> > -		struct media_link *link = &entity->links[link_top(graph)];
> > +		struct media_link *link;
> >  		struct media_entity *next;
> > 
> > +		link = list_entry(link_top(graph), typeof(*link), list);
> > +
> >  		/* The link is not enabled so we do not follow. */
> >  		if (!(link->flags & MEDIA_LNK_FL_ENABLED)) {
> > -			link_top(graph)++;
> > +			link_top(graph) = link_top(graph)->next;
> >  			continue;
> >  		}  
> 
> [snip]
>   
> > @@ -395,6 +396,7 @@ __must_check int media_entity_pipeline_start(struct
> > media_entity *entity, struct media_device *mdev = entity->graph_obj.mdev;
> >  	struct media_entity_graph graph;
> >  	struct media_entity *entity_err = entity;
> > +	struct media_link *link;  
> 
> Nitpicking, I would have placed the variable declaration inside of the while 
> loop, where i was declared.  

OK.

> >  	int ret;
> > 
> >  	mutex_lock(&mdev->graph_mutex);
> > @@ -404,7 +406,6 @@ __must_check int media_entity_pipeline_start(struct
> > media_entity *entity, while ((entity =
> > media_entity_graph_walk_next(&graph))) {
> >  		DECLARE_BITMAP(active, entity->num_pads);
> >  		DECLARE_BITMAP(has_no_links, entity->num_pads);
> > -		unsigned int i;
> > 
> >  		entity->stream_count++;
> >  		WARN_ON(entity->pipe && entity->pipe != pipe);
> > @@ -420,8 +421,7 @@ __must_check int media_entity_pipeline_start(struct
> > media_entity *entity, bitmap_zero(active, entity->num_pads);
> >  		bitmap_fill(has_no_links, entity->num_pads);
> > 
> > -		for (i = 0; i < entity->num_links; i++) {
> > -			struct media_link *link = &entity->links[i];
> > +		list_for_each_entry(link, &entity->links, list) {
> >  			struct media_pad *pad = link->sink->entity == entity
> >  						? link->sink : link->source;  
> 
> [snip]
>   
> > +static void __media_entity_remove_link(struct media_entity *entity,
> > +				       struct media_link *link);
> > +  
> 
> No forward declaration please, let's reorder functions instead.  

OK.

>   
> >  int
> >  media_create_pad_link(struct media_entity *source, u16 source_pad,
> >  			 struct media_entity *sink, u16 sink_pad, u32 flags)  
> 
> [snip]
--
To unsubscribe from this list: send the line "unsubscribe linux-media" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch
diff mbox

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 <linux/ioctl.h>
 #include <linux/media.h>
 #include <linux/types.h>
+#include <linux/slab.h>
 
 #include <media/media-device.h>
 #include <media/media-devnode.h>
@@ -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);
 	/* Initialize media_gobj embedded at the entity */
@@ -465,13 +466,17 @@  void media_device_unregister_entity(struct media_entity *entity)
 {
 	int i;
 	struct media_device *mdev = entity->graph_obj.mdev;
+	struct media_link *link, *tmp;
 
 	if (mdev == NULL)
 		return;
 
 	spin_lock(&mdev->lock);
-	for (i = 0; i < entity->num_links; i++)
-		media_gobj_remove(&entity->links[i].graph_obj);
+	list_for_each_entry_safe(link, tmp, &entity->links, list) {
+		media_gobj_remove(&link->graph_obj);
+		list_del(&link->list);
+		kfree(link);
+	}
 	for (i = 0; i < entity->num_pads; i++)
 		media_gobj_remove(&entity->pads[i].graph_obj);
 	media_gobj_remove(&entity->graph_obj);
diff --git a/drivers/media/media-entity.c b/drivers/media/media-entity.c
index 0926f08be981..d5efa0e2c88c 100644
--- a/drivers/media/media-entity.c
+++ b/drivers/media/media-entity.c
@@ -221,21 +221,13 @@  int
 media_entity_init(struct media_entity *entity, u16 num_pads,
 		  struct media_pad *pads)
 {
-	struct media_link *links;
-	unsigned int max_links = num_pads;
 	unsigned int i;
 
-	links = kzalloc(max_links * sizeof(links[0]), GFP_KERNEL);
-	if (links == NULL)
-		return -ENOMEM;
-
 	entity->group_id = 0;
-	entity->max_links = max_links;
 	entity->num_links = 0;
 	entity->num_backlinks = 0;
 	entity->num_pads = num_pads;
 	entity->pads = pads;
-	entity->links = links;
 
 	for (i = 0; i < num_pads; i++) {
 		pads[i].entity = entity;
@@ -249,7 +241,13 @@  EXPORT_SYMBOL_GPL(media_entity_init);
 void
 media_entity_cleanup(struct media_entity *entity)
 {
-	kfree(entity->links);
+	struct media_link *link, *tmp;
+
+	list_for_each_entry_safe(link, tmp, &entity->links, list) {
+		media_gobj_remove(&link->graph_obj);
+		list_del(&link->list);
+		kfree(link);
+	}
 }
 EXPORT_SYMBOL_GPL(media_entity_cleanup);
 
@@ -275,7 +273,7 @@  static void stack_push(struct media_entity_graph *graph,
 		return;
 	}
 	graph->top++;
-	graph->stack[graph->top].link = 0;
+	graph->stack[graph->top].link = (&entity->links)->next;
 	graph->stack[graph->top].entity = entity;
 }
 
@@ -317,6 +315,7 @@  void media_entity_graph_walk_start(struct media_entity_graph *graph,
 }
 EXPORT_SYMBOL_GPL(media_entity_graph_walk_start);
 
+
 /**
  * media_entity_graph_walk_next - Get the next entity in the graph
  * @graph: Media graph structure
@@ -340,14 +339,16 @@  media_entity_graph_walk_next(struct media_entity_graph *graph)
 	 * top of the stack until no more entities on the level can be
 	 * found.
 	 */
-	while (link_top(graph) < stack_top(graph)->num_links) {
+	while (link_top(graph) != &(stack_top(graph)->links)) {
 		struct media_entity *entity = stack_top(graph);
-		struct media_link *link = &entity->links[link_top(graph)];
+		struct media_link *link;
 		struct media_entity *next;
 
+		link = list_entry(link_top(graph), typeof(*link), list);
+
 		/* The link is not enabled so we do not follow. */
 		if (!(link->flags & MEDIA_LNK_FL_ENABLED)) {
-			link_top(graph)++;
+			link_top(graph) = link_top(graph)->next;
 			continue;
 		}
 
@@ -358,12 +359,12 @@  media_entity_graph_walk_next(struct media_entity_graph *graph)
 
 		/* Has the entity already been visited? */
 		if (__test_and_set_bit(media_entity_id(next), graph->entities)) {
-			link_top(graph)++;
+			link_top(graph) = link_top(graph)->next;
 			continue;
 		}
 
 		/* Push the new entity to stack and start over. */
-		link_top(graph)++;
+		link_top(graph) = link_top(graph)->next;
 		stack_push(graph, next);
 	}
 
@@ -395,6 +396,7 @@  __must_check int media_entity_pipeline_start(struct media_entity *entity,
 	struct media_device *mdev = entity->graph_obj.mdev;
 	struct media_entity_graph graph;
 	struct media_entity *entity_err = entity;
+	struct media_link *link;
 	int ret;
 
 	mutex_lock(&mdev->graph_mutex);
@@ -404,7 +406,6 @@  __must_check int media_entity_pipeline_start(struct media_entity *entity,
 	while ((entity = media_entity_graph_walk_next(&graph))) {
 		DECLARE_BITMAP(active, entity->num_pads);
 		DECLARE_BITMAP(has_no_links, entity->num_pads);
-		unsigned int i;
 
 		entity->stream_count++;
 		WARN_ON(entity->pipe && entity->pipe != pipe);
@@ -420,8 +421,7 @@  __must_check int media_entity_pipeline_start(struct media_entity *entity,
 		bitmap_zero(active, entity->num_pads);
 		bitmap_fill(has_no_links, entity->num_pads);
 
-		for (i = 0; i < entity->num_links; i++) {
-			struct media_link *link = &entity->links[i];
+		list_for_each_entry(link, &entity->links, list) {
 			struct media_pad *pad = link->sink->entity == entity
 						? link->sink : link->source;
 
@@ -582,25 +582,20 @@  EXPORT_SYMBOL_GPL(media_entity_put);
 
 static struct media_link *media_entity_add_link(struct media_entity *entity)
 {
-	if (entity->num_links >= entity->max_links) {
-		struct media_link *links = entity->links;
-		unsigned int max_links = entity->max_links + 2;
-		unsigned int i;
+	struct media_link *link;
 
-		links = krealloc(links, max_links * sizeof(*links), GFP_KERNEL);
-		if (links == NULL)
-			return NULL;
+	link = kzalloc(sizeof(*link), GFP_KERNEL);
+	if (link == NULL)
+		return NULL;
 
-		for (i = 0; i < entity->num_links; i++)
-			links[i].reverse->reverse = &links[i];
+	list_add_tail(&link->list, &entity->links);
 
-		entity->max_links = max_links;
-		entity->links = links;
-	}
-
-	return &entity->links[entity->num_links++];
+	return link;
 }
 
+static void __media_entity_remove_link(struct media_entity *entity,
+				       struct media_link *link);
+
 int
 media_create_pad_link(struct media_entity *source, u16 source_pad,
 			 struct media_entity *sink, u16 sink_pad, u32 flags)
@@ -629,7 +624,7 @@  media_create_pad_link(struct media_entity *source, u16 source_pad,
 	 */
 	backlink = media_entity_add_link(sink);
 	if (backlink == NULL) {
-		source->num_links--;
+		__media_entity_remove_link(source, link);
 		return -ENOMEM;
 	}
 
@@ -645,43 +640,51 @@  media_create_pad_link(struct media_entity *source, u16 source_pad,
 	backlink->reverse = link;
 
 	sink->num_backlinks++;
+	sink->num_links++;
+	source->num_links++;
 
 	return 0;
 }
 EXPORT_SYMBOL_GPL(media_create_pad_link);
 
-void __media_entity_remove_links(struct media_entity *entity)
+static void __media_entity_remove_link(struct media_entity *entity,
+				       struct media_link *link)
 {
-	unsigned int i;
+	struct media_link *rlink, *tmp;
+	struct media_entity *remote;
+	unsigned int r = 0;
 
-	for (i = 0; i < entity->num_links; i++) {
-		struct media_link *link = &entity->links[i];
-		struct media_entity *remote;
-		unsigned int r = 0;
+	if (link->source->entity == entity)
+		remote = link->sink->entity;
+	else
+		remote = link->source->entity;
+
+	list_for_each_entry_safe(rlink, tmp, &remote->links, list) {
+		if (rlink != link->reverse) {
+			r++;
+			continue;
+		}
 
 		if (link->source->entity == entity)
-			remote = link->sink->entity;
-		else
-			remote = link->source->entity;
+			remote->num_backlinks--;
 
-		while (r < remote->num_links) {
-			struct media_link *rlink = &remote->links[r];
+		if (--remote->num_links == 0)
+			break;
 
-			if (rlink != link->reverse) {
-				r++;
-				continue;
-			}
-
-			if (link->source->entity == entity)
-				remote->num_backlinks--;
-
-			if (--remote->num_links == 0)
-				break;
-
-			/* Insert last entry in place of the dropped link. */
-			*rlink = remote->links[remote->num_links];
-		}
+		/* Remove the remote link */
+		list_del(&rlink->list);
+		kfree(rlink);
 	}
+	list_del(&link->list);
+	kfree(link);
+}
+
+void __media_entity_remove_links(struct media_entity *entity)
+{
+	struct media_link *link, *tmp;
+
+	list_for_each_entry_safe(link, tmp, &entity->links, list)
+		__media_entity_remove_link(entity, link);
 
 	entity->num_links = 0;
 	entity->num_backlinks = 0;
@@ -806,11 +809,8 @@  struct media_link *
 media_entity_find_link(struct media_pad *source, struct media_pad *sink)
 {
 	struct media_link *link;
-	unsigned int i;
-
-	for (i = 0; i < source->entity->num_links; ++i) {
-		link = &source->entity->links[i];
 
+	list_for_each_entry(link, &source->entity->links, list) {
 		if (link->source->entity == source->entity &&
 		    link->source->index == source->index &&
 		    link->sink->entity == sink->entity &&
@@ -834,11 +834,9 @@  EXPORT_SYMBOL_GPL(media_entity_find_link);
  */
 struct media_pad *media_entity_remote_pad(struct media_pad *pad)
 {
-	unsigned int i;
-
-	for (i = 0; i < pad->entity->num_links; i++) {
-		struct media_link *link = &pad->entity->links[i];
+	struct media_link *link;
 
+	list_for_each_entry(link, &pad->entity->links, list) {
 		if (!(link->flags & MEDIA_LNK_FL_ENABLED))
 			continue;
 
diff --git a/drivers/media/usb/au0828/au0828-core.c b/drivers/media/usb/au0828/au0828-core.c
index a55eb524ea21..7f645bcb7463 100644
--- a/drivers/media/usb/au0828/au0828-core.c
+++ b/drivers/media/usb/au0828/au0828-core.c
@@ -261,13 +261,11 @@  static void au0828_create_media_graph(struct au0828_dev *dev)
 
 	if (tuner)
 		media_create_pad_link(tuner, 0, decoder, 0,
-					 MEDIA_LNK_FL_ENABLED);
-	if (dev->vdev.entity.links)
-		media_create_pad_link(decoder, 1, &dev->vdev.entity, 0,
-				 MEDIA_LNK_FL_ENABLED);
-	if (dev->vbi_dev.entity.links)
-		media_create_pad_link(decoder, 2, &dev->vbi_dev.entity, 0,
-				 MEDIA_LNK_FL_ENABLED);
+				      MEDIA_LNK_FL_ENABLED);
+	media_create_pad_link(decoder, 1, &dev->vdev.entity, 0,
+			      MEDIA_LNK_FL_ENABLED);
+	media_create_pad_link(decoder, 2, &dev->vbi_dev.entity, 0,
+			      MEDIA_LNK_FL_ENABLED);
 #endif
 }
 
diff --git a/drivers/media/usb/au0828/au0828-video.c b/drivers/media/usb/au0828/au0828-video.c
index 2c040056d4eb..4511e2893282 100644
--- a/drivers/media/usb/au0828/au0828-video.c
+++ b/drivers/media/usb/au0828/au0828-video.c
@@ -643,7 +643,7 @@  static int au0828_enable_analog_tuner(struct au0828_dev *dev)
 	struct media_device *mdev = dev->media_dev;
 	struct media_entity *source;
 	struct media_link *link, *found_link = NULL;
-	int i, ret, active_links = 0;
+	int ret, active_links = 0;
 
 	if (!mdev || !dev->decoder)
 		return 0;
@@ -655,8 +655,7 @@  static int au0828_enable_analog_tuner(struct au0828_dev *dev)
 	 * do DVB streaming while the DMA engine is being used for V4L2,
 	 * this should be enough for the actual needs.
 	 */
-	for (i = 0; i < dev->decoder->num_links; i++) {
-		link = &dev->decoder->links[i];
+	list_for_each_entry(link, &dev->decoder->links, list) {
 		if (link->sink->entity == dev->decoder) {
 			found_link = link;
 			if (link->flags & MEDIA_LNK_FL_ENABLED)
@@ -669,11 +668,10 @@  static int au0828_enable_analog_tuner(struct au0828_dev *dev)
 		return 0;
 
 	source = found_link->source->entity;
-	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 == dev->decoder)
diff --git a/drivers/media/usb/cx231xx/cx231xx-video.c b/drivers/media/usb/cx231xx/cx231xx-video.c
index 8f04b125486f..e8baff4d6290 100644
--- a/drivers/media/usb/cx231xx/cx231xx-video.c
+++ b/drivers/media/usb/cx231xx/cx231xx-video.c
@@ -106,7 +106,7 @@  static int cx231xx_enable_analog_tuner(struct cx231xx *dev)
 	struct media_device *mdev = dev->media_dev;
 	struct media_entity  *entity, *decoder = NULL, *source;
 	struct media_link *link, *found_link = NULL;
-	int i, ret, active_links = 0;
+	int ret, active_links = 0;
 
 	if (!mdev)
 		return 0;
@@ -127,8 +127,7 @@  static int cx231xx_enable_analog_tuner(struct cx231xx *dev)
 	if (!decoder)
 		return 0;
 
-	for (i = 0; i < decoder->num_links; i++) {
-		link = &decoder->links[i];
+	list_for_each_entry(link, &decoder->links, list) {
 		if (link->sink->entity == decoder) {
 			found_link = link;
 			if (link->flags & MEDIA_LNK_FL_ENABLED)
@@ -141,11 +140,10 @@  static int cx231xx_enable_analog_tuner(struct cx231xx *dev)
 		return 0;
 
 	source = found_link->source->entity;
-	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)
diff --git a/include/media/media-entity.h b/include/media/media-entity.h
index 7df8836f4eef..7016f0619415 100644
--- a/include/media/media-entity.h
+++ b/include/media/media-entity.h
@@ -74,6 +74,7 @@  struct media_pipeline {
 
 struct media_link {
 	struct media_gobj graph_obj;
+	struct list_head list;
 	struct media_pad *source;	/* Source pad */
 	struct media_pad *sink;		/* Sink pad  */
 	struct media_link *reverse;	/* Link in the reverse direction */
@@ -116,10 +117,9 @@  struct media_entity {
 	u16 num_links;			/* Number of existing links, both
 					 * enabled and disabled */
 	u16 num_backlinks;		/* Number of backlinks */
-	u16 max_links;			/* Maximum number of links */
 
-	struct media_pad *pads;		/* Pads array (num_pads elements) */
-	struct media_link *links;	/* Links array (max_links elements)*/
+	struct media_pad *pads;		/* Pads array (num_pads objects) */
+	struct list_head links;		/* Links list */
 
 	const struct media_entity_operations *ops;	/* Entity operations */
 
@@ -213,7 +213,7 @@  static inline u32 media_gobj_gen_id(enum media_gobj_type type, u32 local_id)
 struct media_entity_graph {
 	struct {
 		struct media_entity *entity;
-		int link;
+		struct list_head *link;
 	} stack[MEDIA_ENTITY_ENUM_MAX_DEPTH];
 
 	DECLARE_BITMAP(entities, MEDIA_ENTITY_ENUM_MAX_ID);
@@ -247,7 +247,7 @@  void media_gobj_init(struct media_device *mdev,
 void media_gobj_remove(struct media_gobj *gobj);
 
 int media_entity_init(struct media_entity *entity, u16 num_pads,
-		struct media_pad *pads);
+		      struct media_pad *pads);
 void media_entity_cleanup(struct media_entity *entity);
 
 int media_create_pad_link(struct media_entity *source, u16 source_pad,