On 07/26/2018 03:37 PM, Andy Shevchenko wrote:
> On Thu, Jul 26, 2018 at 9:54 PM, Tony Battersby <tonyb@xxxxxxxxxxxxxxx> wrote:
>> dma_pool_alloc() scales poorly when allocating a large number of pages
>> because it does a linear scan of all previously-allocated pages before
>> allocating a new one. Improve its scalability by maintaining a separate
>> list of pages that have free blocks ready to (re)allocate. In big O
>> notation, this improves the algorithm from O(n^2) to O(n).
>
>
>> spin_lock_irqsave(&pool->lock, flags);
>> - list_for_each_entry(page, &pool->page_list, page_list) {
>> - if (page->offset < pool->allocation)
>> - goto ready;
>> + if (!list_empty(&pool->avail_page_list)) {
>> + page = list_first_entry(&pool->avail_page_list,
>> + struct dma_page,
>> + avail_page_link);
>> + goto ready;
>> }
> It looks like
>
> page = list_first_entry_or_null();
> if (page)
> goto ready;
>
> Though I don't know which one produces better code in the result.
>
> >From reader prospective of view I would go with my variant.
Thanks, I didn't know about list_first_entry_or_null().
>
>> + /* This test checks if the page is already in avail_page_list. */
>> + if (list_empty(&page->avail_page_link))
>> + list_add(&page->avail_page_link, &pool->avail_page_list);
> How can you be sure that the page you are testing for is the first one?
>
> It seems you are relying on the fact that in the list should be either
> 0 or 1 page. In that case what's the point to have a list?
>
That would be true if the test were "if (list_empty(&pool->avail_page_list))". But it is testing the list pointers in the item rather than the list pointers in the pool. It may be a bit confusing if you have never seen that usage before, which is why I added a comment. Basically, if you use list_del_init() instead of list_del(), then you can use list_empty() on the item itself to test if the item is present in a list or not. For example, the comments in list.h warn not to use list_empty() on the entry after just list_del():
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty() on entry does not return true after this, the entry is
* in an undefined state.
*/
