lib/int_sqrt.c: optimize square root algorithm

Optimize the current version of the shift-and-subtract (hardware)
algorithm, described by John von Newmann[1] and Guy L Steele.

Iterating 1,000,000 times, perf shows for the current version:

 Performance counter stats for './sqrt-curr' (10 runs):

         27.170996 task-clock                #    0.979 CPUs utilized            ( +-  3.19% )
                 3 context-switches          #    0.103 K/sec                    ( +-  4.76% )
                 0 cpu-migrations            #    0.004 K/sec                    ( +-100.00% )
               104 page-faults               #    0.004 M/sec                    ( +-  0.16% )
        64,921,199 cycles                    #    2.389 GHz                      ( +-  0.03% )
        28,967,789 stalled-cycles-frontend   #   44.62% frontend cycles idle     ( +-  0.18% )
   <not supported> stalled-cycles-backend
       104,502,623 instructions              #    1.61  insns per cycle
                                             #    0.28  stalled cycles per insn  ( +-  0.00% )
        34,088,368 branches                  # 1254.587 M/sec                    ( +-  0.00% )
             4,901 branch-misses             #    0.01% of all branches          ( +-  1.32% )

       0.027763015 seconds time elapsed                                          ( +-  3.22% )

And for the new version:

Performance counter stats for './sqrt-new' (10 runs):

          0.496869 task-clock                #    0.519 CPUs utilized            ( +-  2.38% )
                 0 context-switches          #    0.000 K/sec
                 0 cpu-migrations            #    0.403 K/sec                    ( +-100.00% )
               104 page-faults               #    0.209 M/sec                    ( +-  0.15% )
           590,760 cycles                    #    1.189 GHz                      ( +-  2.35% )
           395,053 stalled-cycles-frontend   #   66.87% frontend cycles idle     ( +-  3.67% )
   <not supported> stalled-cycles-backend
           398,963 instructions              #    0.68  insns per cycle
                                             #    0.99  stalled cycles per insn  ( +-  0.39% )
            70,228 branches                  #  141.341 M/sec                    ( +-  0.36% )
             3,364 branch-misses             #    4.79% of all branches          ( +-  5.45% )

       0.000957440 seconds time elapsed                                          ( +-  2.42% )

Furthermore, this saves space in instruction text:

   text    data     bss     dec     hex filename
    111       0       0     111      6f lib/int_sqrt-baseline.o
     89       0       0      89      59 lib/int_sqrt.o

[1] http://en.wikipedia.org/wiki/First_Draft_of_a_Report_on_the_EDVAC

Signed-off-by: Davidlohr Bueso <davidlohr.bueso@hp.com>
Reviewed-by: Jonathan Gonzalez <jgonzlez@linets.cl>
Tested-by: Jonathan Gonzalez <jgonzlez@linets.cl>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
block: add runtime pm helpers

Add runtime pm helper functions:

void blk_pm_runtime_init(struct request_queue *q, struct device *dev)
  - Initialization function for drivers to call.

int blk_pre_runtime_suspend(struct request_queue *q)
  - If any requests are in the queue, mark last busy and return -EBUSY.
    Otherwise set q->rpm_status to RPM_SUSPENDING and return 0.

void blk_post_runtime_suspend(struct request_queue *q, int err)
  - If the suspend succeeded then set q->rpm_status to RPM_SUSPENDED.
    Otherwise set it to RPM_ACTIVE and mark last busy.

void blk_pre_runtime_resume(struct request_queue *q)
  - Set q->rpm_status to RPM_RESUMING.

void blk_post_runtime_resume(struct request_queue *q, int err)
  - If the resume succeeded then set q->rpm_status to RPM_ACTIVE
    and call __blk_run_queue, then mark last busy and autosuspend.
    Otherwise set q->rpm_status to RPM_SUSPENDED.

The idea and API is designed by Alan Stern and described here:
http://marc.info/?l=linux-scsi&m=133727953625963&w=2

Signed-off-by: Lin Ming <ming.m.lin@intel.com>
Signed-off-by: Aaron Lu <aaron.lu@intel.com>
Acked-by: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
block: implement runtime pm strategy

When a request is added:
    If device is suspended or is suspending and the request is not a
    PM request, resume the device.

When the last request finishes:
    Call pm_runtime_mark_last_busy().

When pick a request:
    If device is resuming/suspending, then only PM request is allowed
    to go.

The idea and API is designed by Alan Stern and described here:
http://marc.info/?l=linux-scsi&m=133727953625963&w=2

Signed-off-by: Lin Ming <ming.m.lin@intel.com>
Signed-off-by: Aaron Lu <aaron.lu@intel.com>
Acked-by: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
PM / Runtime: Asyncronous idle|suspend devices at system resume

Use the asyncronous runtime PM API when returning the runtime
reference for the device after the system resume is completed.

