Development discussion of WireGuard
 help / color / mirror / Atom feed
From: David Woodhouse <dwmw2@infradead.org>
To: Daniel Lenski <dlenski@gmail.com>
Cc: "Jason A. Donenfeld" <Jason@zx2c4.com>,
	WireGuard mailing list <wireguard@lists.zx2c4.com>
Subject: Re: Duplicate IP address, and permissions problems on Windows
Date: Sat, 10 Apr 2021 10:25:38 +0100	[thread overview]
Message-ID: <731dfc961cc071b9ea25f3ef8fb04105956bafe5.camel@infradead.org> (raw)
In-Reply-To: <CAOw_LSH1pnGXyZA=tYMvBdjXQVP1ZzTTXtk002AjsswTh=qpdg@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 2964 bytes --]

On Thu, 2021-04-08 at 10:53 -0700, Daniel Lenski wrote:
> On Thu, Apr 8, 2021 at 9:59 AM David Woodhouse <dwmw2@infradead.org> wrote:
> > Hm, your description doesn't match the code I see at that link.
> > 
> > You're using GetAdaptersAddresses() which gives you the UP/DOWN status
> > as well as the addresses, and you iterate over those. The loop is
> > 
> >  ∀ adapter, ∀ Unicast address on that adapter:
> >      Check if it's our Legacy IP or IPv6 address.
> > 
> > That isn't O(n²), is it? It's still O(n) of the total number of unicast
> > addresses in the system?
> 
> It's O(n²) the number of unicast addresses, because there's an extra layer…
> 
>   ∀ adapter, ∀ Unicast address on that adapter (iterating via
> GetAdaptersAddresses)
>       1. Check if it's using our Legacy IP or IPv6 address.
>       2. If yes, then check if the other adapter is UP or non-UP
>       3. If non-UP, then…
>           ∀ Unicast address on the system (iterating via
> GetUnicastIpAddressTable(), since the other one maddeningly lacks an
> API to delete addresses)
>           2. If non-UP, then steal/delete/reclaim the desired address from it.

Nah, that doesn't make it O(n²) because anything after step 1 doesn't
actually happen for *every* address. It only happens for the one or two
addresses which match our Legacy IP or IPv6 address. And we *know*
there can be only one match for each because that's the whole point of
this exercise, right?

So it's O(n) for checking all the addresses in the system against our
own address(es), then O(n) for each of up to two addresses that get
matches. O(3n) is still O(n).

And I still think you can fix it just to be O(1n) this way anyway,
can't you:

> > Alternatively, can't we start with GetUnicastIpAddressTable() as my
> > original code did, and if we want to check whether an interface is down
> > before we steal the address from it, use GetIfEntry2() to find out?
> > 
> > Using GetIfEntry2() is probably a saner way to find the InterfaceIndex
> > for the Wintun itself, which I was dredging the registry for manually.



> Let's save the OpenConnect-specific decisions, but…
> 
> It seems to me that we've identifying a couple of tasks that many
> users of Wintun would need, and which are (in my opinion) quite
> tedious to implement robustly in Windows:
> 
> 1. Identifying the “interface index” of the newly-created adapter (for
> use with 'netsh', etc.).
> 2. Reclaiming desired Layer3 (IP) addresses from other non-UP adapters
> to which they may already be assigned.
> 
> If the Wintun developers are amenable to it, these both seem like they
> could be useful additions to Wintun itself.

Along with the driver extension to add headroom/tailroom to TUN_PACKET,
I agree. I'd be interested to hear Jason's and Simon's thoughts about
those in principle, before we rephrase those suggestions in the form of
a pull request.


[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5174 bytes --]

      reply	other threads:[~2021-04-10  9:25 UTC|newest]

Thread overview: 11+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-04-06 11:29 David Woodhouse
2021-04-07  0:17 ` Jason A. Donenfeld
2021-04-07  8:18   ` David Woodhouse
2021-04-07 23:05     ` Daniel Lenski
2021-04-12 17:50       ` Jason A. Donenfeld
2021-04-07 23:00   ` Daniel Lenski
2021-04-08  8:46     ` David Woodhouse
2021-04-08 16:09       ` Daniel Lenski
2021-04-08 16:59     ` David Woodhouse
2021-04-08 17:53       ` Daniel Lenski
2021-04-10  9:25         ` David Woodhouse [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=731dfc961cc071b9ea25f3ef8fb04105956bafe5.camel@infradead.org \
    --to=dwmw2@infradead.org \
    --cc=Jason@zx2c4.com \
    --cc=dlenski@gmail.com \
    --cc=wireguard@lists.zx2c4.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).