1//
2// Copyright (C) 2013 The Android Open Source Project
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8//      http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15//
16
17#ifndef SHILL_WIFI_SCAN_SESSION_H_
18#define SHILL_WIFI_SCAN_SESSION_H_
19
20#include <deque>
21#include <set>
22#include <vector>
23
24#include <base/callback.h>
25#include <base/macros.h>
26#include <base/memory/weak_ptr.h>
27#include <gtest/gtest_prod.h>  // for FRIEND_TEST
28#include <metrics/timer.h>
29
30#include "shill/net/byte_string.h"
31#include "shill/net/netlink_manager.h"
32#include "shill/wifi/wifi_provider.h"
33
34namespace shill {
35
36class EventDispatcher;
37class Metrics;
38class NetlinkManager;
39class NetlinkMessage;
40class Nl80211Message;
41
42// |ScanSession| sends requests to the kernel to scan WiFi frequencies for
43// access points.  The sequence for a single scan is as follows:
44//
45//   +-------------+                                                +--------+
46//   | ScanSession |                                                | Kernel |
47//   +---+---------+                                                +-----+--+
48//       |--- NL80211_CMD_TRIGGER_SCAN ---------------------------------->|
49//       |<-- NL80211_CMD_TRIGGER_SCAN (broadcast) -----------------------|
50//       |<-- NL80211_CMD_NEW_SCAN_RESULTS (broadcast) -------------------|
51//       |--- NL80211_CMD_GET_SCAN -------------------------------------->|
52//       |<-- NL80211_CMD_NEW_SCAN_RESULTS (reply, unicast, NLM_F_MULTI) -|
53//       |<-- NL80211_CMD_NEW_SCAN_RESULTS (reply, unicast, NLM_F_MULTI) -|
54//       |                               ...                              |
55//       |<-- NL80211_CMD_NEW_SCAN_RESULTS (reply, unicast, NLM_F_MULTI) -|
56//       |                                                                |
57//
58// Scanning WiFi frequencies for access points takes a long time (on the order
59// of 100ms per frequency and the kernel doesn't return the result until the
60// answers are ready for all the frequencies in the batch).  Given this,
61// scanning all frequencies in one batch takes a very long time.
62//
63// A ScanSession is used to distribute a scan across multiple requests (hoping
64// that a successful connection will result from an early request thereby
65// obviating the need for the remainder of the scan).  A ScanSession can be
66// used as follows (note, this is shown as synchronous code for clarity
67// but it really should be implemented as asynchronous code):
68//
69// ScanSession::FractionList scan_fractions;
70// scan_fractions.push_back(<some value>);
71// ...
72// scan_fractions.push_back(<some value>);
73// ScanSession scan_session(netlink_manager_, dispatcher(),
74//                          frequencies_seen_ever, all_scan_frequencies_,
75//                          interface_index(), scan_fractions,
76//                          kMinScanFrequencies, kMaxScanFrequencies,
77//                          on_scan_failed);
78// while (scan_session.HasMoreFrequencies()) {
79//   scan_session.InitiateScan();
80//   // Wait for scan results.  In the current WiFi code, this means wait
81//   // until |WiFi::ScanDone| is called.
82// }
83
84class ScanSession {
85 public:
86  typedef base::Closure OnScanFailed;
87  typedef std::deque<float> FractionList;
88  // Used as a fraction in |FractionList| to indicate that future scans in
89  // this session should not be limited to a subset of the frequencies we've
90  // already seen.
91  static const float kAllFrequencies;
92
93  // Sets up a new progressive scan session.  Uses |netlink_manager| to send
94  // NL80211_CMD_TRIGGER_SCAN messages to the kernel (uses |dispatcher| to
95  // reissue those commands if a send request returns EBUSY).  Multiple scans
96  // for APs on wifi device |ifindex| are issued (one for each call to
97  // |InitiateScan|) on wifi frequencies taken from the union of unique
98  // frequencies in |previous_frequencies| and |available_frequencies| (most
99  // commonly seen frequencies before less commonly seen ones followed by
100  // never-before seen frequencies, the latter in an unspecified order).
101  //
102  // Each scan takes a greater percentile (described by the values in
103  // |fractions|) of the previously seen frequencies (but no less than
104  // |min_frequencies| and no more than |max_frequencies|).  After all
105  // previously seen frequencies have been requested, each |InitiateScan|
106  // scans the next |max_frequencies| until all |available_frequencies| have
107  // been exhausted.
108  //
109  // If a scan request to the kernel returns an error, |on_scan_failed| is
110  // called.  The caller can reissue the scan by calling |ReInitiateScan| or
111  // abort the scan session by deleting the |ScanSession| object.
112  ScanSession(NetlinkManager* netlink_manager,
113              EventDispatcher* dispatcher,
114              const WiFiProvider::FrequencyCountList& previous_frequencies,
115              const std::set<uint16_t>& available_frequencies,
116              uint32_t ifindex,
117              const FractionList& fractions,
118              size_t min_frequencies,
119              size_t max_frequencies,
120              OnScanFailed on_scan_failed,
121              Metrics* metrics);
122
123  virtual ~ScanSession();
124
125  // Returns true if |ScanSession| contains unscanned frequencies.
126  virtual bool HasMoreFrequencies() const;
127
128  // Adds an SSID to the list of things for which to scan.  Useful for hidden
129  // SSIDs.
130  virtual void AddSsid(const ByteString& ssid);
131
132  // Start a wifi scan of the next set of frequencies (derived from the
133  // constructor's parameters) after saving those frequencies for the potential
134  // need to reinitiate a scan.
135  virtual void InitiateScan();
136
137  // Re-issues the previous scan (i.e., it uses the same frequency list as the
138  // previous scan).  Other classes may use this when |on_scan_failed| is
139  // called.  Called by |OnTriggerScanResponse| when the previous attempt to do
140  // a scan fails.
141  void ReInitiateScan();
142
143 private:
144  friend class ScanSessionTest;
145  friend class WiFiObjectTest;  // OnTriggerScanResponse.
146  FRIEND_TEST(ScanSessionTest, EBusy);
147  FRIEND_TEST(ScanSessionTest, OnError);
148  FRIEND_TEST(ScanSessionTest, OnTriggerScanResponse);
149
150  // Milliseconds to wait before retrying a failed scan.
151  static const uint64_t kScanRetryDelayMilliseconds;
152  // Number of times to retry a failed scan before giving up and calling
153  // |on_scan_failed_|.
154  static const size_t kScanRetryCount;
155
156  // Assists with sorting the |previous_frequencies| passed to the
157  // constructor.
158  static bool CompareFrequencyCount(const WiFiProvider::FrequencyCount& first,
159                                    const WiFiProvider::FrequencyCount& second);
160
161  // |GetScanFrequencies| gets the next set of WiFi scan frequencies.  Returns
162  // at least |min_frequencies| (unless fewer frequencies remain from previous
163  // calls) and no more than |max_frequencies|.  Inside these constraints,
164  // |GetScanFrequencies| tries to return at least the number of frequencies
165  // required to reach the connection fraction |scan_fraction| out of the total
166  // number of previous connections.  For example, the first call requesting
167  // 33.3% will return the minimum number frequencies that add up to _at least_
168  // the 33.3rd percentile of frequencies to which we've successfully connected
169  // in the past.  The next call of 33.3% returns the minimum number of
170  // frequencies required so that the total of the frequencies returned are _at
171  // least_ the 66.6th percentile of the frequencies to which we've successfully
172  // connected.
173  //
174  // For example, say we've connected to 3 frequencies before:
175  //  freq a,count=10; freq b,count=5; freq c,count=5.
176  //
177  //  GetScanFrequencies(.50,2,10) // Returns a & b (|a| reaches %ile but |b| is
178  //                               // required to meet the minimum).
179  //  GetScanFrequencies(.51,2,10) // Returns c & 9 frequencies from the list
180  //                               // of frequencies to which we've never
181  //                               // connected.
182  virtual std::vector<uint16_t> GetScanFrequencies(float scan_fraction,
183                                                   size_t min_frequencies,
184                                                   size_t max_frequencies);
185
186  // Does the real work of initiating a scan by sending an
187  // NL80211_CMD_TRIGGER_SCAN message to the kernel and installing a handler for
188  // any response (which only happens in the error case).
189  void DoScan(const std::vector<uint16_t>& scan_frequencies);
190
191  // Handles any unicast response to NL80211_CMD_TRIGGER_SCAN (which is,
192  // likely, an error -- when things work, we get an
193  // NL80211_CMD_NEW_SCAN_RESULTS broadcast message).
194  void OnTriggerScanResponse(const Nl80211Message& message);
195  void OnTriggerScanErrorResponse(NetlinkManager::AuxilliaryMessageType type,
196                                  const NetlinkMessage* netlink_message);
197  void ReportEbusyTime(int log_level);
198
199  // Logs the results of the scan.
200  void ReportResults(int log_level);
201
202  base::WeakPtrFactory<ScanSession> weak_ptr_factory_;
203
204  NetlinkManager* netlink_manager_;
205  EventDispatcher* dispatcher_;
206
207  // List of frequencies, sorted by the number of successful connections for
208  // each frequency.
209  WiFiProvider::FrequencyCountList frequency_list_;
210  size_t total_connections_;
211  size_t total_connects_provided_;
212  float total_fraction_wanted_;
213  std::vector<uint16_t> current_scan_frequencies_;
214  uint32_t wifi_interface_index_;
215  std::set<ByteString, bool(*)(const ByteString&, const ByteString&)> ssids_;
216  FractionList fractions_;
217  size_t min_frequencies_;
218  size_t max_frequencies_;
219  OnScanFailed on_scan_failed_;
220  size_t scan_tries_left_;
221  bool found_error_;
222
223  // Statistics gathering.
224  size_t original_frequency_count_;
225  chromeos_metrics::Timer ebusy_timer_;
226  Metrics* metrics_;
227
228  DISALLOW_COPY_AND_ASSIGN(ScanSession);
229};
230
231}  // namespace shill.
232
233#endif  // SHILL_WIFI_SCAN_SESSION_H_
234