[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.

It should also be noticed that 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.
A linked list is less efficient than an array in this case, but
this could later be optimized if we can get rid of the reverse
links (with would reduce memory allocation by 50%).

Signed-off-by: Mauro Carvalho Chehab <mchehab@osg.samsung.com>

1 files changed, 5 insertions, 5 deletions

diff --git a/include/media/media-entity.h b/include/media/media-entity.h
index 4d5fc91c4134..2e5646cf36e7 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 */
 
@@ -220,7 +220,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);
@@ -254,7 +254,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,