By using the asyncronous runtime PM API we don't have to wait
for each an every device to become idle|suspended. Instead we
can move on and handle the next device in queue.

Signed-off-by: Ulf Hansson <ulf.hansson@linaro.org>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
PM / Runtime: Asyncronous idle|suspend parent devices at removal

For irq safe devices return the runtime reference for the parent
by using the asyncronous runtime PM API. Thus we don't have to
wait for it to become idle|suspended. Instead we can move on and
handle the next device in queue.

Signed-off-by: Ulf Hansson <ulf.hansson@linaro.org>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
PM / Runtime: Improve prepare handling at system suspend for genpd

When genpd prepares for a system suspend it will fetch a runtime
reference for the device. When returning it we now use the
asyncronous runtime PM API. Thus we don't have to wait for the
device to become idle|suspended before we move on and handle the
next device in queue.

Signed-off-by: Ulf Hansson <ulf.hansson@linaro.org>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
block: recursive merge requests

In a workload, thread 1 accesses a, a+2, ..., thread 2 accesses a+1, a+3,....
When the requests are flushed to queue, a and a+1 are merged to (a, a+1), a+2
and a+3 too to (a+2, a+3), but (a, a+1) and (a+2, a+3) aren't merged.

If we do recursive merge for such interleave access, some workloads throughput
get improvement. A recent worload I'm checking on is swap, below change
boostes the throughput around 5% ~ 10%.

Signed-off-by: Shaohua Li <shli@fusionio.com>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
block: add a flag to identify PM request

Add a flag REQ_PM to identify the request is PM related, such requests
will not change the device request queue's runtime status. It is
intended to be used in driver's runtime PM callback, so that driver can
perform some IO to the device there with the queue's runtime status
unaffected. e.g. in SCSI disk's runtime suspend callback, the disk will
be put into stopped power state, and this require sending a command to
the device. Such command processing should not change the disk's runtime
status.

Signed-off-by: Lin Ming <ming.m.lin@intel.com>
Signed-off-by: Aaron Lu <aaron.lu@intel.com>
Acked-by: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
Bluetooth: Many fixes.

Bluetooth: Resolved a race condition

Due to simultaneous disconnects from HCI and SCO
this race condtion arrives. While doing SCO disconnect
a null pointer check for HCI connection should be present
to avoid any crash due to this condtion.

CRs-Fixed: 415887
Change-Id: I23f0a7a256e267650db0abc2fc510b964b64c50c
Signed-off-by: Nitin Srivastava <nitinsr@codeaurora.org>
Signed-off-by: Mallikarjuna GB <gbmalli@codeaurora.org>
Bluetooth: Support for Remote name request cancel command

Add support for remote name request cancel command in mgmtops
plugin.

Change-Id: If8bec8b457461f7bca90af940d2473b810677322
CRs-fixed: 414884
Signed-off-by: Ram Mohan Korukonda <rkorukon@codeaurora.org>
Signed-off-by: Mallikarjuna GB <gbmalli@codeaurora.org>
Bluetooth: Handle pairing cancel req for LE device

When pairing is cancelled during the pass key request UI pop
up, call pairing complete after sending SMP_CMD_PAIRING_FAIL
which would clean up all the pairing callbacks and send
notification to the above layers.

Change-Id: I0d3e9bdc19dc2fcae280d3c70ddea976ecb218c7
Signed-off-by: Archana Ramachandran <archanar@codeaurora.org>
CRs-fixed: 430016
Signed-off-by: Sunny Kapdi <sunnyk@codeaurora.org>
Signed-off-by: Mallikarjuna GB <gbmalli@codeaurora.org>
Revert "Bluetooth: Initiate dedicated bonding if pin/key missing on remote device"

Change has to be reverted to address one user interaction case,
in the process of addressing one issue it made mandate to have
user interactions in some BT scenarios, the issue is fixed via
f8fffe8423933433c30dda4f9a92afc71e8def21 and it addressees all
the user scenarios properly.

More details on this issue is provided in CR: 413132 analysis
section in the prism.

This reverts commit 45df0f99094aefc2564951495ab0005a18d62de3.

Change-Id: I56611cb2646789c71f4012e906a7bbada1236c00
Signed-off-by: Bhasker Neti <bneti@codeaurora.org>
Signed-off-by: Mallikarjuna GB <gbmalli@codeaurora.org>
Bluetooth: Avoid a case where sleep is getting called in soft irq context

While turning off BT, sleep is getting called in the soft isr context
from work queue which is queued from a code section guarded under the
bh lock,
To resolve this released the bh lock before queing the work, as it wont
impact any BT functionality.

CRs-fixed: 405917
Change-Id: I1b872d724b4d0d384cc5314e0f493facd9829a54
Signed-off-by: Bhasker Neti <bneti@codeaurora.org>
Signed-off-by: Mallikarjuna GB <gbmalli@codeaurora.org>
Bluetooth:Show bonding dialog if neither side requires no bonding

