| Message ID | 2547965181e69b3e0e8c4c1aed67668d580a8e58.1440902901.git.mchehab@osg.samsung.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
Hi Mauro, On Sun, Aug 30, 2015 at 12:06:30AM -0300, 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. The Linux kernel constantly allocates and releases memory for various reasons. Even the V4L2 IOCTL handler does that when the argument is too large to fit into the stack-allocated buffer. There's no reason to avoid allocating and releasing small chunks of memory when hardware configuration changes. > > So, convert links into a list. Instead, if you're worried about the time the memory re-allocation takes that'd be needed to dynamically add a large number of links, I'd just allocate more memory at a time, say, rounding up to a power of two, and use vmalloc() instead of kmalloc() when the size grows over one page. That'd avoid the vast majority of reallocs without wasting much memory: the granularity of memory allocation is much larger than the size of struct media_link except in the case of very small link numbers. The reason I'm proposing this is that linked lists, as you're allocating them, can end up anywhere in the system memory. Walking over the media graph is quite a job if you have as many links as in your example, and the additional cache misses caused by scattering the data structure all over the system memory will not make the effort smaller. Adding links dynamically (for a change in hardware topology?) is by far less performance critical than e.g. starting and stopping streaming or enumerating the links so the latter should have the priority IMHO. > > 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. Would keeping the links in a linked list help with that? I think this could be done using both the current arrays or linked lists --- instead of storing links themselves, you'd store pointers to the links (array or a linked list) which then are stored elsewhere. Helper functions would be needed to e.g. loop over the links in that case though.
On 09/04/2015 10:41 AM, Sakari Ailus wrote: > Hi Mauro, > > On Sun, Aug 30, 2015 at 12:06:30AM -0300, 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. > > The Linux kernel constantly allocates and releases memory for various > reasons. Even the V4L2 IOCTL handler does that when the argument is too > large to fit into the stack-allocated buffer. There's no reason to avoid > allocating and releasing small chunks of memory when hardware configuration > changes. > >> >> So, convert links into a list. > > Instead, if you're worried about the time the memory re-allocation takes > that'd be needed to dynamically add a large number of links, I'd just > allocate more memory at a time, say, rounding up to a power of two, and use > vmalloc() instead of kmalloc() when the size grows over one page. > > That'd avoid the vast majority of reallocs without wasting much memory: the > granularity of memory allocation is much larger than the size of struct > media_link except in the case of very small link numbers. > > The reason I'm proposing this is that linked lists, as you're allocating > them, can end up anywhere in the system memory. Walking over the media graph > is quite a job if you have as many links as in your example, and the > additional cache misses caused by scattering the data structure all over the > system memory will not make the effort smaller. > > Adding links dynamically (for a change in hardware topology?) is by far less > performance critical than e.g. starting and stopping streaming or > enumerating the links so the latter should have the priority IMHO. You don't do either of these jobs very often either. As I have said before, the enemy of media drivers is rarely performance but always complexity. Based on the patches I've seen I agree with Mauro that a linked list is a better fit and simplifies the code. If you have *proof* that this hurts performance in certain real-life cases, then this can always be optimized later. But unless someone shows me proof that it really hurts performance in realistic cases, I will always favor simplicity. In all the time that I have been involved in the media subsystem the only performance issue I am aware of was that enumerating all the links in the MC can be too slow due to all the ioctl calls that it takes (vsp driver). This will be solved with the proposed G_TOPOLOGY ioctl since that returns everything in a single call (or two calls if you need to know how much memory to allocate first). Hmm, actually, I think there is another related issue if you want to enumerate all combinations of pixelformats, discrete framesizes and framerates. There too the problem is the number of ioctl calls you have to do. It's never been important enough to do something about it, though. Bottom line, always go for simplicity unless you can demonstrate with numbers that there are real performance issues. Regards, Hans > >> >> 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. > > Would keeping the links in a linked list help with that? > > I think this could be done using both the current arrays or linked lists --- > instead of storing links themselves, you'd store pointers to the links > (array or a linked list) which then are stored elsewhere. Helper functions > would be needed to e.g. loop over the links in that case though. > -- 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
Em Fri, 04 Sep 2015 11:00:38 +0200 Hans Verkuil <hverkuil@xs4all.nl> escreveu: > On 09/04/2015 10:41 AM, Sakari Ailus wrote: > > Hi Mauro, > > > > On Sun, Aug 30, 2015 at 12:06:30AM -0300, 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. > > > > The Linux kernel constantly allocates and releases memory for various > > reasons. Even the V4L2 IOCTL handler does that when the argument is too > > large to fit into the stack-allocated buffer. There's no reason to avoid > > allocating and releasing small chunks of memory when hardware configuration > > changes. > > > >> > >> So, convert links into a list. > > > > Instead, if you're worried about the time the memory re-allocation takes > > that'd be needed to dynamically add a large number of links, I'd just > > allocate more memory at a time, say, rounding up to a power of two, and use > > vmalloc() instead of kmalloc() when the size grows over one page. We had support to allocate more links via that "extra_links" parameter. This never worked in practice: there was no single client for that. > > > > That'd avoid the vast majority of reallocs without wasting much memory: the > > granularity of memory allocation is much larger than the size of struct > > media_link except in the case of very small link numbers. > > > > The reason I'm proposing this is that linked lists, as you're allocating > > them, can end up anywhere in the system memory. Walking over the media graph > > is quite a job if you have as many links as in your example, and the > > additional cache misses caused by scattering the data structure all over the > > system memory will not make the effort smaller. First of all, I agree with Hans: the major issues we have is not due to performance, but due to complexity. Talking about the graph traversal algorithm, it curently doesn't work even for simple hybrid TV devices, as it currently allows to have only 64 entities, due to the loop detection code there. Ok, it would be possible to extend it to support real case scenarios, but the patch is not as trivial as changing the max number of entities. Just doing that would cause the stack to crash, as the bitmap structs are allocated at the stack. Also, what you're saying regards to the increase of cache misses, this is not true. The links memory are still fragmented, as they're allocated during entities init code. On most codes, that means that they'll be allocated after each entity. So, memory would look like: entity#1 links for entity#1 entity#2 links for entity#2 ... If you want to put the links at consecutive addresses, what you would need to do is to create first all entities, and then create the links altogether. After this patch, drivers that have timing issues can do it, having the memory allocated as: entity#1 entity#2 links for entity#1 links for entity#2 ... So, I won't doubt that this patch would actually improve performance by putting the links altogether ;) Ok, when we have lots of dynamic entity creation/removal, the memory will become more fragmented, but that would happen with or without this change. I mean, if this patch is not applied and entity#2 is created after a long runtime, we would have: entity#1 links for entity #1 <some other data allocated> entity#2 links for entity #2 While, on the other case, the memory would be: entity#1 links for entity #1 (except for the link with entity#2) backlinks for entity #1 (except for the link with entity#2) <some other data allocated> entity#2 link between entity#1 and entity#2 other links for entity #2 I bet performance would be pretty much the same. Anyway, let's go to real numbers. Javier ran some tests in order to check what would be the difference using the omap3isp driver. He hacked yavta to suppress glibc calls to printf() with this hack: #define printf(...) do { } while (0) Then, he measured the times with and without this patch series. Doing the graph traversal needed for this command: $ time ./yavta/yavta -f UYVY -s 720x312 -n 1 --capture=1 -F /dev/video2 Resulted in: real 0m0.022s user 0m0.000s sys 0m0.010s The complete results form Javier are at: http://hastebin.com/turixebuyo.pl He did that with both with and without this patch series. On all cases, it took 10ms to setup the pipeline. > > > > Adding links dynamically (for a change in hardware topology?) is by far less > > performance critical than e.g. starting and stopping streaming or > > enumerating the links so the latter should have the priority IMHO. > > You don't do either of these jobs very often either. As I have said before, the > enemy of media drivers is rarely performance but always complexity. Based > on the patches I've seen I agree with Mauro that a linked list is a better > fit and simplifies the code. > > If you have *proof* that this hurts performance in certain real-life cases, > then this can always be optimized later. > > But unless someone shows me proof that it really hurts performance in realistic > cases, I will always favor simplicity. > > In all the time that I have been involved in the media subsystem the only > performance issue I am aware of was that enumerating all the links in the MC > can be too slow due to all the ioctl calls that it takes (vsp driver). This > will be solved with the proposed G_TOPOLOGY ioctl since that returns everything > in a single call (or two calls if you need to know how much memory to allocate > first). Some timing measurements using au0828 driver: This is the time mc_nextgen_test takes with a hack that: - Reduces the number of demux outputs from 256 to 5; - Reduces the number of output ringbuffers from 512 to 10; - Adds one subdev for tuner (helps me to test subdevs). $ time ~/mc_nextgen_test version: 97 number of entities: 19 number of interfaces: 7 number of pads: 28 number of links: 25 real 0m0.002s user 0m0.000s sys 0m0.000s The time spent at the Kernel (sys) is less than 1ms. Hardly would cause any harm. Btw, that's with the real graph (without a fake subdev for tuner, and with all ringbuffers mapped): $ time ~/mc_nextgen_test version: 2354 number of entities: 521 number of interfaces: 6 number of pads: 781 number of links: 526 real 0m0.002s user 0m0.000s sys 0m0.000s No difference: it still took less than 1 ms. Ok, this is not graph traversal, but the G_TOPOLOGY should read all objects that belong to the graph. So, if cache miss would cause any performance issue, some difference would be noticed here. Also, please notice that cache misses inside a graph traversal loop should happen only one for a given memory object, as, the memory will be cached on the second access to it (provided, of course, that the amount of memory used to store the links is smaller than the size of the cache - that should be the case even for graphs like what we have at au0828 without the hacks). We might try to use ftrace to measure the time spent in Kernel to have a better measurement, but I'm afraid that ftrace could actually mangle the results by causing cache flushes at L1 cache, due to the long jump to the ftrace event store routine. > > Hmm, actually, I think there is another related issue if you want to enumerate > all combinations of pixelformats, discrete framesizes and framerates. There too > the problem is the number of ioctl calls you have to do. It's never been > important enough to do something about it, though. > > Bottom line, always go for simplicity unless you can demonstrate with numbers > that there are real performance issues. > > Regards, > > Hans > > > > >> > >> 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. > > > > Would keeping the links in a linked list help with that? Well, if we reduce the links by half, removing the allocation of a memory for backlinks, then yes. I was planning to to that, but this would require a non-trivial change at the graph traversal algorithm and the usage of a separate linked list for the backlink. Please notice that, if you're concerned with cache misses, using half of the memory to store the links/backlinks would actually be an improvement in terms of performance. > > > > I think this could be done using both the current arrays or linked lists --- > > instead of storing links themselves, you'd store pointers to the links > > (array or a linked list) which then are stored elsewhere. Helper functions > > would be needed to e.g. loop over the links in that case though. > > > -- 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
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 9f8e0145db7a..ff63201443d7 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; 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 (list_is_last(&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_last_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)++; + list_rotate_left(&link_top(graph)); 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)++; + list_rotate_left(&link_top(graph)); continue; } /* Push the new entity to stack and start over. */ - link_top(graph)++; + list_rotate_left(&link_top(graph)); 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..bb89cedb0c40 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,
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>