Re: [PATCH v8 19/55] [media] media: convert links from array to list

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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.

-- 
Kind regards,

Sakari Ailus
e-mail: sakari.ailus@xxxxxx	XMPP: sailus@xxxxxxxxxxxxxx
--
To unsubscribe from this list: send the line "unsubscribe linux-media" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html



[Index of Archives]     [Linux Input]     [Video for Linux]     [Gstreamer Embedded]     [Mplayer Users]     [Linux USB Devel]     [Linux Audio Users]     [Linux Kernel]     [Linux SCSI]     [Yosemite Backpacking]
  Powered by Linux