If the bonded remote device is removed from the list of paired
devices in the DUT, it is still possible to connect to the DUT
from the remote device without any user confirmation.

CRs-fixed: 413132
Change-Id: Iea3e4cf41e5403c3e304ca5f82cf42266be35b79
Signed-off-by: Bhasker Neti <bneti@codeaurora.org>
Signed-off-by: Mallikarjuna GB <gbmalli@codeaurora.org>
Bluetooth: Fixes FindMe Target L2CAP channel issue

When whitelist APIs are used for establishing LE connection
between the phone and remote LE device, few times
ATT requests like Read by Group Type request are received by
the phone from the remote device before the L2CAP channel has
been set up completely. Hence the LE server in the phone
sends a "Request not supported" error response since
the L2CAP channel has not yet been created. This fix checks
the state of the L2CAP channel after sleeping for a while
and sends the ATT request to be processed by the upper layers
when the L2CAP channel is up.

CRs-fixed: 415648

Change-Id: Ifbaf75fe612195b3c6ce49629106cac09dd0a437
Signed-off-by: Subramanian Srinivasan <subrsrin@codeaurora.org>
Signed-off-by: Mallikarjuna GB <gbmalli@codeaurora.org>
Bluetooth: Update pending_sec_level on auth update.

Based on the user requirement for auth type, update even
the pending security level. This will make sure the authentication
requirement matches the action at kernel space on connection
establishment.

CRs-Fixed: 385463
Change-Id: I94c7e621c105bb2180e6e722cc8cca17869ff2e5
Signed-off-by: Srinivas Krovvidi <skrovvid@codeaurora.org>
Signed-off-by: Mallikarjuna GB <gbmalli@codeaurora.org>
bluetooth: LE conn whitelist implementation

Add support to create connection to LE devices using
whitelist. With this, the Controller can try to connect
to multiple devices at the same time. The following
interfaces are added.
1. Add/Remove device from whitelist
2. Clear all the devices from whitelist
3. Create Connection to devices from whitelist
4. Cancel create connection to whitelist devices

CRs-fixed: 388980
Change-Id: I3900c71255e754f80bb2873ae19a41b94cca76c3
Signed-off-by: Sunny Kapdi <sunnyk@codeaurora.org>
(cherry picked from commit 93bef895b01b79f49af60ba1394c9c3f6e563212)
(cherry picked from commit 377ee2bf1fc37bcbeae872661646bdd6a5f8da31)
Bluetooth: Fix for supervision timeout must be 6X connection interval

Added a new function to verify whether the LE Connection Update
parameters are valid instaed of verifying all the LE Connection
parameters since only update parameters are set in the Connection
Update Request.

CRs-Fixed: 387146
Change-Id: I9fe6b51e44e2793f3945613fdfde3a039804746f
Signed-off-by: Archana Ramachandran <archanar@codeaurora.org>
(cherry picked from commit 95319af0612d58788279748f586cc57221c3443e)
Bluetooth: Send Disconnection reason to Bluez

Send device disconnection reason to bluez on receiving the
diconnection complete event so that low energy profiles
such as proximity can decide to reconnect if the reason
is link loss.

CRs-Fixed: 378240
Signed-off-by: Archana Ramachandran <archanar@codeaurora.org>
(cherry picked from commit da09d26a75ee1c7c1911dcfbe0128fd09f6631f4)

Change-Id: Iab1fede47f44342d87be6c3c5aa7590754fd950c
Signed-off-by: Sudhir Sharma <sudsha@codeaurora.org>
Bluetooth: Validate hci conn validity before refering wakelock.

Found in a rare case there is possibility that remote device
sent disconnect on a connection and DUT is trying send data
on the same. In that case accessing some released wakelock
is causing issue. The current changes are to use locking
mechanism to validate the connection before acting on the
wake lock.

CRs-Fixed: 394651
Change-Id: I6a4188a7d0d05a8cfbe66d3680473d549157917a
Signed-off-by: Srinivas Krovvidi <skrovvid@codeaurora.org>
(cherry picked from commit 6aadc41fcbd28dc3899a4b5d098e5f316588a029)

Signed-off-by: Sudhir Sharma <sudsha@codeaurora.org>
Bluetooth: Check for both SCO and ESCO types in hci_connect API.

In hci_connect API there is check for existing link, before
connect operation in order to avoid queuing connect if connection
already exist. This check for Synchronous connections is not
validating for ESCO and SCO connection types which are possible
synchronous connections.The current change takes care of verifying
both before proceeding to add a new connection.

Change-Id: I9018e0938bcd222bb6d80944e1b113e07227b066
Signed-off-by: Srinivas Krovvidi <skrovvid@codeaurora.org>
(cherry picked from commit 645f4d465ba131c87a99fdebcef5e597181b33c8)

Signed-off-by: Sudhir Sharma <sudsha@codeaurora.org>