| // 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 <wlan/common/element_splitter.h> |
| #include <wlan/common/mac_frame.h> |
| #include <wlan/common/parse_element.h> |
| #include <wlan/common/write_element.h> |
| #include <wlan/mlme/mac_header_writer.h> |
| #include <wlan/mlme/mesh/hwmp.h> |
| #include <zircon/status.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; |
| |
| // 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 > 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; |
| } |
| |
| // See IEEE Std 802.11-2016, 14.10.10.3, Case A |
| static fbl::unique_ptr<Packet> MakeOriginalPrep(const MacHeaderWriter& header_writer, |
| const common::MacAddr& preq_transmitter_addr, |
| const common::MacAddr& self_addr, |
| const common::ParsedPreq& preq, |
| const MeshPath& path_to_originator, |
| const HwmpState& state) { |
| 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 = self_addr, |
| .target_hwmp_seqno = state.our_hwmp_seqno, |
| }, |
| nullptr, // For now, we don't support external addresses in path selection |
| { |
| .lifetime = preq.middle->lifetime, |
| .metric = 0, |
| .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 fbl::unique_ptr<Packet> MakeForwardedPreq(const MacHeaderWriter& mac_header_writer, |
| const common::ParsedPreq& incoming_preq, |
| uint32_t last_hop_metric, |
| 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 prep = MakeOriginalPrep(mac_header_writer, preq_transmitter_addr, self_addr, |
| preq, *path_to_originator, *state)) { |
| packets_to_tx->Enqueue(std::move(prep)); |
| } |
| } else { |
| bool replied = false; |
| if (!t.flags.target_only()) { |
| if (auto path_to_target = path_table->GetPath(t.target_addr)) { |
| // TODO(gbonik): send a PREP on behalf of target (case(c)) |
| 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 fbl::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)) |
| } |
| |
| PacketQueue HandleHwmpAction(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; |
| default: |
| break; |
| } |
| } |
| return ret; |
| } |
| |
| // IEEE Std 802.11-2016, 14.10.9.3, case A, Table 14-10 |
| static fbl::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)); |
| } |
| }); |
| } |
| |
| } // namespace wlan |