| // Copyright 2018 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include <zircon/status.h> |
| |
| #include <memory> |
| |
| #include <wlan/common/element_splitter.h> |
| #include <wlan/common/mac_frame.h> |
| #include <wlan/common/parse_element.h> |
| #include <wlan/common/perr_destination_parser.h> |
| #include <wlan/common/write_element.h> |
| #include <wlan/mlme/mac_header_writer.h> |
| #include <wlan/mlme/mesh/hwmp.h> |
| |
| namespace wlan { |
| |
| static constexpr size_t kInitialTtl = 32; |
| static constexpr size_t kMaxHwmpFrameSize = 2048; |
| static constexpr size_t kDot11MeshHWMPactivePathTimeoutTu = 5000; |
| static constexpr size_t kDot11MeshHWMPmaxPREQretries = 3; |
| static constexpr size_t kDot11MeshHWMPpreqMinIntervalTu = 100; |
| static constexpr bool kDot11MeshHWMPtargetOnly = true; |
| static constexpr size_t kDot11MeshHWMPperrMinIntervalTu = 100; |
| |
| HwmpState::HwmpState(std::unique_ptr<Timer> timer) |
| : our_hwmp_seqno(0), |
| timer_mgr(std::move(timer)), |
| perr_rate_limiter(WLAN_TU(kDot11MeshHWMPperrMinIntervalTu), 1) {} |
| |
| // According to IEEE Std 802.11-2016, 14.10.8.3 |
| bool HwmpSeqnoLessThan(uint32_t a, uint32_t b) { |
| // Perform subtraction mod 2^32. |
| // |
| // If a <= b, then d = abs(a - b). |
| // If a > b, then d = 2^32 - abs(a - b). |
| // In either case, 'd' is the distance on the circle that one needs to walk |
| // if starting from 'a', finishing at 'b' and going in the positive direction. |
| // |
| // 'a' precedes 'b' iff this walk distance 'd' is non-zero and is less than |
| // half the length of the circle. Note there is an edge case where 'a' and 'b' |
| // are exactly 2^31 apart (i.e., diametrically opposed on the circle). We will |
| // return false in that case. |
| uint32_t d = b - a; |
| // Equivalent to d != 0 && d < (1u << 31); |
| return static_cast<int32_t>(d) > 0; |
| } |
| |
| static uint32_t MaxHwmpSeqno(uint32_t a, uint32_t b) { return HwmpSeqnoLessThan(a, b) ? b : a; } |
| |
| // See IEEE Std 802.11-2016, 14.10.8.4 |
| static bool ShouldUpdatePathToRemoteNode(const MeshPath* path, uint32_t remote_hwmp_seqno, |
| uint32_t total_metric) { |
| // No known path: definitely create one |
| if (!path) { |
| return true; |
| } |
| |
| // Update if we got a more recent HWMP sequence number |
| if (path->hwmp_seqno && HwmpSeqnoLessThan(*path->hwmp_seqno, remote_hwmp_seqno)) { |
| return true; |
| } |
| |
| // If the sequence number is unknown or exactly matches what we received, |
| // update the path if the metric improved |
| if (!path->hwmp_seqno || *path->hwmp_seqno == remote_hwmp_seqno) { |
| return path->metric > total_metric; |
| } |
| |
| return false; |
| } |
| |
| // See IEEE Std 802.11-2016, 14.10.8.4 |
| // |
| // "Remote" node is either the originator or the target |
| // (for PREQ and PREP elements, respectively) |
| // |
| // Returns the mesh path to the remote node if it was updated and nullptr |
| // otherwise. |
| static const MeshPath* UpdateForwardingInfo(PathTable* path_table, HwmpState* state, |
| const common::MacAddr& transmitter_addr, |
| const common::MacAddr& remote_addr, |
| uint32_t remote_hwmp_seqno, uint32_t metric, |
| uint32_t last_hop_metric, unsigned hop_count, |
| uint32_t lifetime_tu) { |
| zx::time expiration = state->timer_mgr.Now() + WLAN_TU(lifetime_tu); |
| const MeshPath* ret = nullptr; |
| |
| // First, update the path information for the originator/destination node |
| // (see the last two bullet points in 14.10.8.4) |
| auto path = path_table->GetPath(remote_addr); |
| if (ShouldUpdatePathToRemoteNode(path, remote_hwmp_seqno, metric + last_hop_metric)) { |
| zx::time old_expiration = path ? path->expiration_time : zx::time{}; |
| // See Table 14-9, columns titled 'Forwarding information for originator |
| // mesh STA' and 'Forwarding information for target mesh STA'. |
| ret = path_table->AddOrUpdatePath(remote_addr, |
| MeshPath{ |
| .next_hop = transmitter_addr, |
| .hwmp_seqno = {remote_hwmp_seqno}, |
| .expiration_time = std::max(old_expiration, expiration), |
| .metric = metric + last_hop_metric, |
| .hop_count = hop_count + 1, |
| }); |
| } |
| |
| // Update the path information for the transmitter if it is different from the |
| // originator/destination (see the first bullet point in 14.10.8.4). |
| if (transmitter_addr != remote_addr) { |
| auto path = path_table->GetPath(transmitter_addr); |
| if (!path || path->metric > last_hop_metric) { |
| zx::time old_expiration = path ? path->expiration_time : zx::time{}; |
| auto path_seqno = path ? path->hwmp_seqno : std::optional<uint32_t>{}; |
| |
| path_table->AddOrUpdatePath(transmitter_addr, |
| MeshPath{ |
| .next_hop = transmitter_addr, |
| .hwmp_seqno = path_seqno, |
| .expiration_time = std::max(old_expiration, expiration), |
| .metric = last_hop_metric, |
| .hop_count = 1, |
| }); |
| } |
| } |
| |
| return ret; |
| } |
| |
| struct SeqnoAndMetric { |
| uint32_t hwmp_seqno; |
| uint32_t metric; |
| |
| static SeqnoAndMetric FromState(const HwmpState* state) { |
| return {.hwmp_seqno = state->our_hwmp_seqno, .metric = 0}; |
| } |
| |
| static SeqnoAndMetric FromPath(const MeshPath* path) { |
| ZX_ASSERT(path->hwmp_seqno.has_value()); |
| return {.hwmp_seqno = *path->hwmp_seqno, .metric = path->metric}; |
| } |
| }; |
| |
| // See IEEE Std 802.11-2016, 14.10.10.3, Cases A and C |
| static std::unique_ptr<Packet> MakeOriginalPrep(const MacHeaderWriter& header_writer, |
| const common::MacAddr& preq_transmitter_addr, |
| const PreqPerTarget& per_target, |
| const common::ParsedPreq& preq, |
| const MeshPath& path_to_originator, |
| SeqnoAndMetric target_info) { |
| auto packet = GetWlanPacket(kMaxHwmpFrameSize); |
| if (!packet) { |
| return {}; |
| } |
| BufferWriter w(*packet); |
| header_writer.WriteMeshMgmtHeader(&w, kAction, preq_transmitter_addr); |
| w.Write<ActionFrame>()->category = action::kMesh; |
| w.Write<MeshActionHeader>()->mesh_action = action::kHwmpMeshPathSelection; |
| common::WritePrep(&w, |
| { |
| .flags = {}, |
| .hop_count = 0, |
| .element_ttl = kInitialTtl, |
| .target_addr = per_target.target_addr, |
| .target_hwmp_seqno = target_info.hwmp_seqno, |
| }, |
| nullptr, // For now, we don't support external addresses in |
| // path selection |
| { |
| .lifetime = preq.middle->lifetime, |
| .metric = target_info.metric, |
| .originator_addr = preq.header->originator_addr, |
| // Safe because this can only be called after updating |
| // the path to the originator |
| .originator_hwmp_seqno = *path_to_originator.hwmp_seqno, |
| }); |
| packet->set_len(w.WrittenBytes()); |
| return packet; |
| } |
| |
| // See IEEE Std 802.11-2016, 14.10.9.3, Case E |
| static std::unique_ptr<Packet> MakeForwardedPreq(const MacHeaderWriter& mac_header_writer, |
| const common::ParsedPreq& incoming_preq, |
| uint32_t last_hop_metric, |
| fbl::Span<const PreqPerTarget> to_forward) { |
| auto packet = GetWlanPacket(kMaxHwmpFrameSize); |
| if (!packet) { |
| return {}; |
| } |
| BufferWriter w(*packet); |
| mac_header_writer.WriteMeshMgmtHeader(&w, kAction, common::kBcastMac); |
| w.Write<ActionFrame>()->category = action::kMesh; |
| w.Write<MeshActionHeader>()->mesh_action = action::kHwmpMeshPathSelection; |
| common::WritePreq(&w, |
| { |
| .flags = incoming_preq.header->flags, |
| .hop_count = static_cast<uint8_t>(incoming_preq.header->hop_count + 1), |
| .element_ttl = static_cast<uint8_t>(incoming_preq.header->element_ttl - 1), |
| .path_discovery_id = incoming_preq.header->path_discovery_id, |
| .originator_addr = incoming_preq.header->originator_addr, |
| .originator_hwmp_seqno = incoming_preq.header->originator_hwmp_seqno, |
| }, |
| incoming_preq.originator_external_addr, |
| { |
| .lifetime = incoming_preq.middle->lifetime, |
| .metric = incoming_preq.middle->metric + last_hop_metric, |
| .target_count = static_cast<uint8_t>(to_forward.size()), |
| }, |
| to_forward); |
| packet->set_len(w.WrittenBytes()); |
| return packet; |
| } |
| |
| // See IEEE Std 802.11-2016, 14.10.9.4.3 |
| static void HandlePreq(const common::MacAddr& preq_transmitter_addr, |
| const common::MacAddr& self_addr, const common::ParsedPreq& preq, |
| uint32_t last_hop_metric, const MacHeaderWriter& mac_header_writer, |
| HwmpState* state, PathTable* path_table, PacketQueue* packets_to_tx) { |
| // The spec (IEEE Std 802.11-2016, 14.10.9.4.2) suggests that we entirely |
| // throw out the PREQ if it doesn't meet the "acceptance criteria", |
| // e.g. if there is no known path to the target. This seems wrong: we could |
| // still use the information in the PREQ to update the paths to the |
| // transmitter and the originator. Also, the sentence refers to "THE" target |
| // address of the PREQ element, whereas in fact a single PREQ element may |
| // contain several target addresses. |
| auto path_to_originator = |
| UpdateForwardingInfo(path_table, state, preq_transmitter_addr, preq.header->originator_addr, |
| preq.header->originator_hwmp_seqno, preq.middle->metric, last_hop_metric, |
| preq.header->hop_count, preq.middle->lifetime); |
| // The spec also suggests another case when we need to handle the PREQ: |
| // the sequence number in the PREQ matches what we have cached for the target, |
| // but we haven't seen the (originator_addr, path_discovery_id) pair yet. |
| // It is unclear yet whether this is really necessary. To implement this, |
| // we would need to cache (originator_addr, path_discovery_id) pairs, which |
| // could be avoided otherwise. |
| if (path_to_originator == nullptr) { |
| return; |
| } |
| |
| PreqPerTarget to_forward[kPreqMaxTargets]; |
| size_t num_to_forward = 0; |
| |
| for (auto t : preq.per_target) { |
| if (t.target_addr == self_addr) { |
| // TODO(gbonik): Also check if we are a proxy of target_addr |
| |
| // See IEEE Std 802.11-2016, 14.10.8.3, second bullet point |
| state->our_hwmp_seqno = MaxHwmpSeqno(state->our_hwmp_seqno, t.target_hwmp_seqno) + 1; |
| if (auto packet = MakeOriginalPrep(mac_header_writer, preq_transmitter_addr, t, preq, |
| *path_to_originator, SeqnoAndMetric::FromState(state))) { |
| packets_to_tx->Enqueue(std::move(packet)); |
| } |
| } else { |
| bool replied = false; |
| if (!t.flags.target_only()) { |
| auto path_to_target = path_table->GetPath(t.target_addr); |
| if (path_to_target != nullptr && path_to_target->hwmp_seqno.has_value() && |
| path_to_target->expiration_time >= state->timer_mgr.Now()) { |
| auto packet = |
| MakeOriginalPrep(mac_header_writer, preq_transmitter_addr, t, preq, |
| *path_to_originator, SeqnoAndMetric::FromPath(path_to_target)); |
| if (packet) { |
| packets_to_tx->Enqueue(std::move(packet)); |
| } |
| replied = true; |
| } |
| } |
| |
| if (preq.header->element_ttl > 1 && num_to_forward < countof(to_forward)) { |
| to_forward[num_to_forward] = t; |
| if (replied) { |
| // See IEEE Std 802.11-2016, 14.10.9.3, case E2: since we already |
| // replied to the PREQ, we need to set 'Target Only' to true so that |
| // other intermediate nodes do not reply. |
| to_forward[num_to_forward].flags.set_target_only(true); |
| } |
| num_to_forward += 1; |
| } |
| } |
| // TODO(gbonik): update proxy info if address extension is present (case |
| // (a)/(b)) |
| // TODO: Also update precursors if we decide to store them one day (case |
| // (d)) |
| // TODO(gobnik): reply to proactive (broadcast) PREQs (case (e)) |
| } |
| |
| if (num_to_forward > 0) { |
| if (auto packet = MakeForwardedPreq(mac_header_writer, preq, last_hop_metric, |
| {to_forward, num_to_forward})) { |
| packets_to_tx->Enqueue(std::move(packet)); |
| } |
| } |
| } |
| |
| // See IEEE Std 802.11-2016, 14.10.10.3, Case B |
| static std::unique_ptr<Packet> MakeForwardedPrep(const MacHeaderWriter& mac_header_writer, |
| const common::ParsedPrep& incoming_prep, |
| uint32_t last_hop_metric, |
| const MeshPath& path_to_originator) { |
| auto packet = GetWlanPacket(kMaxHwmpFrameSize); |
| if (!packet) { |
| return {}; |
| } |
| BufferWriter w(*packet); |
| mac_header_writer.WriteMeshMgmtHeader(&w, kAction, path_to_originator.next_hop); |
| w.Write<ActionFrame>()->category = action::kMesh; |
| w.Write<MeshActionHeader>()->mesh_action = action::kHwmpMeshPathSelection; |
| common::WritePrep(&w, |
| { |
| .flags = incoming_prep.header->flags, |
| .hop_count = static_cast<uint8_t>(incoming_prep.header->hop_count + 1), |
| .element_ttl = static_cast<uint8_t>(incoming_prep.header->element_ttl - 1), |
| .target_addr = incoming_prep.header->target_addr, |
| .target_hwmp_seqno = incoming_prep.header->target_hwmp_seqno, |
| }, |
| incoming_prep.target_external_addr, |
| { |
| .lifetime = incoming_prep.tail->lifetime, |
| .metric = incoming_prep.tail->metric + last_hop_metric, |
| .originator_addr = incoming_prep.tail->originator_addr, |
| .originator_hwmp_seqno = incoming_prep.tail->originator_hwmp_seqno, |
| }); |
| packet->set_len(w.WrittenBytes()); |
| return packet; |
| } |
| |
| // See IEEE Std 802.11-2016, 14.10.10.4.3 |
| static void HandlePrep(const common::MacAddr& prep_transmitter_addr, |
| const common::MacAddr& self_addr, const common::ParsedPrep& prep, |
| uint32_t last_hop_metric, const MacHeaderWriter& mac_header_writer, |
| HwmpState* state, PathTable* path_table, PacketQueue* packets_to_tx) { |
| auto path_to_target = |
| UpdateForwardingInfo(path_table, state, prep_transmitter_addr, prep.header->target_addr, |
| prep.header->target_hwmp_seqno, prep.tail->metric, last_hop_metric, |
| prep.header->hop_count, prep.tail->lifetime); |
| if (path_to_target == nullptr) { |
| return; |
| } |
| |
| auto it = state->state_by_target.find(prep.header->target_addr.ToU64()); |
| if (it != state->state_by_target.end()) { |
| // Path established successfully: cancel the retry timer |
| state->timer_mgr.Cancel(it->second.next_attempt); |
| state->state_by_target.erase(it); |
| } |
| |
| if (prep.tail->originator_addr != self_addr && prep.header->element_ttl > 1) { |
| if (auto path_to_originator = path_table->GetPath(prep.tail->originator_addr)) { |
| if (auto packet = |
| MakeForwardedPrep(mac_header_writer, prep, last_hop_metric, *path_to_originator)) { |
| packets_to_tx->Enqueue(std::move(packet)); |
| } |
| } |
| } |
| // TODO(gbonik): update proxy info if address extension is present (case |
| // (b)/(c)) |
| // TODO: Also update precursors if we decide to store them one day (case (d)) |
| } |
| |
| // See IEEE Std 802.11-2016, 14.10.11.4.3 |
| static bool ShouldInvalidatePathByPerr(const common::MacAddr& perr_transmitter_addr, |
| const common::ParsedPerrDestination& perr_dest, |
| const PathTable* path_table, uint32_t* out_hwmp_seqno) { |
| using Rc = ::fuchsia::wlan::mlme::ReasonCode; |
| |
| // PERR elements with an external address can only invalidate proxy |
| // information, not forwarding information. An element with reason code set to |
| // NO_FORWARDING_INFORMATION or DESTINATION_UNREACHABLE is not allowed to have |
| // an external address. See IEEE Std 802.11-2016, 14.10.11.3 for the list of |
| // valid PERR contents. |
| if (perr_dest.ext_addr != nullptr) { |
| return false; |
| } |
| |
| auto path = path_table->GetPath(perr_dest.header->dest_addr); |
| if (path == nullptr) { |
| return false; |
| } |
| if (path->next_hop != perr_transmitter_addr) { |
| return false; |
| } |
| |
| // Case (b) |
| // It is unfortunate that the spec suggests using 0 to indicate an unknown |
| // HWMP sequence value, instead of the "USN" flag like in PREQ. Zero is |
| // otherwise a perfectly normal value of the HWMP sequence number which could |
| // occur with the 32-bit counter rollover. |
| if (perr_dest.tail->reason_code == to_enum_type(Rc::MESH_PATH_ERROR_NO_FORWARDING_INFORMATION) && |
| perr_dest.header->hwmp_seqno == 0) { |
| if (path->hwmp_seqno.has_value()) { |
| *out_hwmp_seqno = *path->hwmp_seqno + 1; |
| } else { |
| *out_hwmp_seqno = 0; |
| } |
| return true; |
| } |
| |
| // Case (c) |
| if (perr_dest.tail->reason_code == to_enum_type(Rc::MESH_PATH_ERROR_DESTINATION_UNREACHABLE) || |
| perr_dest.tail->reason_code == to_enum_type(Rc::MESH_PATH_ERROR_NO_FORWARDING_INFORMATION)) { |
| if (!path->hwmp_seqno.has_value() || |
| HwmpSeqnoLessThan(*path->hwmp_seqno, perr_dest.header->hwmp_seqno)) { |
| *out_hwmp_seqno = perr_dest.header->hwmp_seqno; |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| static void WriteForwardedPerrDestination(const common::ParsedPerrDestination& incoming, |
| uint32_t new_hwmp_seqno, BufferWriter* writer) { |
| writer->WriteValue<PerrPerDestinationHeader>({ |
| .flags = incoming.header->flags, |
| .dest_addr = incoming.header->dest_addr, |
| .hwmp_seqno = new_hwmp_seqno, |
| }); |
| if (incoming.ext_addr != nullptr) { |
| writer->WriteValue<common::MacAddr>(*incoming.ext_addr); |
| } |
| writer->WriteValue<PerrPerDestinationTail>(*incoming.tail); |
| } |
| |
| // See IEEE Std 802.11-2016, 14.10.11.3, Case D |
| static std::unique_ptr<Packet> MakeForwardedPerr(const MacHeaderWriter& mac_header_writer, |
| const common::ParsedPerr& incoming_perr, |
| uint8_t num_destinations, |
| fbl::Span<const uint8_t> destinations) { |
| auto packet = GetWlanPacket(kMaxHwmpFrameSize); |
| if (!packet) { |
| return {}; |
| } |
| BufferWriter w(*packet); |
| // Note that we deviate from the standard here, which suggests maintaining a |
| // list of precursors for each path and sending individually-addressed |
| // management frames to all precursors of the invalidated paths. This seems |
| // impractical and would only take more air time. See 14.10.7, "PERR element |
| // individually addressed [Case D]". |
| mac_header_writer.WriteMeshMgmtHeader(&w, kAction, common::kBcastMac); |
| w.Write<ActionFrame>()->category = action::kMesh; |
| w.Write<MeshActionHeader>()->mesh_action = action::kHwmpMeshPathSelection; |
| common::WritePerr(&w, |
| { |
| .element_ttl = static_cast<uint8_t>(incoming_perr.header->element_ttl - 1), |
| .num_destinations = num_destinations, |
| }, |
| destinations); |
| packet->set_len(w.WrittenBytes()); |
| return packet; |
| } |
| |
| static void HandlePerr(const common::MacAddr& perr_transmitter_addr, const common::ParsedPerr& perr, |
| const MacHeaderWriter& mac_header_writer, HwmpState* state, |
| PathTable* path_table, PacketQueue* packets_to_tx) { |
| if (perr.header->num_destinations > kPerrMaxDestinations) { |
| return; |
| } |
| |
| // Buffer for constructing the "destinations" part of the forwarded PERR |
| uint8_t to_forward_buf[kPerrMaxDestinations * kPerrMaxDestinationSize]; |
| BufferWriter to_forward(to_forward_buf); |
| size_t num_dests_to_forward = 0; |
| |
| // Paths to be removed from the table |
| common::MacAddr dests_to_invalidate[kPerrMaxDestinations]; |
| size_t num_dests_to_invalidate = 0; |
| |
| common::PerrDestinationParser parser(perr.destinations); |
| for (size_t i = 0; i < perr.header->num_destinations; ++i) { |
| auto dest = parser.Next(); |
| if (!dest.has_value()) { |
| return; |
| } |
| |
| uint32_t hwmp_seqno; |
| if (ShouldInvalidatePathByPerr(perr_transmitter_addr, *dest, path_table, &hwmp_seqno)) { |
| dests_to_invalidate[num_dests_to_invalidate++] = dest->header->dest_addr; |
| WriteForwardedPerrDestination(*dest, hwmp_seqno, &to_forward); |
| ++num_dests_to_forward; |
| } |
| |
| // TODO(gbonik): invalidate proxy info. See IEEE Std |
| // 802.11-2016, 14.10.11.4.3, case (d) |
| } |
| |
| // Drop the element without processing if it has extra garbage at the end |
| if (parser.ExtraBytesLeft()) { |
| return; |
| } |
| |
| // Remove invalidated paths |
| for (size_t i = 0; i < num_dests_to_invalidate; ++i) { |
| path_table->RemovePath(dests_to_invalidate[i]); |
| } |
| |
| // Forward the frame |
| if (num_dests_to_forward > 0 && perr.header->element_ttl > 1 && |
| state->perr_rate_limiter.RecordEvent(state->timer_mgr.Now())) { |
| if (auto packet = MakeForwardedPerr(mac_header_writer, perr, num_dests_to_forward, |
| to_forward.WrittenData())) { |
| packets_to_tx->Enqueue(std::move(packet)); |
| } |
| } |
| } |
| |
| PacketQueue HandleHwmpAction(fbl::Span<const uint8_t> elements, |
| const common::MacAddr& action_transmitter_addr, |
| const common::MacAddr& self_addr, uint32_t last_hop_metric, |
| const MacHeaderWriter& mac_header_writer, HwmpState* state, |
| PathTable* path_table) { |
| PacketQueue ret; |
| for (auto [id, raw_body] : common::ElementSplitter(elements)) { |
| switch (id) { |
| case element_id::kPreq: |
| if (auto preq = common::ParsePreq(raw_body)) { |
| HandlePreq(action_transmitter_addr, self_addr, *preq, last_hop_metric, mac_header_writer, |
| state, path_table, &ret); |
| } |
| break; |
| case element_id::kPrep: |
| if (auto prep = common::ParsePrep(raw_body)) { |
| HandlePrep(action_transmitter_addr, self_addr, *prep, last_hop_metric, mac_header_writer, |
| state, path_table, &ret); |
| } |
| break; |
| case element_id::kPerr: |
| if (auto perr = common::ParsePerr(raw_body)) { |
| HandlePerr(action_transmitter_addr, *perr, mac_header_writer, state, path_table, &ret); |
| } |
| break; |
| default: |
| break; |
| } |
| } |
| return ret; |
| } |
| |
| // IEEE Std 802.11-2016, 14.10.9.3, case A, Table 14-10 |
| static std::unique_ptr<Packet> MakeOriginalPreq(const common::MacAddr& target_addr, |
| const common::MacAddr& self_addr, |
| const MacHeaderWriter& mac_header_writer, |
| uint32_t our_hwmp_seqno, uint32_t path_discovery_id, |
| const PathTable& path_table) { |
| auto packet = GetWlanPacket(kMaxHwmpFrameSize); |
| if (!packet) { |
| return {}; |
| } |
| |
| BufferWriter w(*packet); |
| // IEEE Std 802.11-2016, 14.10.7, case A |
| mac_header_writer.WriteMeshMgmtHeader(&w, kAction, common::kBcastMac); |
| w.Write<ActionFrame>()->category = action::kMesh; |
| w.Write<MeshActionHeader>()->mesh_action = action::kHwmpMeshPathSelection; |
| |
| const MeshPath* path_to_target = path_table.GetPath(target_addr); |
| auto target_seqno = path_to_target ? path_to_target->hwmp_seqno : std::optional<uint32_t>(); |
| |
| PreqPerTargetFlags target_flags; |
| target_flags.set_target_only(kDot11MeshHWMPtargetOnly); |
| target_flags.set_usn(!target_seqno); |
| |
| PreqPerTarget per_target = { |
| .flags = target_flags, |
| .target_addr = target_addr, |
| .target_hwmp_seqno = target_seqno.value_or(0), |
| }; |
| |
| common::WritePreq(&w, |
| { |
| .flags = {}, |
| .hop_count = 0, |
| .element_ttl = kInitialTtl, |
| .path_discovery_id = path_discovery_id, |
| .originator_addr = self_addr, |
| .originator_hwmp_seqno = our_hwmp_seqno, |
| }, |
| nullptr, |
| { |
| .lifetime = kDot11MeshHWMPactivePathTimeoutTu, |
| .metric = 0, |
| .target_count = 1, |
| }, |
| {&per_target, 1}); |
| |
| packet->set_len(w.WrittenBytes()); |
| return packet; |
| } |
| |
| zx_status_t EmitOriginalPreq(const common::MacAddr& target_addr, |
| HwmpState::TargetState* target_state, const common::MacAddr& self_addr, |
| const MacHeaderWriter& mac_header_writer, HwmpState* state, |
| const PathTable& path_table, PacketQueue* packets_to_tx) { |
| zx_status_t status = |
| state->timer_mgr.Schedule(state->timer_mgr.Now() + WLAN_TU(kDot11MeshHWMPpreqMinIntervalTu), |
| {target_addr}, &target_state->next_attempt); |
| if (status != ZX_OK) { |
| errorf("[hwmp] failed to schedule a timer: %s\n", zx_status_get_string(status)); |
| return ZX_ERR_INTERNAL; |
| } |
| uint32_t our_hwmp_seqno = ++state->our_hwmp_seqno; |
| uint32_t path_discovery_id = ++state->next_path_discovery_id; |
| target_state->attempts_left -= 1; |
| if (auto packet = MakeOriginalPreq(target_addr, self_addr, mac_header_writer, our_hwmp_seqno, |
| path_discovery_id, path_table)) { |
| packets_to_tx->Enqueue(std::move(packet)); |
| } |
| return ZX_OK; |
| } |
| |
| zx_status_t InitiatePathDiscovery(const common::MacAddr& target_addr, |
| const common::MacAddr& self_addr, |
| const MacHeaderWriter& mac_header_writer, HwmpState* state, |
| const PathTable& path_table, PacketQueue* packets_to_tx) { |
| auto it = state->state_by_target.find(target_addr.ToU64()); |
| if (it != state->state_by_target.end()) { |
| it->second.attempts_left = kDot11MeshHWMPmaxPREQretries; |
| return ZX_OK; |
| } |
| |
| it = state->state_by_target |
| .emplace(target_addr.ToU64(), HwmpState::TargetState{{}, kDot11MeshHWMPmaxPREQretries}) |
| .first; |
| zx_status_t status = EmitOriginalPreq(target_addr, &it->second, self_addr, mac_header_writer, |
| state, path_table, packets_to_tx); |
| if (status != ZX_OK) { |
| state->state_by_target.erase(it); |
| } |
| return status; |
| } |
| |
| zx_status_t HandleHwmpTimeout(const common::MacAddr& self_addr, |
| const MacHeaderWriter& mac_header_writer, HwmpState* state, |
| const PathTable& path_table, PacketQueue* packets_to_tx) { |
| return state->timer_mgr.HandleTimeout([&](auto now, auto event, auto timeout_id) { |
| auto it = state->state_by_target.find(event.addr.ToU64()); |
| if (it == state->state_by_target.end() || it->second.next_attempt != timeout_id) { |
| return; |
| } |
| |
| if (it->second.attempts_left == 0) { |
| // Failed to discover the path after the maximum number of attempts. Clear |
| // the state. |
| state->state_by_target.erase(it); |
| return; |
| } |
| |
| zx_status_t status = EmitOriginalPreq(event.addr, &it->second, self_addr, mac_header_writer, |
| state, path_table, packets_to_tx); |
| if (status != ZX_OK) { |
| errorf("[hwmp] failed to schedule a path request frame transmission: %s\n", |
| zx_status_get_string(status)); |
| } |
| }); |
| } |
| |
| // IEEE Std 802.11-2016, Case B |
| PacketQueue OnMissingForwardingPath(const common::MacAddr& peer_to_notify, |
| const common::MacAddr& missing_destination, |
| const MacHeaderWriter& mac_header_writer, HwmpState* state) { |
| auto packet = GetWlanPacket(kMaxHwmpFrameSize); |
| if (!packet) { |
| return {}; |
| } |
| |
| if (!state->perr_rate_limiter.RecordEvent(state->timer_mgr.Now())) { |
| return {}; |
| } |
| |
| uint8_t destination_buf[kPerrMaxDestinationSize]; |
| BufferWriter destination_writer(destination_buf); |
| destination_writer.WriteValue<PerrPerDestinationHeader>({ |
| .flags = {}, |
| .dest_addr = missing_destination, |
| .hwmp_seqno = 0, |
| }); |
| destination_writer.WriteValue<PerrPerDestinationTail>( |
| {.reason_code = static_cast<uint16_t>( |
| fuchsia::wlan::mlme::ReasonCode::MESH_PATH_ERROR_NO_FORWARDING_INFORMATION)}); |
| |
| BufferWriter w(*packet); |
| mac_header_writer.WriteMeshMgmtHeader(&w, kAction, peer_to_notify); |
| w.Write<ActionFrame>()->category = action::kMesh; |
| w.Write<MeshActionHeader>()->mesh_action = action::kHwmpMeshPathSelection; |
| common::WritePerr(&w, |
| { |
| .element_ttl = kInitialTtl, |
| .num_destinations = 1, |
| }, |
| destination_writer.WrittenData()); |
| packet->set_len(w.WrittenBytes()); |
| |
| PacketQueue packets_to_tx; |
| packets_to_tx.Enqueue(std::move(packet)); |
| return packets_to_tx; |
| } |
| |
| } // namespace wlan |
