diff options
author | Josh Gao | 2018-04-03 16:37:11 -0500 |
---|---|---|
committer | Josh Gao | 2018-05-23 13:26:04 -0500 |
commit | 7c738cdb53061f89605abc8243236a2bd783eeec (patch) | |
tree | 2d39f1b96b8f759d667e07bc2e6fbdca8f23390c | |
parent | 9da1a9118bbbff1d8dab8b15449d23e6e512f9e3 (diff) | |
download | platform-system-core-7c738cdb53061f89605abc8243236a2bd783eeec.tar.gz platform-system-core-7c738cdb53061f89605abc8243236a2bd783eeec.tar.xz platform-system-core-7c738cdb53061f89605abc8243236a2bd783eeec.zip |
adb: add IOVector.
An IOVector is a collection of immutable reference counted blocks which
can have its head detached at an arbitrary index. This is extremely
useful for implementing packet-framed protocols like adb on top of a
stream protocol like TCP: a stream reader can read blocks, append them
to the end of the IOVector, and then pull packets off of the front.
This also lends itself naturally towards scatter/gather I/O, which will
enable us to read data from disk and send it across the wire with a
theoretical minimum number of copies in USB, and one extra copy over
TCP.
Since this is basically a generalization of std::deque<Range>, delete
Range and replace its uses with IOVector.
Test: adb_test
Test: wine adb_test.exe
Change-Id: I06561ad0bb25a3a51b378b61d257b5b04b41d9c4
-rw-r--r-- | adb/Android.bp | 1 | ||||
-rw-r--r-- | adb/socket.h | 2 | ||||
-rw-r--r-- | adb/sockets.cpp | 20 | ||||
-rw-r--r-- | adb/types.h | 209 | ||||
-rw-r--r-- | adb/types_test.cpp | 119 |
5 files changed, 322 insertions, 29 deletions
diff --git a/adb/Android.bp b/adb/Android.bp index 99de54e1c..1f41e4f3f 100644 --- a/adb/Android.bp +++ b/adb/Android.bp | |||
@@ -122,6 +122,7 @@ libadb_test_srcs = [ | |||
122 | "sysdeps_test.cpp", | 122 | "sysdeps_test.cpp", |
123 | "sysdeps/stat_test.cpp", | 123 | "sysdeps/stat_test.cpp", |
124 | "transport_test.cpp", | 124 | "transport_test.cpp", |
125 | "types_test.cpp", | ||
125 | ] | 126 | ] |
126 | 127 | ||
127 | cc_library_host_static { | 128 | cc_library_host_static { |
diff --git a/adb/socket.h b/adb/socket.h index 27e5b0534..0905aab30 100644 --- a/adb/socket.h +++ b/adb/socket.h | |||
@@ -62,7 +62,7 @@ struct asocket { | |||
62 | int fd = -1; | 62 | int fd = -1; |
63 | 63 | ||
64 | // queue of data waiting to be written | 64 | // queue of data waiting to be written |
65 | std::deque<Range> packet_queue; | 65 | IOVector packet_queue; |
66 | 66 | ||
67 | std::string smart_socket_data; | 67 | std::string smart_socket_data; |
68 | 68 | ||
diff --git a/adb/sockets.cpp b/adb/sockets.cpp index 9a6dcbec5..de3215dc4 100644 --- a/adb/sockets.cpp +++ b/adb/sockets.cpp | |||
@@ -113,14 +113,14 @@ enum class SocketFlushResult { | |||
113 | }; | 113 | }; |
114 | 114 | ||
115 | static SocketFlushResult local_socket_flush_incoming(asocket* s) { | 115 | static SocketFlushResult local_socket_flush_incoming(asocket* s) { |
116 | while (!s->packet_queue.empty()) { | 116 | if (!s->packet_queue.empty()) { |
117 | Range& r = s->packet_queue.front(); | 117 | std::vector<adb_iovec> iov = s->packet_queue.iovecs(); |
118 | 118 | ssize_t rc = adb_writev(s->fd, iov.data(), iov.size()); | |
119 | int rc = adb_write(s->fd, r.data(), r.size()); | 119 | if (rc > 0 && static_cast<size_t>(rc) == s->packet_queue.size()) { |
120 | if (rc == static_cast<int>(r.size())) { | 120 | s->packet_queue.clear(); |
121 | s->packet_queue.pop_front(); | ||
122 | } else if (rc > 0) { | 121 | } else if (rc > 0) { |
123 | r.drop_front(rc); | 122 | // TODO: Implement a faster drop_front? |
123 | s->packet_queue.take_front(rc); | ||
124 | fdevent_add(s->fde, FDE_WRITE); | 124 | fdevent_add(s->fde, FDE_WRITE); |
125 | return SocketFlushResult::TryAgain; | 125 | return SocketFlushResult::TryAgain; |
126 | } else if (rc == -1 && errno == EAGAIN) { | 126 | } else if (rc == -1 && errno == EAGAIN) { |
@@ -130,7 +130,6 @@ static SocketFlushResult local_socket_flush_incoming(asocket* s) { | |||
130 | // We failed to write, but it's possible that we can still read from the socket. | 130 | // We failed to write, but it's possible that we can still read from the socket. |
131 | // Give that a try before giving up. | 131 | // Give that a try before giving up. |
132 | s->has_write_error = true; | 132 | s->has_write_error = true; |
133 | break; | ||
134 | } | 133 | } |
135 | } | 134 | } |
136 | 135 | ||
@@ -217,8 +216,7 @@ static bool local_socket_flush_outgoing(asocket* s) { | |||
217 | static int local_socket_enqueue(asocket* s, apacket::payload_type data) { | 216 | static int local_socket_enqueue(asocket* s, apacket::payload_type data) { |
218 | D("LS(%d): enqueue %zu", s->id, data.size()); | 217 | D("LS(%d): enqueue %zu", s->id, data.size()); |
219 | 218 | ||
220 | Range r(std::move(data)); | 219 | s->packet_queue.append(std::move(data)); |
221 | s->packet_queue.push_back(std::move(r)); | ||
222 | switch (local_socket_flush_incoming(s)) { | 220 | switch (local_socket_flush_incoming(s)) { |
223 | case SocketFlushResult::Destroyed: | 221 | case SocketFlushResult::Destroyed: |
224 | return -1; | 222 | return -1; |
@@ -622,7 +620,7 @@ static int smart_socket_enqueue(asocket* s, apacket::payload_type data) { | |||
622 | D("SS(%d): enqueue %zu", s->id, data.size()); | 620 | D("SS(%d): enqueue %zu", s->id, data.size()); |
623 | 621 | ||
624 | if (s->smart_socket_data.empty()) { | 622 | if (s->smart_socket_data.empty()) { |
625 | // TODO: Make this a BlockChain? | 623 | // TODO: Make this an IOVector? |
626 | s->smart_socket_data.assign(data.begin(), data.end()); | 624 | s->smart_socket_data.assign(data.begin(), data.end()); |
627 | } else { | 625 | } else { |
628 | std::copy(data.begin(), data.end(), std::back_inserter(s->smart_socket_data)); | 626 | std::copy(data.begin(), data.end(), std::back_inserter(s->smart_socket_data)); |
diff --git a/adb/types.h b/adb/types.h index dd3e06390..c6b3f0703 100644 --- a/adb/types.h +++ b/adb/types.h | |||
@@ -17,11 +17,15 @@ | |||
17 | #pragma once | 17 | #pragma once |
18 | 18 | ||
19 | #include <algorithm> | 19 | #include <algorithm> |
20 | #include <deque> | ||
21 | #include <type_traits> | ||
20 | #include <utility> | 22 | #include <utility> |
23 | #include <vector> | ||
21 | 24 | ||
22 | #include <android-base/logging.h> | 25 | #include <android-base/logging.h> |
23 | 26 | ||
24 | #include "sysdeps/memory.h" | 27 | #include "sysdeps/memory.h" |
28 | #include "sysdeps/uio.h" | ||
25 | 29 | ||
26 | // Essentially std::vector<char>, except without zero initialization or reallocation. | 30 | // Essentially std::vector<char>, except without zero initialization or reallocation. |
27 | struct Block { | 31 | struct Block { |
@@ -130,34 +134,205 @@ struct apacket { | |||
130 | payload_type payload; | 134 | payload_type payload; |
131 | }; | 135 | }; |
132 | 136 | ||
133 | struct Range { | 137 | struct IOVector { |
134 | explicit Range(apacket::payload_type data) : data_(std::move(data)) {} | 138 | using value_type = char; |
139 | using block_type = Block; | ||
140 | using size_type = size_t; | ||
135 | 141 | ||
136 | Range(const Range& copy) = delete; | 142 | IOVector() {} |
137 | Range& operator=(const Range& copy) = delete; | ||
138 | 143 | ||
139 | Range(Range&& move) = default; | 144 | explicit IOVector(std::unique_ptr<block_type> block) { |
140 | Range& operator=(Range&& move) = default; | 145 | append(std::move(block)); |
146 | } | ||
147 | |||
148 | IOVector(const IOVector& copy) = delete; | ||
149 | IOVector(IOVector&& move) : IOVector() { | ||
150 | *this = std::move(move); | ||
151 | } | ||
152 | |||
153 | IOVector& operator=(const IOVector& copy) = delete; | ||
154 | IOVector& operator=(IOVector&& move) { | ||
155 | chain_ = std::move(move.chain_); | ||
156 | chain_length_ = move.chain_length_; | ||
157 | begin_offset_ = move.begin_offset_; | ||
158 | end_offset_ = move.end_offset_; | ||
141 | 159 | ||
142 | size_t size() const { return data_.size() - begin_offset_ - end_offset_; }; | 160 | move.chain_.clear(); |
161 | move.chain_length_ = 0; | ||
162 | move.begin_offset_ = 0; | ||
163 | move.end_offset_ = 0; | ||
164 | |||
165 | return *this; | ||
166 | } | ||
167 | |||
168 | size_type size() const { return chain_length_ - begin_offset_ - end_offset_; } | ||
143 | bool empty() const { return size() == 0; } | 169 | bool empty() const { return size() == 0; } |
144 | 170 | ||
145 | void drop_front(size_t n) { | 171 | void clear() { |
146 | CHECK_GE(size(), n); | 172 | chain_length_ = 0; |
147 | begin_offset_ += n; | 173 | begin_offset_ = 0; |
174 | end_offset_ = 0; | ||
175 | chain_.clear(); | ||
176 | } | ||
177 | |||
178 | // Split the first |len| bytes out of this chain into its own. | ||
179 | IOVector take_front(size_type len) { | ||
180 | IOVector head; | ||
181 | |||
182 | if (len == 0) { | ||
183 | return head; | ||
184 | } | ||
185 | CHECK_GE(size(), len); | ||
186 | |||
187 | std::shared_ptr<const block_type> first_block = chain_.front(); | ||
188 | CHECK_GE(first_block->size(), begin_offset_); | ||
189 | head.append_shared(std::move(first_block)); | ||
190 | head.begin_offset_ = begin_offset_; | ||
191 | |||
192 | while (head.size() < len) { | ||
193 | pop_front_block(); | ||
194 | CHECK(!chain_.empty()); | ||
195 | |||
196 | head.append_shared(chain_.front()); | ||
197 | } | ||
198 | |||
199 | if (head.size() == len) { | ||
200 | // Head takes full ownership of the last block it took. | ||
201 | head.end_offset_ = 0; | ||
202 | begin_offset_ = 0; | ||
203 | pop_front_block(); | ||
204 | } else { | ||
205 | // Head takes partial ownership of the last block it took. | ||
206 | size_t bytes_taken = head.size() - len; | ||
207 | head.end_offset_ = bytes_taken; | ||
208 | CHECK_GE(chain_.front()->size(), bytes_taken); | ||
209 | begin_offset_ = chain_.front()->size() - bytes_taken; | ||
210 | } | ||
211 | |||
212 | return head; | ||
213 | } | ||
214 | |||
215 | // Add a nonempty block to the chain. | ||
216 | // The end of the chain must be a complete block (i.e. end_offset_ == 0). | ||
217 | void append(std::unique_ptr<const block_type> block) { | ||
218 | CHECK_NE(0ULL, block->size()); | ||
219 | CHECK_EQ(0ULL, end_offset_); | ||
220 | chain_length_ += block->size(); | ||
221 | chain_.emplace_back(std::move(block)); | ||
222 | } | ||
223 | |||
224 | void append(block_type&& block) { append(std::make_unique<block_type>(std::move(block))); } | ||
225 | |||
226 | void trim_front() { | ||
227 | if (begin_offset_ == 0) { | ||
228 | return; | ||
229 | } | ||
230 | |||
231 | const block_type* first_block = chain_.front().get(); | ||
232 | auto copy = std::make_unique<block_type>(first_block->size() - begin_offset_); | ||
233 | memcpy(copy->data(), first_block->data() + begin_offset_, copy->size()); | ||
234 | chain_.front() = std::move(copy); | ||
235 | |||
236 | chain_length_ -= begin_offset_; | ||
237 | begin_offset_ = 0; | ||
238 | } | ||
239 | |||
240 | private: | ||
241 | // append, except takes a shared_ptr. | ||
242 | // Private to prevent exterior mutation of blocks. | ||
243 | void append_shared(std::shared_ptr<const block_type> block) { | ||
244 | CHECK_NE(0ULL, block->size()); | ||
245 | CHECK_EQ(0ULL, end_offset_); | ||
246 | chain_length_ += block->size(); | ||
247 | chain_.emplace_back(std::move(block)); | ||
248 | } | ||
249 | |||
250 | // Drop the front block from the chain, and update chain_length_ appropriately. | ||
251 | void pop_front_block() { | ||
252 | chain_length_ -= chain_.front()->size(); | ||
253 | begin_offset_ = 0; | ||
254 | chain_.pop_front(); | ||
255 | } | ||
256 | |||
257 | // Iterate over the blocks with a callback with an operator()(const char*, size_t). | ||
258 | template <typename Fn> | ||
259 | void iterate_blocks(Fn&& callback) const { | ||
260 | if (chain_.size() == 0) { | ||
261 | return; | ||
262 | } | ||
263 | |||
264 | for (size_t i = 0; i < chain_.size(); ++i) { | ||
265 | const std::shared_ptr<const block_type>& block = chain_.at(i); | ||
266 | const char* begin = block->data(); | ||
267 | size_t length = block->size(); | ||
268 | |||
269 | // Note that both of these conditions can be true if there's only one block. | ||
270 | if (i == 0) { | ||
271 | CHECK_GE(block->size(), begin_offset_); | ||
272 | begin += begin_offset_; | ||
273 | length -= begin_offset_; | ||
274 | } | ||
275 | |||
276 | if (i == chain_.size() - 1) { | ||
277 | CHECK_GE(length, end_offset_); | ||
278 | length -= end_offset_; | ||
279 | } | ||
280 | |||
281 | callback(begin, length); | ||
282 | } | ||
148 | } | 283 | } |
149 | 284 | ||
150 | void drop_end(size_t n) { | 285 | public: |
151 | CHECK_GE(size(), n); | 286 | // Copy all of the blocks into a single block. |
152 | end_offset_ += n; | 287 | template <typename CollectionType = block_type> |
288 | CollectionType coalesce() const { | ||
289 | CollectionType result; | ||
290 | if (size() == 0) { | ||
291 | return result; | ||
292 | } | ||
293 | |||
294 | result.resize(size()); | ||
295 | |||
296 | size_t offset = 0; | ||
297 | iterate_blocks([&offset, &result](const char* data, size_t len) { | ||
298 | memcpy(&result[offset], data, len); | ||
299 | offset += len; | ||
300 | }); | ||
301 | |||
302 | return result; | ||
153 | } | 303 | } |
154 | 304 | ||
155 | char* data() { return &data_[0] + begin_offset_; } | 305 | template <typename FunctionType> |
306 | auto coalesced(FunctionType&& f) const -> | ||
307 | typename std::result_of<FunctionType(const char*, size_t)>::type { | ||
308 | if (chain_.size() == 1) { | ||
309 | // If we only have one block, we can use it directly. | ||
310 | return f(chain_.front()->data() + begin_offset_, size()); | ||
311 | } else { | ||
312 | // Otherwise, copy to a single block. | ||
313 | auto data = coalesce(); | ||
314 | return f(data.data(), data.size()); | ||
315 | } | ||
316 | } | ||
156 | 317 | ||
157 | apacket::payload_type::iterator begin() { return data_.begin() + begin_offset_; } | 318 | // Get a list of iovecs that can be used to write out all of the blocks. |
158 | apacket::payload_type::iterator end() { return data_.end() - end_offset_; } | 319 | std::vector<adb_iovec> iovecs() const { |
320 | std::vector<adb_iovec> result; | ||
321 | iterate_blocks([&result](const char* data, size_t len) { | ||
322 | adb_iovec iov; | ||
323 | iov.iov_base = const_cast<char*>(data); | ||
324 | iov.iov_len = len; | ||
325 | result.emplace_back(iov); | ||
326 | }); | ||
327 | |||
328 | return result; | ||
329 | } | ||
330 | |||
331 | private: | ||
332 | // Total length of all of the blocks in the chain. | ||
333 | size_t chain_length_ = 0; | ||
159 | 334 | ||
160 | apacket::payload_type data_; | ||
161 | size_t begin_offset_ = 0; | 335 | size_t begin_offset_ = 0; |
162 | size_t end_offset_ = 0; | 336 | size_t end_offset_ = 0; |
337 | std::deque<std::shared_ptr<const block_type>> chain_; | ||
163 | }; | 338 | }; |
diff --git a/adb/types_test.cpp b/adb/types_test.cpp new file mode 100644 index 000000000..31ab90af3 --- /dev/null +++ b/adb/types_test.cpp | |||
@@ -0,0 +1,119 @@ | |||
1 | /* | ||
2 | * Copyright (C) 2018 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 | #include <gtest/gtest.h> | ||
18 | |||
19 | #include "sysdeps/memory.h" | ||
20 | #include "types.h" | ||
21 | |||
22 | static std::unique_ptr<IOVector::block_type> create_block(const std::string& string) { | ||
23 | return std::make_unique<IOVector::block_type>(string.begin(), string.end()); | ||
24 | } | ||
25 | |||
26 | static std::unique_ptr<IOVector::block_type> create_block(char value, size_t len) { | ||
27 | auto block = std::make_unique<IOVector::block_type>(); | ||
28 | block->resize(len); | ||
29 | memset(&(*block)[0], value, len); | ||
30 | return block; | ||
31 | } | ||
32 | |||
33 | template <typename T> | ||
34 | static std::unique_ptr<IOVector::block_type> copy_block(T&& block) { | ||
35 | auto copy = std::make_unique<IOVector::block_type>(); | ||
36 | copy->assign(block->begin(), block->end()); | ||
37 | return copy; | ||
38 | } | ||
39 | |||
40 | TEST(IOVector, empty) { | ||
41 | // Empty IOVector. | ||
42 | IOVector bc; | ||
43 | CHECK_EQ(0ULL, bc.coalesce().size()); | ||
44 | } | ||
45 | |||
46 | TEST(IOVector, single_block) { | ||
47 | // A single block. | ||
48 | auto block = create_block('x', 100); | ||
49 | IOVector bc; | ||
50 | bc.append(copy_block(block)); | ||
51 | ASSERT_EQ(100ULL, bc.size()); | ||
52 | auto coalesced = bc.coalesce(); | ||
53 | ASSERT_EQ(*block, coalesced); | ||
54 | } | ||
55 | |||
56 | TEST(IOVector, single_block_split) { | ||
57 | // One block split. | ||
58 | IOVector bc; | ||
59 | bc.append(create_block("foobar")); | ||
60 | IOVector foo = bc.take_front(3); | ||
61 | ASSERT_EQ(3ULL, foo.size()); | ||
62 | ASSERT_EQ(3ULL, bc.size()); | ||
63 | ASSERT_EQ(*create_block("foo"), foo.coalesce()); | ||
64 | ASSERT_EQ(*create_block("bar"), bc.coalesce()); | ||
65 | } | ||
66 | |||
67 | TEST(IOVector, aligned_split) { | ||
68 | IOVector bc; | ||
69 | bc.append(create_block("foo")); | ||
70 | bc.append(create_block("bar")); | ||
71 | bc.append(create_block("baz")); | ||
72 | ASSERT_EQ(9ULL, bc.size()); | ||
73 | |||
74 | IOVector foo = bc.take_front(3); | ||
75 | ASSERT_EQ(3ULL, foo.size()); | ||
76 | ASSERT_EQ(*create_block("foo"), foo.coalesce()); | ||
77 | |||
78 | IOVector bar = bc.take_front(3); | ||
79 | ASSERT_EQ(3ULL, bar.size()); | ||
80 | ASSERT_EQ(*create_block("bar"), bar.coalesce()); | ||
81 | |||
82 | IOVector baz = bc.take_front(3); | ||
83 | ASSERT_EQ(3ULL, baz.size()); | ||
84 | ASSERT_EQ(*create_block("baz"), baz.coalesce()); | ||
85 | |||
86 | ASSERT_EQ(0ULL, bc.size()); | ||
87 | } | ||
88 | |||
89 | TEST(IOVector, misaligned_split) { | ||
90 | IOVector bc; | ||
91 | bc.append(create_block("foo")); | ||
92 | bc.append(create_block("bar")); | ||
93 | bc.append(create_block("baz")); | ||
94 | bc.append(create_block("qux")); | ||
95 | bc.append(create_block("quux")); | ||
96 | |||
97 | // Aligned left, misaligned right, across multiple blocks. | ||
98 | IOVector foob = bc.take_front(4); | ||
99 | ASSERT_EQ(4ULL, foob.size()); | ||
100 | ASSERT_EQ(*create_block("foob"), foob.coalesce()); | ||
101 | |||
102 | // Misaligned left, misaligned right, in one block. | ||
103 | IOVector a = bc.take_front(1); | ||
104 | ASSERT_EQ(1ULL, a.size()); | ||
105 | ASSERT_EQ(*create_block("a"), a.coalesce()); | ||
106 | |||
107 | // Misaligned left, misaligned right, across two blocks. | ||
108 | IOVector rba = bc.take_front(3); | ||
109 | ASSERT_EQ(3ULL, rba.size()); | ||
110 | ASSERT_EQ(*create_block("rba"), rba.coalesce()); | ||
111 | |||
112 | // Misaligned left, misaligned right, across three blocks. | ||
113 | IOVector zquxquu = bc.take_front(7); | ||
114 | ASSERT_EQ(7ULL, zquxquu.size()); | ||
115 | ASSERT_EQ(*create_block("zquxquu"), zquxquu.coalesce()); | ||
116 | |||
117 | ASSERT_EQ(1ULL, bc.size()); | ||
118 | ASSERT_EQ(*create_block("x"), bc.coalesce()); | ||
119 | } | ||