This is an automated email from the ASF dual-hosted git repository. masaori pushed a commit to branch master in repository https://git-dual.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push: new 16172a4 TS-3535: Experimental Support of HTTP/2 Stream Priority feature 16172a4 is described below commit 16172a4e79865d1201a51e85aeb72df8b0609986 Author: Masaori Koshiba <masa...@apache.org> AuthorDate: Fri Feb 12 16:07:10 2016 +0900 TS-3535: Experimental Support of HTTP/2 Stream Priority feature - Add a option to enable this feature ( disabled in default ). `proxy.config.http2.stream_priority_enabled` - Parse priority parameters of HEADERS and PRIORITY frame correctly. - Add Http2DependencyTree and tests using `lib/ts/PriorityQueue.h`. - Create a dependency tree when clients send HEADERS frame with priority parameters or PRIORITY frame. - Separate `Http2ConnectionState::send_data_frame()` into `Http2ConnectionState::send_a_data_frame()` and `Http2ConnectionState::send_data_frames()`. - Schedule DATA frames using the WFQ algorithm. This closes #632 --- .gitignore | 1 + doc/admin-guide/files/records.config.en.rst | 5 + mgmt/RecordsConfig.cc | 4 +- proxy/http2/HTTP2.cc | 12 +- proxy/http2/HTTP2.h | 16 +- proxy/http2/Http2ConnectionState.cc | 309 ++++++++++++++++++-------- proxy/http2/Http2ConnectionState.h | 22 +- proxy/http2/Http2DependencyTree.h | 308 ++++++++++++++++++++++++++ proxy/http2/Http2Stream.cc | 21 +- proxy/http2/Http2Stream.h | 7 + proxy/http2/Makefile.am | 15 +- proxy/http2/test_Http2DependencyTree.cc | 327 ++++++++++++++++++++++++++++ 12 files changed, 940 insertions(+), 107 deletions(-) diff --git a/.gitignore b/.gitignore index 61ec27d..601dcec 100644 --- a/.gitignore +++ b/.gitignore @@ -87,6 +87,7 @@ proxy/config/records.config.default proxy/config/storage.config.default proxy/hdrs/test_mime proxy/http2/test_Huffmancode +proxy/http2/test_Http2DependencyTree plugins/header_rewrite/header_rewrite_test plugins/experimental/esi/*_test diff --git a/doc/admin-guide/files/records.config.en.rst b/doc/admin-guide/files/records.config.en.rst index bc4f9d2..b2e6442 100644 --- a/doc/admin-guide/files/records.config.en.rst +++ b/doc/admin-guide/files/records.config.en.rst @@ -3063,6 +3063,11 @@ HTTP/2 Configuration that the sender is prepared to accept blocks. The default value, which is the unsigned int maximum value in Traffic Server, implies unlimited size. +.. ts:cv:: CONFIG proxy.config.http2.stream_priority_enabled INT 0 + :reloadable: + + Enable the experimental HTTP/2 Stream Priority feature. + SPDY Configuration ================== diff --git a/mgmt/RecordsConfig.cc b/mgmt/RecordsConfig.cc index b500027..8d3e54b 100644 --- a/mgmt/RecordsConfig.cc +++ b/mgmt/RecordsConfig.cc @@ -1974,7 +1974,9 @@ static const RecordElement RecordsConfig[] = //# HTTP/2 global configuration. //# //############ - {RECT_CONFIG, "proxy.config.http2.enabled", RECD_INT, "0", RECU_RESTART_TM, RR_NULL, RECC_INT, "[0-1]", RECA_NULL} + {RECT_CONFIG, "proxy.config.http2.enabled", RECD_INT, "0", RECU_DYNAMIC, RR_NULL, RECC_INT, "[0-1]", RECA_NULL} + , + {RECT_CONFIG, "proxy.config.http2.stream_priority_enabled", RECD_INT, "0", RECU_DYNAMIC, RR_NULL, RECC_INT, "[0-1]", RECA_NULL} , {RECT_CONFIG, "proxy.config.http2.max_concurrent_streams_in", RECD_INT, "100", RECU_DYNAMIC, RR_NULL, RECC_STR, "^[0-9]+$", RECA_NULL} , diff --git a/proxy/http2/HTTP2.cc b/proxy/http2/HTTP2.cc index bcaad3b..4bee9ed 100644 --- a/proxy/http2/HTTP2.cc +++ b/proxy/http2/HTTP2.cc @@ -335,15 +335,19 @@ http2_parse_headers_parameter(IOVec iov, Http2HeadersParameter ¶ms) } bool -http2_parse_priority_parameter(IOVec iov, Http2Priority ¶ms) +http2_parse_priority_parameter(IOVec iov, Http2Priority &priority) { byte_pointer ptr(iov.iov_base); byte_addressable_value<uint32_t> dependency; memcpy_and_advance(dependency.bytes, ptr); - memcpy_and_advance(params.weight, ptr); - params.stream_dependency = ntohl(dependency.value); + priority.exclusive_flag = dependency.bytes[0] & 0x80; + + dependency.bytes[0] &= 0x7f; // Clear the highest bit for exclusive flag + priority.stream_dependency = ntohl(dependency.value); + + memcpy_and_advance(priority.weight, ptr); return true; } @@ -666,6 +670,7 @@ uint32_t Http2::max_concurrent_streams_in = 100; uint32_t Http2::min_concurrent_streams_in = 10; uint32_t Http2::max_active_streams_in = 0; bool Http2::throttling = false; +uint32_t Http2::stream_priority_enabled = 0; uint32_t Http2::initial_window_size = 1048576; uint32_t Http2::max_frame_size = 16384; uint32_t Http2::header_table_size = 4096; @@ -681,6 +686,7 @@ Http2::init() REC_EstablishStaticConfigInt32U(max_concurrent_streams_in, "proxy.config.http2.max_concurrent_streams_in"); REC_EstablishStaticConfigInt32U(min_concurrent_streams_in, "proxy.config.http2.min_concurrent_streams_in"); REC_EstablishStaticConfigInt32U(max_active_streams_in, "proxy.config.http2.max_active_streams_in"); + REC_EstablishStaticConfigInt32U(stream_priority_enabled, "proxy.config.http2.stream_priority_enabled"); REC_EstablishStaticConfigInt32U(initial_window_size, "proxy.config.http2.initial_window_size_in"); REC_EstablishStaticConfigInt32U(max_frame_size, "proxy.config.http2.max_frame_size"); REC_EstablishStaticConfigInt32U(header_table_size, "proxy.config.http2.header_table_size"); diff --git a/proxy/http2/HTTP2.h b/proxy/http2/HTTP2.h index 3cbb443..1fde5fc 100644 --- a/proxy/http2/HTTP2.h +++ b/proxy/http2/HTTP2.h @@ -60,6 +60,12 @@ const uint32_t HTTP2_MAX_FRAME_SIZE = 16384; const uint32_t HTTP2_HEADER_TABLE_SIZE = 4096; const uint32_t HTTP2_MAX_HEADER_LIST_SIZE = UINT_MAX; +// [RFC 7540] 5.3.5 Default Priorities +// The RFC says weight value is 1 to 256, but the value in TS is between 0 to 255 +// to use uint8_t. So the default weight is 16 minus 1. +const uint32_t HTTP2_PRIORITY_DEFAULT_STREAM_DEPENDENCY = 0; +const uint8_t HTTP2_PRIORITY_DEFAULT_WEIGHT = 15; + // Statistics enum { HTTP2_STAT_CURRENT_CLIENT_SESSION_COUNT, // Current # of active HTTP2 @@ -253,9 +259,14 @@ struct Http2SettingsParameter { // [RFC 7540] 6.3 PRIORITY Format struct Http2Priority { - Http2Priority() : stream_dependency(0), weight(15) {} - uint32_t stream_dependency; + Http2Priority() + : exclusive_flag(false), weight(HTTP2_PRIORITY_DEFAULT_WEIGHT), stream_dependency(HTTP2_PRIORITY_DEFAULT_STREAM_DEPENDENCY) + { + } + + bool exclusive_flag; uint8_t weight; + uint32_t stream_dependency; }; // [RFC 7540] 6.2 HEADERS Format @@ -348,6 +359,7 @@ public: static uint32_t min_concurrent_streams_in; static uint32_t max_active_streams_in; static bool throttling; + static uint32_t stream_priority_enabled; static uint32_t initial_window_size; static uint32_t max_frame_size; static uint32_t header_table_size; diff --git a/proxy/http2/Http2ConnectionState.cc b/proxy/http2/Http2ConnectionState.cc index da1f8d3..da294e4 100644 --- a/proxy/http2/Http2ConnectionState.cc +++ b/proxy/http2/Http2ConnectionState.cc @@ -192,6 +192,8 @@ rcv_headers_frame(Http2ConnectionState &cstate, const Http2Frame &frame) } Http2Stream *stream = NULL; + bool new_stream = false; + if (stream_id <= cstate.get_latest_stream_id()) { stream = cstate.find_stream(stream_id); if (stream == NULL || !stream->has_trailing_header()) { @@ -199,6 +201,7 @@ rcv_headers_frame(Http2ConnectionState &cstate, const Http2Frame &frame) } } else { // Create new stream + new_stream = true; stream = cstate.create_stream(stream_id); if (!stream) { return Http2Error(HTTP2_ERROR_CLASS_CONNECTION, HTTP2_ERROR_PROTOCOL_ERROR); @@ -239,7 +242,6 @@ rcv_headers_frame(Http2ConnectionState &cstate, const Http2Frame &frame) } // NOTE: Parse priority parameters if exists - // TODO: Currently priority is NOT supported. TS-3535 will fix this. if (frame.header().flags & HTTP2_FLAGS_HEADERS_PRIORITY) { uint8_t buf[HTTP2_PRIORITY_LEN] = {0}; @@ -256,6 +258,19 @@ rcv_headers_frame(Http2ConnectionState &cstate, const Http2Frame &frame) header_block_fragment_length -= HTTP2_PRIORITY_LEN; } + if (new_stream && Http2::stream_priority_enabled) { + DependencyTree::Node *node = cstate.dependency_tree->find(stream_id); + if (node != NULL) { + stream->priority_node = node; + } else { + DebugHttp2Stream(cstate.ua_session, stream_id, "PRIORITY - dep: %d, weight: %d, excl: %d", params.priority.stream_dependency, + params.priority.weight, params.priority.exclusive_flag); + + stream->priority_node = cstate.dependency_tree->add(params.priority.stream_dependency, stream_id, params.priority.weight, + params.priority.exclusive_flag, stream); + } + } + stream->header_blocks = static_cast<uint8_t *>(ats_malloc(header_block_fragment_length)); frame.reader()->memcpy(stream->header_blocks, header_block_fragment_length, header_block_fragment_offset); @@ -305,25 +320,59 @@ rcv_headers_frame(Http2ConnectionState &cstate, const Http2Frame &frame) return Http2Error(HTTP2_ERROR_CLASS_NONE); } +/* + * [RFC 7540] 6.3 PRIORITY + * + */ static Http2Error rcv_priority_frame(Http2ConnectionState &cstate, const Http2Frame &frame) { - DebugHttp2Stream(cstate.ua_session, frame.header().streamid, "Received PRIORITY frame"); + const Http2StreamId stream_id = frame.header().streamid; + const uint32_t payload_length = frame.header().length; + + DebugHttp2Stream(cstate.ua_session, stream_id, "Received PRIORITY frame"); // If a PRIORITY frame is received with a stream identifier of 0x0, the // recipient MUST respond with a connection error of type PROTOCOL_ERROR. - if (frame.header().streamid == 0) { + if (stream_id == 0) { return Http2Error(HTTP2_ERROR_CLASS_CONNECTION, HTTP2_ERROR_PROTOCOL_ERROR); } // A PRIORITY frame with a length other than 5 octets MUST be treated as // a stream error (Section 5.4.2) of type FRAME_SIZE_ERROR. - if (frame.header().length != HTTP2_PRIORITY_LEN) { + if (payload_length != HTTP2_PRIORITY_LEN) { return Http2Error(HTTP2_ERROR_CLASS_STREAM, HTTP2_ERROR_FRAME_SIZE_ERROR); } - // TODO Pick stream dependencies and weight - // Supporting PRIORITY is not essential so its temporarily ignored. + if (!Http2::stream_priority_enabled) { + return Http2Error(HTTP2_ERROR_CLASS_NONE); + } + + uint8_t buf[HTTP2_PRIORITY_LEN] = {0}; + frame.reader()->memcpy(buf, HTTP2_PRIORITY_LEN, 0); + + Http2Priority priority; + if (!http2_parse_priority_parameter(make_iovec(buf, HTTP2_PRIORITY_LEN), priority)) { + return Http2Error(HTTP2_ERROR_CLASS_CONNECTION, HTTP2_ERROR_PROTOCOL_ERROR); + } + + DebugHttp2Stream(cstate.ua_session, stream_id, "PRIORITY - dep: %d, weight: %d, excl: %d", priority.stream_dependency, + priority.weight, priority.exclusive_flag); + + DependencyTree::Node *node = cstate.dependency_tree->find(stream_id); + + if (node != NULL) { + // [RFC 7540] 5.3.3 Reprioritization + DebugHttp2Stream(cstate.ua_session, stream_id, "Reprioritize"); + cstate.dependency_tree->reprioritize(node, priority.stream_dependency, priority.exclusive_flag); + } else { + cstate.dependency_tree->add(priority.stream_dependency, stream_id, priority.weight, priority.exclusive_flag, NULL); + + Http2Stream *stream = cstate.find_stream(stream_id); + if (stream != NULL) { + stream->priority_node = node; + } + } return Http2Error(HTTP2_ERROR_CLASS_NONE); } @@ -536,30 +585,32 @@ rcv_window_update_frame(Http2ConnectionState &cstate, const Http2Frame &frame) { char buf[HTTP2_WINDOW_UPDATE_LEN]; uint32_t size; - const Http2StreamId sid = frame.header().streamid; + const Http2StreamId stream_id = frame.header().streamid; // A WINDOW_UPDATE frame with a length other than 4 octets MUST be // treated as a connection error of type FRAME_SIZE_ERROR. if (frame.header().length != HTTP2_WINDOW_UPDATE_LEN) { - DebugHttp2Stream(cstate.ua_session, sid, "Received WINDOW_UPDATE frame - length incorrect"); + DebugHttp2Stream(cstate.ua_session, stream_id, "Received WINDOW_UPDATE frame - length incorrect"); return Http2Error(HTTP2_ERROR_CLASS_CONNECTION, HTTP2_ERROR_FRAME_SIZE_ERROR); } - if (sid == 0) { - // Connection level window update - frame.reader()->memcpy(buf, sizeof(buf), 0); - http2_parse_window_update(make_iovec(buf, sizeof(buf)), size); - - DebugHttp2Stream(cstate.ua_session, sid, "Received WINDOW_UPDATE frame - updated to: %zd delta: %u", - (cstate.client_rwnd + size), size); + frame.reader()->memcpy(buf, sizeof(buf), 0); + http2_parse_window_update(make_iovec(buf, sizeof(buf)), size); - // A receiver MUST treat the receipt of a WINDOW_UPDATE frame with a - // connection - // flow control window increment of 0 as a connection error of type - // PROTOCOL_ERROR; - if (size == 0) { + // A receiver MUST treat the receipt of a WINDOW_UPDATE frame with a flow + // control window increment of 0 as a connection error of type PROTOCOL_ERROR; + if (size == 0) { + if (stream_id == 0) { return Http2Error(HTTP2_ERROR_CLASS_CONNECTION, HTTP2_ERROR_PROTOCOL_ERROR); + } else { + return Http2Error(HTTP2_ERROR_CLASS_STREAM, HTTP2_ERROR_PROTOCOL_ERROR); } + } + + if (stream_id == 0) { + // Connection level window update + DebugHttp2Stream(cstate.ua_session, stream_id, "Received WINDOW_UPDATE frame - updated to: %zd delta: %u", + (cstate.client_rwnd + size), size); // A sender MUST NOT allow a flow-control window to exceed 2^31-1 // octets. If a sender receives a WINDOW_UPDATE that causes a flow- @@ -576,29 +627,19 @@ rcv_window_update_frame(Http2ConnectionState &cstate, const Http2Frame &frame) cstate.restart_streams(); } else { // Stream level window update - Http2Stream *stream = cstate.find_stream(sid); + Http2Stream *stream = cstate.find_stream(stream_id); if (stream == NULL) { - if (sid <= cstate.get_latest_stream_id()) { + if (stream_id <= cstate.get_latest_stream_id()) { return Http2Error(HTTP2_ERROR_CLASS_NONE); } else { return Http2Error(HTTP2_ERROR_CLASS_CONNECTION, HTTP2_ERROR_PROTOCOL_ERROR); } } - frame.reader()->memcpy(buf, sizeof(buf), 0); - http2_parse_window_update(make_iovec(buf, sizeof(buf)), size); - - DebugHttp2Stream(cstate.ua_session, sid, "Received WINDOW_UPDATE frame - updated to: %zd delta: %u", + DebugHttp2Stream(cstate.ua_session, stream_id, "Received WINDOW_UPDATE frame - updated to: %zd delta: %u", (stream->client_rwnd + size), size); - // A receiver MUST treat the receipt of a WINDOW_UPDATE frame with an - // flow control window increment of 0 as a stream error of type - // PROTOCOL_ERROR; - if (size == 0) { - return Http2Error(HTTP2_ERROR_CLASS_STREAM, HTTP2_ERROR_PROTOCOL_ERROR); - } - // A sender MUST NOT allow a flow-control window to exceed 2^31-1 // octets. If a sender receives a WINDOW_UPDATE that causes a flow- // control window to exceed this maximum, it MUST terminate either the @@ -612,8 +653,9 @@ rcv_window_update_frame(Http2ConnectionState &cstate, const Http2Frame &frame) stream->client_rwnd += size; ssize_t wnd = min(cstate.client_rwnd, stream->client_rwnd); + if (stream->get_state() == HTTP2_STREAM_STATE_HALF_CLOSED_REMOTE && wnd > 0) { - cstate.send_data_frame(stream); + stream->send_response_body(); } } @@ -756,6 +798,14 @@ Http2ConnectionState::main_event_handler(int event, void *edata) return 0; } + case HTTP2_SESSION_EVENT_XMIT: { + SCOPED_MUTEX_LOCK(lock, this->mutex, this_ethread()); + send_data_frames_depends_on_priority(); + _scheduled = false; + + return 0; + } + // Parse received HTTP/2 frames case HTTP2_SESSION_EVENT_RECV: { const Http2Frame *frame = (Http2Frame *)edata; @@ -796,6 +846,7 @@ Http2ConnectionState::main_event_handler(int event, void *edata) return 0; } + default: DebugHttp2Con(ua_session, "unexpected event=%d edata=%p", event, edata); ink_release_assert(0); @@ -855,13 +906,12 @@ Http2ConnectionState::find_stream(Http2StreamId id) const void Http2ConnectionState::restart_streams() { - // Currently lookup retryable streams sequentially. - // TODO considering to stream weight and dependencies. Http2Stream *s = stream_list.head; + while (s) { Http2Stream *next = s->link.next; if (s->get_state() == HTTP2_STREAM_STATE_HALF_CLOSED_REMOTE && min(this->client_rwnd, s->client_rwnd) > 0) { - this->send_data_frame(s); + s->send_response_body(); } s = next; } @@ -876,6 +926,7 @@ Http2ConnectionState::cleanup_streams() this->delete_stream(s); s = next; } + client_streams_count = 0; if (!is_state_closed()) { ua_session->get_netvc()->add_to_keep_alive_queue(); @@ -885,6 +936,13 @@ Http2ConnectionState::cleanup_streams() void Http2ConnectionState::delete_stream(Http2Stream *stream) { + if (Http2::stream_priority_enabled) { + DependencyTree::Node *node = stream->priority_node; + if (node != NULL && node->active) { + dependency_tree->deactivate(node, 0); + } + } + stream_list.remove(stream); stream->initiating_close(); @@ -906,74 +964,139 @@ Http2ConnectionState::update_initial_rwnd(Http2WindowSize new_size) } void -Http2ConnectionState::send_data_frame(Http2Stream *stream) +Http2ConnectionState::schedule_stream(Http2Stream *stream) { - size_t buf_len = BUFFER_SIZE_FOR_INDEX(buffer_size_index[HTTP2_FRAME_TYPE_DATA]) - HTTP2_FRAME_HEADER_LEN; - uint8_t payload_buffer[buf_len]; + DebugHttp2Stream(ua_session, stream->get_id(), "Scheduled"); - if (stream->get_state() == HTTP2_STREAM_STATE_CLOSED) { + DependencyTree::Node *node = stream->priority_node; + ink_release_assert(node != NULL); + + SCOPED_MUTEX_LOCK(lock, this->mutex, this_ethread()); + dependency_tree->activate(node); + + if (!_scheduled) { + _scheduled = true; + + SET_HANDLER(&Http2ConnectionState::main_event_handler); + this_ethread()->schedule_imm_local((Continuation *)this, HTTP2_SESSION_EVENT_XMIT); + } +} + +void +Http2ConnectionState::send_data_frames_depends_on_priority() +{ + DependencyTree::Node *node = dependency_tree->top(); + + // No node to send or no connection level window left + if (node == NULL || client_rwnd <= 0) { return; } - for (;;) { - uint8_t flags = 0x00; + Http2Stream *stream = node->t; + ink_release_assert(stream != NULL); + DebugHttp2Stream(ua_session, stream->get_id(), "top node, point=%d", node->point); - size_t window_size = min(this->client_rwnd, stream->client_rwnd); - size_t send_size = min(buf_len, window_size); - size_t payload_length; - IOBufferReader *current_reader = stream->response_get_data_reader(); + size_t len = 0; + Http2SendADataFrameResult result = send_a_data_frame(stream, len); - // Are we at the end? - // If we break here, we never send the END_STREAM in the case of a - // early terminating OS. Ok if there is no body yet. Otherwise - // continue on to delete the stream - if (stream->is_body_done() && current_reader && !current_reader->is_read_avail_more_than(0)) { - Debug("http2_con", "End of Stream id=%d no more data and body done", stream->get_id()); - flags |= HTTP2_FLAGS_DATA_END_STREAM; - payload_length = 0; - } else { - // Select appropriate payload size - if (this->client_rwnd <= 0 || stream->client_rwnd <= 0) - break; - // Copy into the payload buffer. Seems like we should be able to skip this - // copy step - payload_length = current_reader ? current_reader->read(payload_buffer, send_size) : 0; - - if (payload_length == 0 && !stream->is_body_done()) { - break; - } + if (result != HTTP2_SEND_A_DATA_FRAME_NO_ERROR) { + // When no stream level window left, deactivate node once and wait window_update frame + dependency_tree->deactivate(node, len); + this_ethread()->schedule_imm_local((Continuation *)this, HTTP2_SESSION_EVENT_XMIT); + return; + } - // Update window size - this->client_rwnd -= payload_length; - stream->client_rwnd -= payload_length; + // No response body to send + if (len == 0 && !stream->is_body_done()) { + dependency_tree->deactivate(node, len); + this_ethread()->schedule_imm_local((Continuation *)this, HTTP2_SESSION_EVENT_XMIT); + return; + } - if (stream->is_body_done() && payload_length < send_size) { - flags |= HTTP2_FLAGS_DATA_END_STREAM; - } - } + if (stream->get_state() == HTTP2_STREAM_STATE_CLOSED) { + dependency_tree->deactivate(node, len); + delete_stream(stream); + } else { + dependency_tree->update(node, len); + } - // Create frame - DebugHttp2Stream(ua_session, stream->get_id(), "Send DATA frame - client window con: %zd stream: %zd payload: %zd", client_rwnd, - stream->client_rwnd, payload_length); - Http2Frame data(HTTP2_FRAME_TYPE_DATA, stream->get_id(), flags); - data.alloc(buffer_size_index[HTTP2_FRAME_TYPE_DATA]); - http2_write_data(payload_buffer, payload_length, data.write()); - data.finalize(payload_length); - - stream->update_sent_count(payload_length); - - // Change state to 'closed' if its end of DATAs. - if (flags & HTTP2_FLAGS_DATA_END_STREAM) { - DebugHttp2Stream(ua_session, stream->get_id(), "End of DATA frame"); - // Setting to the same state shouldn't be erroneous - stream->change_state(data.header().type, data.header().flags); - } + this_ethread()->schedule_imm_local((Continuation *)this, HTTP2_SESSION_EVENT_XMIT); +} - // xmit event - SCOPED_MUTEX_LOCK(lock, this->ua_session->mutex, this_ethread()); - this->ua_session->handleEvent(HTTP2_SESSION_EVENT_XMIT, &data); +Http2SendADataFrameResult +Http2ConnectionState::send_a_data_frame(Http2Stream *stream, size_t &payload_length) +{ + const ssize_t window_size = min(this->client_rwnd, stream->client_rwnd); + if (window_size <= 0) { + return HTTP2_SEND_A_DATA_FRAME_NO_WINDOW; + } + const size_t buf_len = BUFFER_SIZE_FOR_INDEX(buffer_size_index[HTTP2_FRAME_TYPE_DATA]) - HTTP2_FRAME_HEADER_LEN; + const size_t available_size = min(buf_len, static_cast<size_t>(window_size)); + + uint8_t flags = 0x00; + uint8_t payload_buffer[buf_len]; + IOBufferReader *current_reader = stream->response_get_data_reader(); + + SCOPED_MUTEX_LOCK(stream_lock, stream->mutex, this_ethread()); + + // Select appropriate payload length + if (current_reader && current_reader->is_read_avail_more_than(0)) { + // Copy into the payload buffer. Seems like we should be able to skip this copy step + payload_length = current_reader->read(payload_buffer, available_size); + } else { + payload_length = 0; + } + + // Are we at the end? + // If we return here, we never send the END_STREAM in the case of a early terminating OS. + // OK if there is no body yet. Otherwise continue on to send a DATA frame and delete the stream + if (!stream->is_body_done() && payload_length == 0) { + return HTTP2_SEND_A_DATA_FRAME_NO_PAYLOAD; + } + + if (stream->is_body_done() && payload_length < available_size) { + flags |= HTTP2_FLAGS_DATA_END_STREAM; + } + + // Update window size + this->client_rwnd -= payload_length; + stream->client_rwnd -= payload_length; + + // Create frame + DebugHttp2Stream(ua_session, stream->get_id(), "Send a DATA frame - client window con: %zd stream: %zd payload: %zd", client_rwnd, + stream->client_rwnd, payload_length); + + Http2Frame data(HTTP2_FRAME_TYPE_DATA, stream->get_id(), flags); + data.alloc(buffer_size_index[HTTP2_FRAME_TYPE_DATA]); + http2_write_data(payload_buffer, payload_length, data.write()); + data.finalize(payload_length); + + stream->update_sent_count(payload_length); + + // Change state to 'closed' if its end of DATAs. + if (flags & HTTP2_FLAGS_DATA_END_STREAM) { + DebugHttp2Stream(ua_session, stream->get_id(), "End of DATA frame"); + // Setting to the same state shouldn't be erroneous + stream->change_state(data.header().type, data.header().flags); + } + + // xmit event + SCOPED_MUTEX_LOCK(lock, this->ua_session->mutex, this_ethread()); + this->ua_session->handleEvent(HTTP2_SESSION_EVENT_XMIT, &data); + + return HTTP2_SEND_A_DATA_FRAME_NO_ERROR; +} + +void +Http2ConnectionState::send_data_frames(Http2Stream *stream) +{ + if (stream->get_state() == HTTP2_STREAM_STATE_CLOSED) { + return; + } - if (flags & HTTP2_FLAGS_DATA_END_STREAM) { + size_t len = 0; + while (send_a_data_frame(stream, len) == HTTP2_SEND_A_DATA_FRAME_NO_ERROR) { + if (stream->get_state() == HTTP2_STREAM_STATE_CLOSED) { // Delete a stream immediately // TODO its should not be deleted for a several time to handling // RST_STREAM and WINDOW_UPDATE. diff --git a/proxy/http2/Http2ConnectionState.h b/proxy/http2/Http2ConnectionState.h index c4dc5d5..584f0f8 100644 --- a/proxy/http2/Http2ConnectionState.h +++ b/proxy/http2/Http2ConnectionState.h @@ -27,9 +27,16 @@ #include "HTTP2.h" #include "HPACK.h" #include "Http2Stream.h" +#include "Http2DependencyTree.h" class Http2ClientSession; +enum Http2SendADataFrameResult { + HTTP2_SEND_A_DATA_FRAME_NO_ERROR = 0, + HTTP2_SEND_A_DATA_FRAME_NO_WINDOW = 1, + HTTP2_SEND_A_DATA_FRAME_NO_PAYLOAD = 2, +}; + class Http2ConnectionSettings { public: @@ -106,12 +113,14 @@ public: Http2ConnectionState() : Continuation(NULL), ua_session(NULL), + dependency_tree(NULL), client_rwnd(HTTP2_INITIAL_WINDOW_SIZE), server_rwnd(Http2::initial_window_size), stream_list(), latest_streamid(0), client_streams_count(0), - continued_stream_id(0) + continued_stream_id(0), + _scheduled(false) { SET_HANDLER(&Http2ConnectionState::main_event_handler); } @@ -119,6 +128,7 @@ public: Http2ClientSession *ua_session; HpackHandle *local_hpack_handle; HpackHandle *remote_hpack_handle; + DependencyTree *dependency_tree; // Settings. Http2ConnectionSettings server_settings; @@ -132,6 +142,8 @@ public: continued_buffer.iov_base = NULL; continued_buffer.iov_len = 0; + + dependency_tree = new DependencyTree(); } void @@ -144,6 +156,8 @@ public: delete remote_hpack_handle; ats_free(continued_buffer.iov_base); + + delete dependency_tree; } // Event handlers @@ -186,7 +200,10 @@ public: ssize_t client_rwnd, server_rwnd; // HTTP/2 frame sender - void send_data_frame(Http2Stream *stream); + void schedule_stream(Http2Stream *stream); + void send_data_frames_depends_on_priority(); + void send_data_frames(Http2Stream *stream); + Http2SendADataFrameResult send_a_data_frame(Http2Stream *stream, size_t &payload_length); void send_headers_frame(Http2Stream *stream); void send_rst_stream_frame(Http2StreamId id, Http2ErrorCode ec); void send_settings_frame(const Http2ConnectionSettings &new_settings); @@ -227,6 +244,7 @@ private: // another CONTINUATION frame." Http2StreamId continued_stream_id; IOVec continued_buffer; + bool _scheduled; }; #endif // __HTTP2_CONNECTION_STATE_H__ diff --git a/proxy/http2/Http2DependencyTree.h b/proxy/http2/Http2DependencyTree.h new file mode 100644 index 0000000..8ea3bc2 --- /dev/null +++ b/proxy/http2/Http2DependencyTree.h @@ -0,0 +1,308 @@ +/** @file + + HTTP/2 Dependency Tree + + The original idea of Stream Priority Algorithm using Weighted Fair Queue (WFQ) + Scheduling is invented by Kazuho Oku (H2O project). + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + */ + +#ifndef __HTTP2_DEP_TREE_H__ +#define __HTTP2_DEP_TREE_H__ + +#include "ts/List.h" +#include "ts/Diags.h" +#include "ts/PriorityQueue.h" + +#include "HTTP2.h" + +// TODO: K is a constant, 256 is temporal value. +const static int K = 256; + +template <typename T> class Http2DependencyTree +{ +public: + class Node + { + public: + Node() + : active(false), + queued(false), + id(HTTP2_PRIORITY_DEFAULT_STREAM_DEPENDENCY), + weight(HTTP2_PRIORITY_DEFAULT_WEIGHT), + point(0), + parent(NULL), + t(NULL) + { + entry = new PriorityQueueEntry<Node *>(this); + queue = new PriorityQueue<Node *>(); + } + Node(uint32_t i, uint32_t w, uint32_t p, Node *n, T t) + : active(false), queued(false), id(i), weight(w), point(p), parent(n), t(t) + { + entry = new PriorityQueueEntry<Node *>(this); + queue = new PriorityQueue<Node *>(); + } + + ~Node() + { + delete entry; + delete queue; + + // delete all child nodes + if (!children.empty()) { + Node *node = children.head; + Node *next = NULL; + while (node) { + next = node->link.next; + children.remove(node); + delete node; + node = next; + } + } + } + + LINK(Node, link); + + bool + operator<(const Node &n) const + { + return point < n.point; + } + bool + operator>(const Node &n) const + { + return point > n.point; + } + + bool active; + bool queued; + uint32_t id; + uint32_t weight; + uint32_t point; + Node *parent; + DLL<Node> children; + PriorityQueueEntry<Node *> *entry; + PriorityQueue<Node *> *queue; + T t; + }; + + Http2DependencyTree() { _root = new Node(); } + ~Http2DependencyTree() { delete _root; } + Node *find(uint32_t id); + Node *add(uint32_t parent_id, uint32_t id, uint32_t weight, bool exclusive, T t); + void reprioritize(uint32_t new_parent_id, uint32_t id, bool exclusive); + void reprioritize(Node *node, uint32_t id, bool exclusive); + Node *top(); + void activate(Node *node); + void deactivate(Node *node, uint32_t sent); + void update(Node *node, uint32_t sent); + +private: + Node *_find(Node *node, uint32_t id); + Node *_top(Node *node); + void _change_parent(Node *new_parent, Node *node, bool exclusive); + + Node *_root; +}; + +template <typename T> +typename Http2DependencyTree<T>::Node * +Http2DependencyTree<T>::_find(Node *node, uint32_t id) +{ + if (node->id == id) { + return node; + } + + if (node->children.empty()) { + return NULL; + } + + Node *result = NULL; + for (Node *n = node->children.head; n; n = n->link.next) { + result = _find(n, id); + if (result != NULL) { + break; + } + } + + return result; +} + +template <typename T> +typename Http2DependencyTree<T>::Node * +Http2DependencyTree<T>::find(uint32_t id) +{ + return _find(_root, id); +} + +template <typename T> +typename Http2DependencyTree<T>::Node * +Http2DependencyTree<T>::add(uint32_t parent_id, uint32_t id, uint32_t weight, bool exclusive, T t) +{ + Node *parent = find(parent_id); + if (parent == NULL) { + parent = _root; + } + + // Use stream id as initial point + Node *node = new Node(id, weight, id, parent, t); + + if (exclusive) { + while (Node *child = parent->children.pop()) { + node->children.push(child); + child->parent = node; + } + } + + parent->children.push(node); + + return node; +} + +template <typename T> +void +Http2DependencyTree<T>::reprioritize(uint32_t id, uint32_t new_parent_id, bool exclusive) +{ + Node *node = find(id); + if (node == NULL) { + return; + } + + reprioritize(node, new_parent_id, exclusive); +} + +template <typename T> +void +Http2DependencyTree<T>::reprioritize(Node *node, uint32_t new_parent_id, bool exclusive) +{ + if (node == NULL) { + return; + } + + Node *old_parent = node->parent; + if (old_parent->id == new_parent_id) { + // Do nothing + return; + } + + Node *new_parent = find(new_parent_id); + if (new_parent == NULL) { + return; + } + _change_parent(new_parent, old_parent, false); + _change_parent(node, new_parent, exclusive); +} + +// Change node's parent to new_parent +template <typename T> +void +Http2DependencyTree<T>::_change_parent(Node *node, Node *new_parent, bool exclusive) +{ + node->parent->children.remove(node); + node->parent = NULL; + + if (exclusive) { + while (Node *child = new_parent->children.pop()) { + node->children.push(child); + child->parent = node; + } + } + + new_parent->children.push(node); + node->parent = new_parent; +} + +template <typename T> +typename Http2DependencyTree<T>::Node * +Http2DependencyTree<T>::_top(Node *node) +{ + Node *child = node; + + while (child != NULL) { + if (child->active) { + return child; + } else if (!child->queue->empty()) { + child = child->queue->top()->node; + } else { + return NULL; + } + } + + return child; +} + +template <typename T> +typename Http2DependencyTree<T>::Node * +Http2DependencyTree<T>::top() +{ + return _top(_root); +} + +template <typename T> +void +Http2DependencyTree<T>::activate(Node *node) +{ + node->active = true; + + while (node->parent != NULL && !node->queued) { + node->parent->queue->push(node->entry); + node->queued = true; + node = node->parent; + } +} + +template <typename T> +void +Http2DependencyTree<T>::deactivate(Node *node, uint32_t sent) +{ + node->active = false; + + while (node->queue->empty() && node->parent != NULL) { + ink_assert(node->parent->queue->top() == node->entry); + + node->parent->queue->pop(); + node->queued = false; + + node = node->parent; + } + + update(node, sent); +} + +template <typename T> +void +Http2DependencyTree<T>::update(Node *node, uint32_t sent) +{ + while (node->parent != NULL) { + node->point += sent * K / (node->weight + 1); + + if (node->queued) { + node->parent->queue->update(node->entry, true); + } else { + node->parent->queue->push(node->entry); + node->queued = true; + } + + node = node->parent; + } +} + +#endif // __HTTP2_DEP_TREE_H__ diff --git a/proxy/http2/Http2Stream.cc b/proxy/http2/Http2Stream.cc index df35f1e..e54ed85 100644 --- a/proxy/http2/Http2Stream.cc +++ b/proxy/http2/Http2Stream.cc @@ -255,7 +255,7 @@ Http2Stream::do_io_close(int /* flags */) if (parent) { // Make sure any trailing end of stream frames are sent - static_cast<Http2ClientSession *>(parent)->connection_state.send_data_frame(this); + static_cast<Http2ClientSession *>(parent)->connection_state.send_data_frames(this); // Remove ourselves from the stream list static_cast<Http2ClientSession *>(parent)->connection_state.delete_stream(this); @@ -444,7 +444,7 @@ Http2Stream::update_write_request(IOBufferReader *buf_reader, int64_t write_len, retval = false; } // Send the data frame - parent->connection_state.send_data_frame(this); + send_response_body(); } break; } @@ -459,11 +459,11 @@ Http2Stream::update_write_request(IOBufferReader *buf_reader, int64_t write_len, // Defer sending the write complete until the send_data_frame has sent it all // this_ethread()->schedule_imm(this, send_event, &write_vio); this->mark_body_done(); - parent->connection_state.send_data_frame(this); + send_response_body(); retval = false; } else { this_ethread()->schedule_imm(this, VC_EVENT_WRITE_READY, &write_vio); - parent->connection_state.send_data_frame(this); + send_response_body(); // write_vio._cont->handleEvent(send_event, &write_vio); } } @@ -474,6 +474,19 @@ Http2Stream::update_write_request(IOBufferReader *buf_reader, int64_t write_len, } void +Http2Stream::send_response_body() +{ + Http2ClientSession *parent = static_cast<Http2ClientSession *>(this->get_parent()); + + if (Http2::stream_priority_enabled) { + parent->connection_state.schedule_stream(this); + } else { + // Send DATA frames directly + parent->connection_state.send_data_frames(this); + } +} + +void Http2Stream::reenable(VIO *vio) { if (this->parent) { diff --git a/proxy/http2/Http2Stream.h b/proxy/http2/Http2Stream.h index 5ef7818..51606f0 100644 --- a/proxy/http2/Http2Stream.h +++ b/proxy/http2/Http2Stream.h @@ -28,9 +28,13 @@ #include "../ProxyClientTransaction.h" #include "Http2DebugNames.h" #include "../http/HttpTunnel.h" // To get ChunkedHandler +#include "Http2DependencyTree.h" +class Http2Stream; class Http2ConnectionState; +typedef Http2DependencyTree<Http2Stream *> DependencyTree; + class Http2Stream : public ProxyClientTransaction { public: @@ -45,6 +49,7 @@ public: response_reader(NULL), request_reader(NULL), request_buffer(CLIENT_CONNECTION_FIRST_READ_BUFFER_SIZE_INDEX), + priority_node(NULL), _id(sid), _state(HTTP2_STREAM_STATE_IDLE), trailing_header(false), @@ -156,6 +161,7 @@ public: void update_read_request(int64_t read_len, bool send_update); bool update_write_request(IOBufferReader *buf_reader, int64_t write_len, bool send_update); void reenable(VIO *vio); + void send_response_body(); // Stream level window size ssize_t client_rwnd, server_rwnd; @@ -177,6 +183,7 @@ public: IOBufferReader *response_reader; IOBufferReader *request_reader; MIOBuffer request_buffer; + DependencyTree::Node *priority_node; EThread * get_thread() diff --git a/proxy/http2/Makefile.am b/proxy/http2/Makefile.am index 5912847..ad34798 100644 --- a/proxy/http2/Makefile.am +++ b/proxy/http2/Makefile.am @@ -42,6 +42,7 @@ libhttp2_a_SOURCES = \ Http2ConnectionState.h \ Http2DebugNames.cc \ Http2DebugNames.h \ + Http2DependencyTree.h \ Http2Stream.cc \ Http2Stream.h \ Http2SessionAccept.cc \ @@ -55,9 +56,12 @@ if BUILD_TESTS endif noinst_PROGRAMS = \ - test_Huffmancode + test_Huffmancode \ + test_Http2DependencyTree -TESTS = test_Huffmancode +TESTS = \ + test_Huffmancode \ + test_Http2DependencyTree test_Huffmancode_LDADD = \ $(top_builddir)/lib/ts/libtsutil.la @@ -66,3 +70,10 @@ test_Huffmancode_SOURCES = \ test_Huffmancode.cc \ HuffmanCodec.cc \ HuffmanCodec.h + +test_Http2DependencyTree_LDADD = \ + $(top_builddir)/lib/ts/libtsutil.la + +test_Http2DependencyTree_SOURCES = \ + test_Http2DependencyTree.cc \ + Http2DependencyTree.h diff --git a/proxy/http2/test_Http2DependencyTree.cc b/proxy/http2/test_Http2DependencyTree.cc new file mode 100644 index 0000000..c94c373 --- /dev/null +++ b/proxy/http2/test_Http2DependencyTree.cc @@ -0,0 +1,327 @@ +/** @file + + Unit tests for Http2DependencyTree + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +*/ + +#include <iostream> +#include <string.h> +#include <sstream> + +#include "ts/TestBox.h" + +#include "Http2DependencyTree.h" + +using namespace std; + +typedef Http2DependencyTree<string *> Tree; + +/** + * Exclusive Dependency Creation + * + * A A + * / \ => | + * B C D + * / \ + * B C + */ +REGRESSION_TEST(Http2DependencyTree_1)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Tree *tree = new Tree(); + string a("A"), b("B"), c("C"), d("D"); + + tree->add(0, 1, 0, false, &b); + tree->add(0, 3, 0, false, &c); + + Tree::Node *node_a = tree->find(0); + Tree::Node *node_b = tree->find(1); + Tree::Node *node_c = tree->find(3); + + box.check(node_b->parent == node_a, "parent of B should be A"); + box.check(node_c->parent == node_a, "parent of C should be A"); + + // Add node with exclusive flag + tree->add(0, 5, 0, true, &d); + + Tree::Node *node_d = tree->find(5); + + box.check(node_d->parent == node_a, "parent of D should be A"); + box.check(node_b->parent == node_d, "parent of B should be D"); + box.check(node_c->parent == node_d, "parent of C should be D"); + + delete tree; +} + +/** + * Reprioritization (non-exclusive) + * + * x x + * | | + * A D + * / \ / \ + * B C ==> F A + * / \ / \ + * D E B C + * | | + * F E + */ +REGRESSION_TEST(Http2DependencyTree_2)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Tree *tree = new Tree(); + string a("A"), b("B"), c("C"), d("D"), e("E"), f("F"); + + tree->add(0, 1, 0, false, &a); + tree->add(1, 3, 0, false, &b); + tree->add(1, 5, 0, false, &c); + tree->add(5, 7, 0, false, &d); + tree->add(5, 9, 0, false, &e); + tree->add(7, 11, 0, false, &f); + + tree->reprioritize(1, 7, false); + + Tree::Node *node_x = tree->find(0); + Tree::Node *node_a = tree->find(1); + Tree::Node *node_d = tree->find(7); + Tree::Node *node_f = tree->find(11); + + box.check(node_a->parent == node_d, "parent of A should be D"); + box.check(node_d->parent == node_x, "parent of D should be X"); + box.check(node_f->parent == node_d, "parent of F should be D"); + + delete tree; +} + +/** + * Reprioritization (exclusive) + * + * x x + * | | + * A D + * / \ | + * B C ==> A + * / \ /|\ + * D E B C F + * | | + * F E + */ +REGRESSION_TEST(Http2DependencyTree_3)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Tree *tree = new Tree(); + string a("A"), b("B"), c("C"), d("D"), e("E"), f("F"); + + tree->add(0, 1, 0, false, &a); + tree->add(1, 3, 0, false, &b); + tree->add(1, 5, 0, false, &c); + tree->add(5, 7, 0, false, &d); + tree->add(5, 9, 0, false, &e); + tree->add(7, 11, 0, false, &f); + + tree->reprioritize(1, 7, true); + + Tree::Node *node_x = tree->find(0); + Tree::Node *node_a = tree->find(1); + Tree::Node *node_d = tree->find(7); + Tree::Node *node_f = tree->find(11); + + box.check(node_a->parent == node_d, "parent of A should be D"); + box.check(node_d->parent == node_x, "parent of D should be X"); + box.check(node_f->parent == node_a, "parent of F should be A"); + + delete tree; +} + +/** + * Only One Node Tree + * ROOT + * / + * A(1) + */ +REGRESSION_TEST(Http2DependencyTree_4)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Tree *tree = new Tree(); + string a("A"); + tree->add(0, 1, 0, false, &a); + + Tree::Node *node_a = tree->find(1); + + box.check(tree->top() == NULL, "top should be NULL"); + + tree->activate(node_a); + box.check(tree->top() == node_a, "top should be A"); + + tree->deactivate(node_a, 0); + box.check(tree->top() == NULL, "top should be NULL"); + + delete tree; +} + +/** + * Simple Tree + * ROOT + * / + * A(3) + * / + * B(5) + * + */ +REGRESSION_TEST(Http2DependencyTree_5)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Tree *tree = new Tree(); + string a("A"), b("B"), c("C"); + + tree->add(0, 3, 15, false, &a); + tree->add(3, 5, 15, false, &b); + + Tree::Node *node_a = tree->find(3); + Tree::Node *node_b = tree->find(5); + + box.check(tree->top() == NULL, "top should be NULL"); + + tree->activate(node_a); + tree->activate(node_b); + box.check(tree->top() == node_a, "top should be A"); + + tree->deactivate(node_a, 0); + box.check(tree->top() == node_b, "top should be B"); + + delete tree; +} + +/** + * Basic Tree + * ROOT + * / \ + * A(3) D(9) + * / \ + * B(5) C(7) + * + */ +REGRESSION_TEST(Http2DependencyTree_6)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Tree *tree = new Tree(); + + string a("A"), b("B"), c("C"), d("D"); + + // NOTE, weight is actual weight - 1 + tree->add(0, 3, 20, false, &a); // node_a is unused + Tree::Node *node_b = tree->add(3, 5, 10, false, &b); + Tree::Node *node_c = tree->add(3, 7, 10, false, &c); + Tree::Node *node_d = tree->add(0, 9, 20, false, &d); + + // Activate B, C and D + tree->activate(node_b); + tree->activate(node_c); + tree->activate(node_d); + + ostringstream oss; + + for (int i = 0; i < 90; ++i) { + Tree::Node *node = tree->top(); + oss << node->t->c_str(); + tree->update(node, 100); + } + + const string expect = "BDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBD"; + box.check(oss.str() == expect, "\nExpect : %s\nActual : %s", expect.c_str(), oss.str().c_str()); + + delete tree; +} + +/** + * Tree of Chrome 50 + * + * ROOT + * / | \ + * A(3) B(5) ... I(19) + * + */ +REGRESSION_TEST(Http2DependencyTree_7)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Tree *tree = new Tree(); + + string a("A"), b("B"), c("C"), d("D"), e("E"), f("F"), g("G"), h("H"), i("I"); + + Tree::Node *node_a = tree->add(0, 3, 255, false, &a); + Tree::Node *node_b = tree->add(0, 5, 255, false, &b); + Tree::Node *node_c = tree->add(0, 7, 255, false, &c); + Tree::Node *node_d = tree->add(0, 9, 182, false, &d); + Tree::Node *node_e = tree->add(0, 11, 182, false, &e); + Tree::Node *node_f = tree->add(0, 13, 182, false, &f); + Tree::Node *node_g = tree->add(0, 15, 146, false, &g); + Tree::Node *node_h = tree->add(0, 17, 146, false, &h); + Tree::Node *node_i = tree->add(0, 19, 146, false, &i); + + // Activate A and B + tree->activate(node_a); + tree->activate(node_b); + tree->activate(node_c); + tree->activate(node_d); + tree->activate(node_e); + tree->activate(node_f); + tree->activate(node_g); + tree->activate(node_h); + tree->activate(node_i); + + ostringstream oss; + + for (int i = 0; i < 108; ++i) { + Tree::Node *node = tree->top(); + oss << node->t->c_str(); + + tree->update(node, 16375); + } + + const string expect = + "ABCDEFGHIABCDEFGHIABCDEFABCGHIABCDEFABCGHIDEFABCGHIDEFABCABCDEFGHIABCDEFABCGHIABCDEFABCGHIDEFABCGHIDEFABCABC"; + + box.check(oss.str() == expect, "\nExpect : %s\nActual : %s", expect.c_str(), oss.str().c_str()); + + delete tree; +} + +int +main(int /* argc ATS_UNUSED */, const char ** /* argv ATS_UNUSED */) +{ + const char *name = "Http2DependencyTree"; + RegressionTest::run(name); + + return RegressionTest::final_status == REGRESSION_TEST_PASSED ? 0 : 1; +} -- To stop receiving notification emails like this one, please contact ['"commits@trafficserver.apache.org" <commits@trafficserver.apache.org>'].