You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by so...@apache.org on 2016/05/20 16:49:34 UTC
[trafficserver] 02/15: TS-3535: Experimental Support of HTTP/2
Stream Priority feature
This is an automated email from the ASF dual-hosted git repository.
sorber pushed a commit to branch 6.2.x
in repository https://git-dual.apache.org/repos/asf/trafficserver.git
commit 2bf7e5850b55bbb9eca388540c71e68d172c38ea
Author: Masaori Koshiba <ma...@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
(cherry picked from commit 16172a4e79865d1201a51e85aeb72df8b0609986)
---
.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 4a7b81c..af55f7b 100644
--- a/.gitignore
+++ b/.gitignore
@@ -89,6 +89,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 da23cb6..b5bc60a 100644
--- a/doc/admin-guide/files/records.config.en.rst
+++ b/doc/admin-guide/files/records.config.en.rst
@@ -2997,6 +2997,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 8d17edb..6361971 100644
--- a/mgmt/RecordsConfig.cc
+++ b/mgmt/RecordsConfig.cc
@@ -1972,7 +1972,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" <co...@trafficserver.apache.org>.