/*
 * A generic implementation of binary search for the Linux kernel
 *
 * Copyright (C) 2008-2009 Ksplice, Inc.
 * Author: Tim Abbott <tabbott@ksplice.com>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; version 2.
 */

#include <linux/export.h>
#include <linux/bsearch.h>

/*
 * bsearch - binary search an array of elements
 * @key: pointer to item being searched for
 * @base: pointer to first element to search
 * @num: number of elements
 * @size: size of each element
 * @cmp: pointer to comparison function
 *
 * This function does a binary search on the given array.  The
 * contents of the array should already be in ascending sorted order
 * under the provided comparison function.
 *
 * Note that the key need not have the same type as the elements in
 * the array, e.g. key could be a string and the comparison function
 * could compare the string with the struct's name field.  However, if
 * the key and elements in the array are of the same type, you can use
 * the same comparison function for both sort() and bsearch().
 */
void *bsearch(const void *key, const void *base, size_t num, size_t size,
	      int (*cmp)(const void *key, const void *elt))
{
	size_t start = 0, end = num;
	int result;

	while (start < end) {
		size_t mid = start + (end - start) / 2;

		result = cmp(key, base + mid * size);
		if (result < 0)
			end = mid;
		else if (result > 0)
			start = mid + 1;
		else
			return (void *)base + mid * size;
	}

	return NULL;
}
EXPORT_SYMBOL(bsearch);
59e7cfeb0cc9ef03d885182ce8b'>refs</a><a href='/cgit.cgi/linux/net-next.git/log/'>log</a><a href='/cgit.cgi/linux/net-next.git/tree/?id=ae4a3e028bb8b59e7cfeb0cc9ef03d885182ce8b'>tree</a><a class='active' href='/cgit.cgi/linux/net-next.git/commit/?id=ae4a3e028bb8b59e7cfeb0cc9ef03d885182ce8b'>commit</a><a href='/cgit.cgi/linux/net-next.git/diff/?id=ae4a3e028bb8b59e7cfeb0cc9ef03d885182ce8b'>diff</a></td><td class='form'><form class='right' method='get' action='/cgit.cgi/linux/net-next.git/log/'>
<input type='hidden' name='id' value='ae4a3e028bb8b59e7cfeb0cc9ef03d885182ce8b'/><select name='qt'>
<option value='grep'>log msg</option>
<option value='author'>author</option>
<option value='committer'>committer</option>
<option value='range'>range</option>
</select>
<input class='txt' type='search' size='10' name='q' value=''/>
<input type='submit' value='search'/>
</form>
</td></tr></table>
<div class='content'><div class='cgit-panel'><b>diff options</b><form method='get'><input type='hidden' name='id' value='ae4a3e028bb8b59e7cfeb0cc9ef03d885182ce8b'/><table><tr><td colspan='2'/></tr><tr><td class='label'>context:</td><td class='ctrl'><select name='context' onchange='this.form.submit();'><option value='1'>1</option><option value='2'>2</option><option value='3' selected='selected'>3</option><option value='4'>4</option><option value='5'>5</option><option value='6'>6</option><option value='7'>7</option><option value='8'>8</option><option value='9'>9</option><option value='10'>10</option><option value='15'>15</option><option value='20'>20</option><option value='25'>25</option><option value='30'>30</option><option value='35'>35</option><option value='40'>40</option></select></td></tr><tr><td class='label'>space:</td><td class='ctrl'><select name='ignorews' onchange='this.form.submit();'><option value='0' selected='selected'>include</option><option value='1'>ignore</option></select></td></tr><tr><td class='label'>mode:</td><td class='ctrl'><select name='dt' onchange='this.form.submit();'><option value='0' selected='selected'>unified</option><option value='1'>ssdiff</option><option value='2'>stat only</option></select></td></tr><tr><td/><td class='ctrl'><noscript><input type='submit' value='reload'/></noscript></td></tr></table></form></div><table summary='commit info' class='commit-info'>
<tr><th>author</th><td>Tony Lindgren &lt;tony@atomide.com&gt;</td><td class='right'>2017-01-19 08:49:07 -0800</td></tr>
<tr><th>committer</th><td>Vinod Koul &lt;vinod.koul@intel.com&gt;</td><td class='right'>2017-01-25 11:29:11 +0530</td></tr>
<tr><th>commit</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/?id=ae4a3e028bb8b59e7cfeb0cc9ef03d885182ce8b'>ae4a3e028bb8b59e7cfeb0cc9ef03d885182ce8b</a> (<a href='/cgit.cgi/linux/net-next.git/patch/?id=ae4a3e028bb8b59e7cfeb0cc9ef03d885182ce8b'>patch</a>)</td></tr>
<tr><th>tree</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/tree/?id=ae4a3e028bb8b59e7cfeb0cc9ef03d885182ce8b'>139fc7e29f97d6bb6c4dca2a97be2dc3f824bd51</a></td></tr>
<tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/?id=49def1853334396f948dcb4cedb9347abb318df5'>49def1853334396f948dcb4cedb9347abb318df5</a> (<a href='/cgit.cgi/linux/net-next.git/diff/?id=ae4a3e028bb8b59e7cfeb0cc9ef03d885182ce8b&amp;id2=49def1853334396f948dcb4cedb9347abb318df5'>diff</a>)</td></tr></table>
<div class='commit-subject'>dmaengine: cppi41: Fix runtime PM timeouts with USB mass storage</div><div class='commit-msg'>Commit fdea2d09b997 ("dmaengine: cppi41: Add basic PM runtime support")
added runtime PM support for cppi41, but had corner case issues. Some of
the issues were fixed with commit 098de42ad670 ("dmaengine: cppi41: Fix
unpaired pm runtime when only a USB hub is connected"). That fix however
caused a new regression where we can get error -115 messages with USB on
BeagleBone when connecting a USB mass storage device to a hub.

This is because when connecting a USB mass storage device to a hub, the
initial DMA transfers can take over 200ms to complete and cppi41
autosuspend delay times out.

To fix the issue, we want to implement refcounting for chan_busy array
that contains the active dma transfers. Increasing the autosuspend delay
won't help as that the delay could be potentially seconds, and it's best
to let the USB subsystem to deal with the timeouts on errors.

The earlier attempt for runtime PM was buggy as the pm_runtime_get/put()
calls could get unpaired easily as they did not follow the state of
the chan_busy array as described in commit 098de42ad670 ("dmaengine:
cppi41: Fix unpaired pm runtime when only a USB hub is connected".

Let's fix the issue by adding pm_runtime_get() to where a new transfer
is added to the chan_busy array, and calls to pm_runtime_put() where
chan_busy array entry is cleared. This prevents any autosuspend timeouts
from happening while dma transfers are active.

Fixes: 098de42ad670 ("dmaengine: cppi41: Fix unpaired pm runtime when
only a USB hub is connected")
Fixes: fdea2d09b997 ("dmaengine: cppi41: Add basic PM runtime support")
Cc: Andy Shevchenko &lt;andy.shevchenko@gmail.com&gt;
Cc: Bin Liu &lt;b-liu@ti.com&gt;
Cc: Grygorii Strashko &lt;grygorii.strashko@ti.com&gt;
Cc: Kevin Hilman &lt;khilman@baylibre.com&gt;
Cc: Patrick Titiano &lt;ptitiano@baylibre.com&gt;
Cc: Sergei Shtylyov &lt;sergei.shtylyov@cogentembedded.com&gt;
Signed-off-by: Tony Lindgren &lt;tony@atomide.com&gt;
Tested-by: Bin Liu &lt;b-liu@ti.com&gt;
Signed-off-by: Vinod Koul &lt;vinod.koul@intel.com&gt;
</div><div class='diffstat-header'><a href='/cgit.cgi/linux/net-next.git/diff/?id=ae4a3e028bb8b59e7cfeb0cc9ef03d885182ce8b'>Diffstat</a></div><table summary='diffstat' class='diffstat'>