Delete obsolete /* ARGSUSED */ lint comments.

ok miod@ millert@

spelling fixes; from paul tagliamonte
any parts of his diff not taken are noted on tech

Implement RFC 5919 (LDP End-of-LIB).

Implement RFC 6667 (Typed Wildcard FEC for PWid).

Implement RFC 5918 (Typed Wildcard FEC).

Implement support for PWid group wildcards.

This was missing from our original RFC 4447 VPLS implementation. Now
ldpd understands group wildcards as mandated by the RFC, but we still
don't send them ourselves. I can't see any case in which sending a group
wildcard would be useful, but nonetheless this patch provides a function
called lde_send_labelwithdraw_pwid_wcard() which is ready to be used in
the future anytime we feel like it might be useful.

Fix processing of Label Withdraw messages.

Whenever we receive a Label Withdraw message with an optional Label
TLV, we should check if this label matches the label previously
received from this neighbor for this FEC. If they don't match then we
shouldn't uninstall the previous label from the kernel. This fixes a
misinterpretation from the "Receive Label Withdraw" algorithm described
in the A.1.5 section of RFC 5036.

Also, simplify the check of pending withdraws in lde_check_release()
and lde_check_release_wcard().

Minor tweaks.

More renaming and whitespace cleanup.

No binary change after "strip -s".

Several minor tweaks.

Remove TODO comments about loop detection.

LDP loop detection is only necessary for ATM LSRs running in cell mode. We
are never going to implement this "feature".

Also, add two more comments in lde_check_request().

Fix small LIB<->LFIB synchronization issue.

ldpd operates only with the best routes of each IP prefix. In other words,
the routes with the lowest priorities.

When a route with a better priority is detected (possibly with a different
nexthop), we should uninstall the labels from the "old" routes and try
to install a new label for the new route (if there's one available in
the LIB).

In this specific case, ldpd was failing to uninstall the labels from the
old routes because it wasn't keeping track of each route's priority in
lde. With this missing bit of information, the parent process had no way
to get the correct label to uninstall when processing a IMSG_KLABEL_DELETE
message.

Add missing ntohl() when recording a label request.

Fixes the following ANVL LDP tests: 1.5 and 9.4.

Update copyright information.

Remove superfluous includes.

Make functions and variables static whenever possible.

The benefits of this include:
* clean up of the ldpd global namespace;
* improved readability;
* more hints to the compiler/linker to generate more efficient code.

Whenever possible, move global static variables to a smaller scope
(function).

All extern variables are now declared in header files to avoid unnecessary
duplication.

This patch also cleans up the indentation of all function prototypes
and global variables.

Add support for IPv6 (RFC 7552).

This includes:
* Full compliance to RFC 7552;
* Support for MD5 on LDPov6 sessions;
* Support for pseudowires over IPv6 LSPs (we're probably the world's
first implementation doing this);
* Support for the IPv6 explicit-null label;
* Knob to specify the prefered address-family for TCP transport
connections;
* Knob to use cisco non-compliant format to send and interpret the
Dual-Stack capability TLV.

Assorted fixes and small cleanup.

Nothing really interesting here.

Introduce a garbage collector for dead entries in the LIB.

If we lose a route and all of its associated labels, then there's no
point on keeping an entry for it in the LIB.

Simplify label allocation.

Whenever we lose a route, unset the local label. If the same route is
learned again later, allocate a new label for it. No need to be economic
with labels, it's not worth the added complexity.

Reuse lde_address_find() inside lde_check_mapping().

Copy structs by assignment instead of memcpy.

Copying by straight assignment is shorter, easier to read and has a
higher level of abstraction. We'll only avoid it when copying from an
unaligned source (e.g., network buffers).

In addition, copy in_addr structs directly.

Fix mess caused by my commit script.

I screwed up everything... trying to fix now.

Rework L2VPN code.

Fix bug in the processing of label withdraws and releases.

The F_MAP_PW_ID flag is only set for PW-ID mappings, which means that we
were ignoring all label withdraws and label releases for non PW-ID FECs.

Make send_labelmessage() more robust.

Immediately return from this function if the given list of mappings
is empty. This way we have more freedom when sending label messages,
not having to care with corner cases.

Fix byte order issues with notification messages.

Remove unnecessary break statements.

More renaming.

Rename a few more things to improve readability.

* s/F_PW_CONTROLWORD_CONF/F_PW_CWORD_CONF/ (shorter)
* s/F_PW_CONTROLWORD/F_PW_CWORD/ (shorter)
* s/LDPD_FLAG_*/F_LDPD_*/ (consistency)
* s/lde_nbr_address/lde_addr/ (shorter)
* s/ldp_discovery_socket/ldp_disc_socket/ (shorter)
* s/ldp_ediscovery_socket/ldp_edisc_socket/ (shorter)
* s/ldp_sendboth/main_imsg_compose_both/ (consistency)
* s/cons/total/ (makes more sense)
* s/kaddr/ka/ (consistency with remaining code)
* Always use 'ln' for lde_nbrs (consistency)

Rename a few constants to avoid confusion.

In ldpd we have the map structure, which is used to represent a label message,
and the fec structure, used to store FECs in the LIB.

As of now, ldpd supports two type of FECs:
* IPv4 prefix (FEC_TYPE_IPV4);
* PWID (FEC_TYPE_PWID).

For the label messages, the following contants were being used:
* FEC_WILDCARD;
* FEC_PREFIX (IPv4 or IPv6);
* FEC_PWID.

Since these contants have similar names to the previous ones, rename
them to:
* MAP_TYPE_WILDCARD;
* MAP_TYPE_PREFIX;
* MAP_TYPE_PWID.

Replace manually written function names with __func__.

VPLS signaling support.

This patch introduces full support for pseudowire signaling in ldpd(8),
including Control Word and Status TLV negotiation.

As of now it's not possible to configure a VPWS, but the signaling is
the same. In the future, when VPWS support is available in the kernel,
ldpd(8) can be extended to support VPWS with only a few modifications.

Limitations:
* No support for FEC 129, only FEC 128 (more widely deployed);
* No support for group withdraws (not widely deployed);
* No support for MAC withdraws (not widely deployed).

Related RFCs:
* RFC 3916: Requirements for Pseudo-Wire Emulation Edge-to-Edge (PWE3)
* RFC 3985: Pseudo Wire Emulation Edge-to-Edge (PWE3) Architecture
* RFC 4385: Pseudowire Emulation Edge-to-Edge (PWE3) Control Word for
Use over an MPLS PSN
* RFC 4446: IANA Allocations for Pseudowire Edge to Edge Emulation (PWE3)
* RFC 4447: Pseudowire Setup and Maintenance Using the Label Distribution
Protocol (LDP)
* RFC 4448: Encapsulation Methods for Transport of Ethernet over MPLS
Networks
* RFC 4905: Encapsulation Methods for Transport of Layer 2 Frames over
MPLS Networks
* RFC 4906: Transport of Layer 2 Frames Over MPLS

ok claudio@

Record all fields of the received label mappings.

Since we implement the Liberal Label Retention mode, we need to record
all fields of the received label mappings so the messages can be processed
later when there is a matching nexthop for the advertised FECs.

This will be important when we implement VPLS because we need to retain
information like the pseudowire's interface MTU and Group ID.

ok claudio@

Rename structures and functions to be more generic.

LDP work with FECs, where a FEC can be a prefix, a pseudowire and so on.

ok claudio@

Rework label mapping algorithms to be more in line with the RFC.

This patch presents a thoroughly review of the label mapping
algorithms. Most of the changes are minor bug fixes in the handling of
received label messages.

Additional improvements:
* Add a few more references to the Appendix A of the RFC5036 ("LDP
Label Distribution Procedures") into the code;
* Add full multipath support;
* Send label withdraws when appropriate;
* Add label withdraw/release wildcard support.

NOTE: As a result of implementing only the "Liberal Label Retention" and
"Downstream Unsolicited" modes, we will never send a label request
("Request Never"). And that means that we can ignore the following
notification messages: "Label Request Aborted", "No Label Resources",
"No Route" and "Label Resources Available". The following algorithms
mentioned in the RFC can also be ignored: "Timeout of Deferred Label
Request", "Detect Local Label Resources Have Become Available" and
"Receive Label Abort Request".

Now, considering that we only support one combination of all modes of
operation, we can say that we have an almost complete implementation of
the protocol.

ok claudio@

Remove incomplete support for unnecessary modes of operation.

LDP has several modes of operation, it was designed in that way so it
could run on legacy equipment like ATM/FR switches with very strict
memory limitations.

For modern hardware there's no point on using either the "Conservative
Label Retention" or "Downstream On Demand" modes of operation since they
save memory at cost of blackholing traffic when routing changes. Major
vendors implement only the "Liberal Label Retention" and "Downstream
Unsolicited" modes for non ATM/FR hardware. Let's do that too.

As for using either "Independent Control" or "Ordered Control", let's
stick with the first option mainly because it's easier to implement
and because it doesn't really matter which control mode is used. For
reference, Cisco implements only "Independent Control" and Juniper only
"Ordered Control". Both modes are interoperable.

The point of supporting only one combination of all modes of operation
is that it will allow for the writing of a simpler code without removing
useful functionality.

ok claudio@

Uninstall associated label bindings when a neighbor is down.

ok claudio@

Rework kroute.c to send only the best routes to lde.

This is major rework of the kroute.c code. The idea is remove complexity
from the lde process by making kroute.c advertise only the lowest priority
routes of each prefix.

kroute.c now keeps track of all routes using three different structures:
kroute_prefix, kroute_priority and kroute_node.

kroute_prefix represents a prefix and contains an ordered list of
priorities (kroute_priority) and for each priority there is a list of
nexthops (kroute_node). Arranging the routes using these three structures
allows for the writing of a simpler code, easier to understand.

Whenever a route is removed, if there's another route for the same prefix,
but with a lower priority, this route is immediately sent to lde.

Additional fixes:
* On RTM_CHANGE, remove the old route before installing the new one;
* On IMSG_CTL_KROUTE_ADDR, show all nexthops for multpath routes;

Typos: equalivant, fucntion, libary.

Show the full LIB in the "ldpctl show lib" command.

The LIB is a table where the router keeps all known MPLS labels. So,
we should loop over all the received label mappings from all neighbors
to show the full LIB.

The lde_nbr_is_nexthop() function was introduced to verify if a lib
entry is supposed to be installed in the fib (according to the fib entry's
nexthop and the addresses advertised by the lib entry's nexthop). This is
better than keeping track of lib<->fib entries with pointers and back
pointers because it keeps the lib/fib structures independent of each
other, which in turn makes the code less prone to bugs.

OK claudio@

Fix whitespace and other style issues.
OK claudio@

Advertise the implicit-null label for routes attached to loopback
interfaces to guarantee PHP. With this 'fib-update no' is not totaly
broken because of missing mappings for the loopbacks.
Diff by Renato Westphal

Only consider pathes with highest priority when replying to label
requests. Else a priority inversion may happen that would build
label switching pathes that use inactive routes.
OK michele@

Change lde_check_request(), lde_check_mapping(), lde_send_labelmapping(),
lde_send_labelrequest(), and lde_nbr_do_mappings() to follow the
algorithms defined in Appendix A of RFC 5036. Added comments and
markers for better understanding and to find missing bits.
OK michele@

Start implementing the missing lablemapping messages in the LDE and
fix the existing ones to correctly track outstanding request and
sent / recv mappings.
Looks good to michele@

Fix format string that was not changed after the log_fec introduction.

Fix a memory leak in an error path. Found and diff by Igor Zinovik.
OK michele@

Make it possible to store multiple LSP to a FEC. This is another step to
handle multipath routes in MPLS.
Looks good to michele@

Kill IMSG_KLABEL_INSERT and all the related functions around it.
IMSG_KLABEL_CHANGE is smart enough to know when something is a change
or an insert.

Switch prefix in struct map to a struct in_addr instead of a u_int32_t.
Needed for further clean etc.

Move the logging of FEC changes to the LDE and print the FEC and label
information. This is more useful.
OK michele

Store all labels in ldpd in host byte order without any additional shifting.
Add the necessary ntohl() and shifts in various places and cleanup the byte
order mess we had before. michele@ agrees.

Start reworking the LDE. Implement a FEC RB tree that can be used for the
route table and the per neighbor request and mapping lists.
The received and sent mappings are added to the per neighbor RB tree and
additionally linked to the route table. This makes lookups, etc. a lot
easier. While there flip the neighbor hash list over to a RB tree.
OK michele@

Kill a bogus bzero() and introduce an empty lde_check_release().
That function will be needed soon.

Remove yet another ospf leftover that is not needed here. This time
neighbor self and all the madness surrounding this amazing concept.
LDP is not self aware so there is no need for this.
OK michele@

No need to do a rt_find() twice.

When a prefix has a implicit null label associated, force pop operation.
This allow us to correcly do penultimate hop popping.

From Thomas Habets. Thanks.
ok claudio@

Rework the kroute code by stealing some code from ospfd and massaging it
a lot more. Main reason for this is to add priority support. Additionally
add some additional NO_LABEL fixes.
OK michele@

One more substitution of label 0 with NO_LABEL.

ok claudio@

Whitespaces cleanup.

NO_LABEL (instead of zero) must be used to mean that no labels are associated
with the prefix.

ok claudio@

If a neighbor goes down we need to cleanup the LIB from all FEC that point
via that neighbor. Fixes a use after free and an additional NULL dereference
in a log_debug is fixed as well.
OK michele

Don't fatalx() when a static route is deleted.

ok claudio@

Implement section A.1.6 of RFC 5036: "Recognize new FEC".

When a new prefix is learnt, redistribute the local label associated with
it to the other connected peers.

ok claudio@

In the "ldpctl show lib" output print every known label and make clear if it
is currently in use or not.

ok claudio@

When a route is deleted, ldpd should remove labels associated with it from
lfib (the kernel lib) but not from the lib. These could be used later on when
the route come back.

ok claudio@

"ldpctl show lib" output cleanup.

- Show only the remote/local labels of the prefixes currently present
in fib.

- Write a "-" instead of "0" when a remote label is not present (the
prefix is directly connected). It avoids confusion with explicit null label.

ok claudio@

Detect nexthop change.
React installing the label associated with the new nexthop
in the kernel routing table.

ok claudio@

When operating in liberal mode, retain labels even if they aren't learnt
from current nexthop.

ok laurent@

Correctly send notification messages when errors occur.

ok claudio@ laurent@

Welcome ldpd, the Label Distribution Protocol daemon.
Built using the imsg/three process framework, its main aim
is to redistribute MPLS labels between peers.

Right now it has some really basic functionalities,
the basic protocol works and peers are able to exchange
labels and insert them in the kernel.
It still does not react to changes of topology.

Not yet connected to the builds.

ok claudio@ deraadt@

spelling fixes; from paul tagliamonte
any parts of his diff not taken are noted on tech

Implement RFC 5919 (LDP End-of-LIB).

Implement RFC 6667 (Typed Wildcard FEC for PWid).

Implement RFC 5918 (Typed Wildcard FEC).

Implement support for PWid group wildcards.

This was missing from our original RFC 4447 VPLS implementation. Now
ldpd understands group wildcards as mandated by the RFC, but we still
don't send them ourselves. I can't see any case in which sending a group
wildcard would be useful, but nonetheless this patch provides a function
called lde_send_labelwithdraw_pwid_wcard() which is ready to be used in
the future anytime we feel like it might be useful.

Fix processing of Label Withdraw messages.

Whenever we receive a Label Withdraw message with an optional Label
TLV, we should check if this label matches the label previously
received from this neighbor for this FEC. If they don't match then we
shouldn't uninstall the previous label from the kernel. This fixes a
misinterpretation from the "Receive Label Withdraw" algorithm described
in the A.1.5 section of RFC 5036.

Also, simplify the check of pending withdraws in lde_check_release()
and lde_check_release_wcard().

Minor tweaks.

More renaming and whitespace cleanup.

No binary change after "strip -s".

Several minor tweaks.

Remove TODO comments about loop detection.

LDP loop detection is only necessary for ATM LSRs running in cell mode. We
are never going to implement this "feature".

Also, add two more comments in lde_check_request().

Fix small LIB<->LFIB synchronization issue.

ldpd operates only with the best routes of each IP prefix. In other words,
the routes with the lowest priorities.

When a route with a better priority is detected (possibly with a different
nexthop), we should uninstall the labels from the "old" routes and try
to install a new label for the new route (if there's one available in
the LIB).

In this specific case, ldpd was failing to uninstall the labels from the
old routes because it wasn't keeping track of each route's priority in
lde. With this missing bit of information, the parent process had no way
to get the correct label to uninstall when processing a IMSG_KLABEL_DELETE
message.

Add missing ntohl() when recording a label request.

Fixes the following ANVL LDP tests: 1.5 and 9.4.

Update copyright information.

Remove superfluous includes.

Make functions and variables static whenever possible.

The benefits of this include:
* clean up of the ldpd global namespace;
* improved readability;
* more hints to the compiler/linker to generate more efficient code.

Whenever possible, move global static variables to a smaller scope
(function).

All extern variables are now declared in header files to avoid unnecessary
duplication.

This patch also cleans up the indentation of all function prototypes
and global variables.

Add support for IPv6 (RFC 7552).

This includes:
* Full compliance to RFC 7552;
* Support for MD5 on LDPov6 sessions;
* Support for pseudowires over IPv6 LSPs (we're probably the world's
first implementation doing this);
* Support for the IPv6 explicit-null label;
* Knob to specify the prefered address-family for TCP transport
connections;
* Knob to use cisco non-compliant format to send and interpret the
Dual-Stack capability TLV.

Assorted fixes and small cleanup.

Nothing really interesting here.

Introduce a garbage collector for dead entries in the LIB.

If we lose a route and all of its associated labels, then there's no
point on keeping an entry for it in the LIB.

Simplify label allocation.

Whenever we lose a route, unset the local label. If the same route is
learned again later, allocate a new label for it. No need to be economic
with labels, it's not worth the added complexity.

Reuse lde_address_find() inside lde_check_mapping().

Copy structs by assignment instead of memcpy.

Copying by straight assignment is shorter, easier to read and has a
higher level of abstraction. We'll only avoid it when copying from an
unaligned source (e.g., network buffers).

In addition, copy in_addr structs directly.

Fix mess caused by my commit script.

I screwed up everything... trying to fix now.

Rework L2VPN code.

Fix bug in the processing of label withdraws and releases.

The F_MAP_PW_ID flag is only set for PW-ID mappings, which means that we
were ignoring all label withdraws and label releases for non PW-ID FECs.

Make send_labelmessage() more robust.

Immediately return from this function if the given list of mappings
is empty. This way we have more freedom when sending label messages,
not having to care with corner cases.

Fix byte order issues with notification messages.

Remove unnecessary break statements.

More renaming.

Rename a few more things to improve readability.

* s/F_PW_CONTROLWORD_CONF/F_PW_CWORD_CONF/ (shorter)
* s/F_PW_CONTROLWORD/F_PW_CWORD/ (shorter)
* s/LDPD_FLAG_*/F_LDPD_*/ (consistency)
* s/lde_nbr_address/lde_addr/ (shorter)
* s/ldp_discovery_socket/ldp_disc_socket/ (shorter)
* s/ldp_ediscovery_socket/ldp_edisc_socket/ (shorter)
* s/ldp_sendboth/main_imsg_compose_both/ (consistency)
* s/cons/total/ (makes more sense)
* s/kaddr/ka/ (consistency with remaining code)
* Always use 'ln' for lde_nbrs (consistency)

Rename a few constants to avoid confusion.

In ldpd we have the map structure, which is used to represent a label message,
and the fec structure, used to store FECs in the LIB.

As of now, ldpd supports two type of FECs:
* IPv4 prefix (FEC_TYPE_IPV4);
* PWID (FEC_TYPE_PWID).

For the label messages, the following contants were being used:
* FEC_WILDCARD;
* FEC_PREFIX (IPv4 or IPv6);
* FEC_PWID.

Since these contants have similar names to the previous ones, rename
them to:
* MAP_TYPE_WILDCARD;
* MAP_TYPE_PREFIX;
* MAP_TYPE_PWID.

Replace manually written function names with __func__.

VPLS signaling support.

This patch introduces full support for pseudowire signaling in ldpd(8),
including Control Word and Status TLV negotiation.

As of now it's not possible to configure a VPWS, but the signaling is
the same. In the future, when VPWS support is available in the kernel,
ldpd(8) can be extended to support VPWS with only a few modifications.

Limitations:
* No support for FEC 129, only FEC 128 (more widely deployed);
* No support for group withdraws (not widely deployed);
* No support for MAC withdraws (not widely deployed).

Related RFCs:
* RFC 3916: Requirements for Pseudo-Wire Emulation Edge-to-Edge (PWE3)
* RFC 3985: Pseudo Wire Emulation Edge-to-Edge (PWE3) Architecture
* RFC 4385: Pseudowire Emulation Edge-to-Edge (PWE3) Control Word for
Use over an MPLS PSN
* RFC 4446: IANA Allocations for Pseudowire Edge to Edge Emulation (PWE3)
* RFC 4447: Pseudowire Setup and Maintenance Using the Label Distribution
Protocol (LDP)
* RFC 4448: Encapsulation Methods for Transport of Ethernet over MPLS
Networks
* RFC 4905: Encapsulation Methods for Transport of Layer 2 Frames over
MPLS Networks
* RFC 4906: Transport of Layer 2 Frames Over MPLS

ok claudio@

Record all fields of the received label mappings.

Since we implement the Liberal Label Retention mode, we need to record
all fields of the received label mappings so the messages can be processed
later when there is a matching nexthop for the advertised FECs.

This will be important when we implement VPLS because we need to retain
information like the pseudowire's interface MTU and Group ID.

ok claudio@

Rename structures and functions to be more generic.

LDP work with FECs, where a FEC can be a prefix, a pseudowire and so on.

ok claudio@

Rework label mapping algorithms to be more in line with the RFC.

This patch presents a thoroughly review of the label mapping
algorithms. Most of the changes are minor bug fixes in the handling of
received label messages.

Additional improvements:
* Add a few more references to the Appendix A of the RFC5036 ("LDP
Label Distribution Procedures") into the code;
* Add full multipath support;
* Send label withdraws when appropriate;
* Add label withdraw/release wildcard support.

NOTE: As a result of implementing only the "Liberal Label Retention" and
"Downstream Unsolicited" modes, we will never send a label request
("Request Never"). And that means that we can ignore the following
notification messages: "Label Request Aborted", "No Label Resources",
"No Route" and "Label Resources Available". The following algorithms
mentioned in the RFC can also be ignored: "Timeout of Deferred Label
Request", "Detect Local Label Resources Have Become Available" and
"Receive Label Abort Request".

Now, considering that we only support one combination of all modes of
operation, we can say that we have an almost complete implementation of
the protocol.

ok claudio@

Remove incomplete support for unnecessary modes of operation.

LDP has several modes of operation, it was designed in that way so it
could run on legacy equipment like ATM/FR switches with very strict
memory limitations.

For modern hardware there's no point on using either the "Conservative
Label Retention" or "Downstream On Demand" modes of operation since they
save memory at cost of blackholing traffic when routing changes. Major
vendors implement only the "Liberal Label Retention" and "Downstream
Unsolicited" modes for non ATM/FR hardware. Let's do that too.

As for using either "Independent Control" or "Ordered Control", let's
stick with the first option mainly because it's easier to implement
and because it doesn't really matter which control mode is used. For
reference, Cisco implements only "Independent Control" and Juniper only
"Ordered Control". Both modes are interoperable.

The point of supporting only one combination of all modes of operation
is that it will allow for the writing of a simpler code without removing
useful functionality.

ok claudio@

Uninstall associated label bindings when a neighbor is down.

ok claudio@

Rework kroute.c to send only the best routes to lde.

This is major rework of the kroute.c code. The idea is remove complexity
from the lde process by making kroute.c advertise only the lowest priority
routes of each prefix.

kroute.c now keeps track of all routes using three different structures:
kroute_prefix, kroute_priority and kroute_node.

kroute_prefix represents a prefix and contains an ordered list of
priorities (kroute_priority) and for each priority there is a list of
nexthops (kroute_node). Arranging the routes using these three structures
allows for the writing of a simpler code, easier to understand.

Whenever a route is removed, if there's another route for the same prefix,
but with a lower priority, this route is immediately sent to lde.

Additional fixes:
* On RTM_CHANGE, remove the old route before installing the new one;
* On IMSG_CTL_KROUTE_ADDR, show all nexthops for multpath routes;

Typos: equalivant, fucntion, libary.

Show the full LIB in the "ldpctl show lib" command.

The LIB is a table where the router keeps all known MPLS labels. So,
we should loop over all the received label mappings from all neighbors
to show the full LIB.

The lde_nbr_is_nexthop() function was introduced to verify if a lib
entry is supposed to be installed in the fib (according to the fib entry's
nexthop and the addresses advertised by the lib entry's nexthop). This is
better than keeping track of lib<->fib entries with pointers and back
pointers because it keeps the lib/fib structures independent of each
other, which in turn makes the code less prone to bugs.

OK claudio@

Fix whitespace and other style issues.
OK claudio@

Advertise the implicit-null label for routes attached to loopback
interfaces to guarantee PHP. With this 'fib-update no' is not totaly
broken because of missing mappings for the loopbacks.
Diff by Renato Westphal

Only consider pathes with highest priority when replying to label
requests. Else a priority inversion may happen that would build
label switching pathes that use inactive routes.
OK michele@

Change lde_check_request(), lde_check_mapping(), lde_send_labelmapping(),
lde_send_labelrequest(), and lde_nbr_do_mappings() to follow the
algorithms defined in Appendix A of RFC 5036. Added comments and
markers for better understanding and to find missing bits.
OK michele@

Start implementing the missing lablemapping messages in the LDE and
fix the existing ones to correctly track outstanding request and
sent / recv mappings.
Looks good to michele@

Fix format string that was not changed after the log_fec introduction.

Fix a memory leak in an error path. Found and diff by Igor Zinovik.
OK michele@

Make it possible to store multiple LSP to a FEC. This is another step to
handle multipath routes in MPLS.
Looks good to michele@

Kill IMSG_KLABEL_INSERT and all the related functions around it.
IMSG_KLABEL_CHANGE is smart enough to know when something is a change
or an insert.

Switch prefix in struct map to a struct in_addr instead of a u_int32_t.
Needed for further clean etc.

Move the logging of FEC changes to the LDE and print the FEC and label
information. This is more useful.
OK michele

Store all labels in ldpd in host byte order without any additional shifting.
Add the necessary ntohl() and shifts in various places and cleanup the byte
order mess we had before. michele@ agrees.

Start reworking the LDE. Implement a FEC RB tree that can be used for the
route table and the per neighbor request and mapping lists.
The received and sent mappings are added to the per neighbor RB tree and
additionally linked to the route table. This makes lookups, etc. a lot
easier. While there flip the neighbor hash list over to a RB tree.
OK michele@

Kill a bogus bzero() and introduce an empty lde_check_release().
That function will be needed soon.

Remove yet another ospf leftover that is not needed here. This time
neighbor self and all the madness surrounding this amazing concept.
LDP is not self aware so there is no need for this.
OK michele@

No need to do a rt_find() twice.

When a prefix has a implicit null label associated, force pop operation.
This allow us to correcly do penultimate hop popping.

From Thomas Habets. Thanks.
ok claudio@

Rework the kroute code by stealing some code from ospfd and massaging it
a lot more. Main reason for this is to add priority support. Additionally
add some additional NO_LABEL fixes.
OK michele@

One more substitution of label 0 with NO_LABEL.

ok claudio@

Whitespaces cleanup.

NO_LABEL (instead of zero) must be used to mean that no labels are associated
with the prefix.

ok claudio@

If a neighbor goes down we need to cleanup the LIB from all FEC that point
via that neighbor. Fixes a use after free and an additional NULL dereference
in a log_debug is fixed as well.
OK michele

Don't fatalx() when a static route is deleted.

ok claudio@

Implement section A.1.6 of RFC 5036: "Recognize new FEC".

When a new prefix is learnt, redistribute the local label associated with
it to the other connected peers.

ok claudio@

In the "ldpctl show lib" output print every known label and make clear if it
is currently in use or not.

ok claudio@

When a route is deleted, ldpd should remove labels associated with it from
lfib (the kernel lib) but not from the lib. These could be used later on when
the route come back.

ok claudio@

"ldpctl show lib" output cleanup.

- Show only the remote/local labels of the prefixes currently present
in fib.

- Write a "-" instead of "0" when a remote label is not present (the
prefix is directly connected). It avoids confusion with explicit null label.

ok claudio@

Detect nexthop change.
React installing the label associated with the new nexthop
in the kernel routing table.

ok claudio@

When operating in liberal mode, retain labels even if they aren't learnt
from current nexthop.

ok laurent@

Correctly send notification messages when errors occur.

ok claudio@ laurent@

Welcome ldpd, the Label Distribution Protocol daemon.
Built using the imsg/three process framework, its main aim
is to redistribute MPLS labels between peers.

Right now it has some really basic functionalities,
the basic protocol works and peers are able to exchange
labels and insert them in the kernel.
It still does not react to changes of topology.

Not yet connected to the builds.

ok claudio@ deraadt@

Implement RFC 5919 (LDP End-of-LIB).

Implement RFC 6667 (Typed Wildcard FEC for PWid).

Implement RFC 5918 (Typed Wildcard FEC).

Implement support for PWid group wildcards.

This was missing from our original RFC 4447 VPLS implementation. Now
ldpd understands group wildcards as mandated by the RFC, but we still
don't send them ourselves. I can't see any case in which sending a group
wildcard would be useful, but nonetheless this patch provides a function
called lde_send_labelwithdraw_pwid_wcard() which is ready to be used in
the future anytime we feel like it might be useful.

Fix processing of Label Withdraw messages.

Whenever we receive a Label Withdraw message with an optional Label
TLV, we should check if this label matches the label previously
received from this neighbor for this FEC. If they don't match then we
shouldn't uninstall the previous label from the kernel. This fixes a
misinterpretation from the "Receive Label Withdraw" algorithm described
in the A.1.5 section of RFC 5036.

Also, simplify the check of pending withdraws in lde_check_release()
and lde_check_release_wcard().

Minor tweaks.

More renaming and whitespace cleanup.

No binary change after "strip -s".

Several minor tweaks.

Remove TODO comments about loop detection.

LDP loop detection is only necessary for ATM LSRs running in cell mode. We
are never going to implement this "feature".

Also, add two more comments in lde_check_request().

Fix small LIB<->LFIB synchronization issue.

ldpd operates only with the best routes of each IP prefix. In other words,
the routes with the lowest priorities.

When a route with a better priority is detected (possibly with a different
nexthop), we should uninstall the labels from the "old" routes and try
to install a new label for the new route (if there's one available in
the LIB).

In this specific case, ldpd was failing to uninstall the labels from the
old routes because it wasn't keeping track of each route's priority in
lde. With this missing bit of information, the parent process had no way
to get the correct label to uninstall when processing a IMSG_KLABEL_DELETE
message.

Add missing ntohl() when recording a label request.

Fixes the following ANVL LDP tests: 1.5 and 9.4.

Update copyright information.

Remove superfluous includes.

Make functions and variables static whenever possible.

The benefits of this include:
* clean up of the ldpd global namespace;
* improved readability;
* more hints to the compiler/linker to generate more efficient code.

Whenever possible, move global static variables to a smaller scope
(function).

All extern variables are now declared in header files to avoid unnecessary
duplication.

This patch also cleans up the indentation of all function prototypes
and global variables.

Add support for IPv6 (RFC 7552).

This includes:
* Full compliance to RFC 7552;
* Support for MD5 on LDPov6 sessions;
* Support for pseudowires over IPv6 LSPs (we're probably the world's
first implementation doing this);
* Support for the IPv6 explicit-null label;
* Knob to specify the prefered address-family for TCP transport
connections;
* Knob to use cisco non-compliant format to send and interpret the
Dual-Stack capability TLV.

Assorted fixes and small cleanup.

Nothing really interesting here.

Introduce a garbage collector for dead entries in the LIB.

If we lose a route and all of its associated labels, then there's no
point on keeping an entry for it in the LIB.

Simplify label allocation.

Whenever we lose a route, unset the local label. If the same route is
learned again later, allocate a new label for it. No need to be economic
with labels, it's not worth the added complexity.

Reuse lde_address_find() inside lde_check_mapping().

Copy structs by assignment instead of memcpy.

Copying by straight assignment is shorter, easier to read and has a
higher level of abstraction. We'll only avoid it when copying from an
unaligned source (e.g., network buffers).

In addition, copy in_addr structs directly.

Fix mess caused by my commit script.

I screwed up everything... trying to fix now.

Rework L2VPN code.

Fix bug in the processing of label withdraws and releases.

The F_MAP_PW_ID flag is only set for PW-ID mappings, which means that we
were ignoring all label withdraws and label releases for non PW-ID FECs.

Make send_labelmessage() more robust.

Immediately return from this function if the given list of mappings
is empty. This way we have more freedom when sending label messages,
not having to care with corner cases.

Fix byte order issues with notification messages.

Remove unnecessary break statements.

More renaming.

Rename a few more things to improve readability.

* s/F_PW_CONTROLWORD_CONF/F_PW_CWORD_CONF/ (shorter)
* s/F_PW_CONTROLWORD/F_PW_CWORD/ (shorter)
* s/LDPD_FLAG_*/F_LDPD_*/ (consistency)
* s/lde_nbr_address/lde_addr/ (shorter)
* s/ldp_discovery_socket/ldp_disc_socket/ (shorter)
* s/ldp_ediscovery_socket/ldp_edisc_socket/ (shorter)
* s/ldp_sendboth/main_imsg_compose_both/ (consistency)
* s/cons/total/ (makes more sense)
* s/kaddr/ka/ (consistency with remaining code)
* Always use 'ln' for lde_nbrs (consistency)

Rename a few constants to avoid confusion.

In ldpd we have the map structure, which is used to represent a label message,
and the fec structure, used to store FECs in the LIB.

As of now, ldpd supports two type of FECs:
* IPv4 prefix (FEC_TYPE_IPV4);
* PWID (FEC_TYPE_PWID).

For the label messages, the following contants were being used:
* FEC_WILDCARD;
* FEC_PREFIX (IPv4 or IPv6);
* FEC_PWID.

Since these contants have similar names to the previous ones, rename
them to:
* MAP_TYPE_WILDCARD;
* MAP_TYPE_PREFIX;
* MAP_TYPE_PWID.

Replace manually written function names with __func__.

VPLS signaling support.

This patch introduces full support for pseudowire signaling in ldpd(8),
including Control Word and Status TLV negotiation.

As of now it's not possible to configure a VPWS, but the signaling is
the same. In the future, when VPWS support is available in the kernel,
ldpd(8) can be extended to support VPWS with only a few modifications.

Limitations:
* No support for FEC 129, only FEC 128 (more widely deployed);
* No support for group withdraws (not widely deployed);
* No support for MAC withdraws (not widely deployed).

Related RFCs:
* RFC 3916: Requirements for Pseudo-Wire Emulation Edge-to-Edge (PWE3)
* RFC 3985: Pseudo Wire Emulation Edge-to-Edge (PWE3) Architecture
* RFC 4385: Pseudowire Emulation Edge-to-Edge (PWE3) Control Word for
Use over an MPLS PSN
* RFC 4446: IANA Allocations for Pseudowire Edge to Edge Emulation (PWE3)
* RFC 4447: Pseudowire Setup and Maintenance Using the Label Distribution
Protocol (LDP)
* RFC 4448: Encapsulation Methods for Transport of Ethernet over MPLS
Networks
* RFC 4905: Encapsulation Methods for Transport of Layer 2 Frames over
MPLS Networks
* RFC 4906: Transport of Layer 2 Frames Over MPLS

ok claudio@

Record all fields of the received label mappings.

Since we implement the Liberal Label Retention mode, we need to record
all fields of the received label mappings so the messages can be processed
later when there is a matching nexthop for the advertised FECs.

This will be important when we implement VPLS because we need to retain
information like the pseudowire's interface MTU and Group ID.

ok claudio@

Rename structures and functions to be more generic.

LDP work with FECs, where a FEC can be a prefix, a pseudowire and so on.

ok claudio@

Rework label mapping algorithms to be more in line with the RFC.

This patch presents a thoroughly review of the label mapping
algorithms. Most of the changes are minor bug fixes in the handling of
received label messages.

Additional improvements:
* Add a few more references to the Appendix A of the RFC5036 ("LDP
Label Distribution Procedures") into the code;
* Add full multipath support;
* Send label withdraws when appropriate;
* Add label withdraw/release wildcard support.

NOTE: As a result of implementing only the "Liberal Label Retention" and
"Downstream Unsolicited" modes, we will never send a label request
("Request Never"). And that means that we can ignore the following
notification messages: "Label Request Aborted", "No Label Resources",
"No Route" and "Label Resources Available". The following algorithms
mentioned in the RFC can also be ignored: "Timeout of Deferred Label
Request", "Detect Local Label Resources Have Become Available" and
"Receive Label Abort Request".

Now, considering that we only support one combination of all modes of
operation, we can say that we have an almost complete implementation of
the protocol.

ok claudio@

Remove incomplete support for unnecessary modes of operation.

LDP has several modes of operation, it was designed in that way so it
could run on legacy equipment like ATM/FR switches with very strict
memory limitations.

For modern hardware there's no point on using either the "Conservative
Label Retention" or "Downstream On Demand" modes of operation since they
save memory at cost of blackholing traffic when routing changes. Major
vendors implement only the "Liberal Label Retention" and "Downstream
Unsolicited" modes for non ATM/FR hardware. Let's do that too.

As for using either "Independent Control" or "Ordered Control", let's
stick with the first option mainly because it's easier to implement
and because it doesn't really matter which control mode is used. For
reference, Cisco implements only "Independent Control" and Juniper only
"Ordered Control". Both modes are interoperable.

The point of supporting only one combination of all modes of operation
is that it will allow for the writing of a simpler code without removing
useful functionality.

ok claudio@

Uninstall associated label bindings when a neighbor is down.

ok claudio@

Rework kroute.c to send only the best routes to lde.

This is major rework of the kroute.c code. The idea is remove complexity
from the lde process by making kroute.c advertise only the lowest priority
routes of each prefix.

kroute.c now keeps track of all routes using three different structures:
kroute_prefix, kroute_priority and kroute_node.

kroute_prefix represents a prefix and contains an ordered list of
priorities (kroute_priority) and for each priority there is a list of
nexthops (kroute_node). Arranging the routes using these three structures
allows for the writing of a simpler code, easier to understand.

Whenever a route is removed, if there's another route for the same prefix,
but with a lower priority, this route is immediately sent to lde.

Additional fixes:
* On RTM_CHANGE, remove the old route before installing the new one;
* On IMSG_CTL_KROUTE_ADDR, show all nexthops for multpath routes;

Typos: equalivant, fucntion, libary.

Show the full LIB in the "ldpctl show lib" command.

The LIB is a table where the router keeps all known MPLS labels. So,
we should loop over all the received label mappings from all neighbors
to show the full LIB.

The lde_nbr_is_nexthop() function was introduced to verify if a lib
entry is supposed to be installed in the fib (according to the fib entry's
nexthop and the addresses advertised by the lib entry's nexthop). This is
better than keeping track of lib<->fib entries with pointers and back
pointers because it keeps the lib/fib structures independent of each
other, which in turn makes the code less prone to bugs.

OK claudio@

Fix whitespace and other style issues.
OK claudio@

Advertise the implicit-null label for routes attached to loopback
interfaces to guarantee PHP. With this 'fib-update no' is not totaly
broken because of missing mappings for the loopbacks.
Diff by Renato Westphal

Only consider pathes with highest priority when replying to label
requests. Else a priority inversion may happen that would build
label switching pathes that use inactive routes.
OK michele@

Change lde_check_request(), lde_check_mapping(), lde_send_labelmapping(),
lde_send_labelrequest(), and lde_nbr_do_mappings() to follow the
algorithms defined in Appendix A of RFC 5036. Added comments and
markers for better understanding and to find missing bits.
OK michele@

Start implementing the missing lablemapping messages in the LDE and
fix the existing ones to correctly track outstanding request and
sent / recv mappings.
Looks good to michele@

Fix format string that was not changed after the log_fec introduction.

Fix a memory leak in an error path. Found and diff by Igor Zinovik.
OK michele@

Make it possible to store multiple LSP to a FEC. This is another step to
handle multipath routes in MPLS.
Looks good to michele@

Kill IMSG_KLABEL_INSERT and all the related functions around it.
IMSG_KLABEL_CHANGE is smart enough to know when something is a change
or an insert.

Switch prefix in struct map to a struct in_addr instead of a u_int32_t.
Needed for further clean etc.

Move the logging of FEC changes to the LDE and print the FEC and label
information. This is more useful.
OK michele

Store all labels in ldpd in host byte order without any additional shifting.
Add the necessary ntohl() and shifts in various places and cleanup the byte
order mess we had before. michele@ agrees.

Start reworking the LDE. Implement a FEC RB tree that can be used for the
route table and the per neighbor request and mapping lists.
The received and sent mappings are added to the per neighbor RB tree and
additionally linked to the route table. This makes lookups, etc. a lot
easier. While there flip the neighbor hash list over to a RB tree.
OK michele@

Kill a bogus bzero() and introduce an empty lde_check_release().
That function will be needed soon.

Remove yet another ospf leftover that is not needed here. This time
neighbor self and all the madness surrounding this amazing concept.
LDP is not self aware so there is no need for this.
OK michele@

No need to do a rt_find() twice.

When a prefix has a implicit null label associated, force pop operation.
This allow us to correcly do penultimate hop popping.

From Thomas Habets. Thanks.
ok claudio@

Rework the kroute code by stealing some code from ospfd and massaging it
a lot more. Main reason for this is to add priority support. Additionally
add some additional NO_LABEL fixes.
OK michele@

One more substitution of label 0 with NO_LABEL.

ok claudio@

Whitespaces cleanup.

NO_LABEL (instead of zero) must be used to mean that no labels are associated
with the prefix.

ok claudio@

If a neighbor goes down we need to cleanup the LIB from all FEC that point
via that neighbor. Fixes a use after free and an additional NULL dereference
in a log_debug is fixed as well.
OK michele

Don't fatalx() when a static route is deleted.

ok claudio@

Implement section A.1.6 of RFC 5036: "Recognize new FEC".

When a new prefix is learnt, redistribute the local label associated with
it to the other connected peers.

ok claudio@

In the "ldpctl show lib" output print every known label and make clear if it
is currently in use or not.

ok claudio@

When a route is deleted, ldpd should remove labels associated with it from
lfib (the kernel lib) but not from the lib. These could be used later on when
the route come back.

ok claudio@

"ldpctl show lib" output cleanup.

- Show only the remote/local labels of the prefixes currently present
in fib.

- Write a "-" instead of "0" when a remote label is not present (the
prefix is directly connected). It avoids confusion with explicit null label.

ok claudio@

Detect nexthop change.
React installing the label associated with the new nexthop
in the kernel routing table.

ok claudio@

When operating in liberal mode, retain labels even if they aren't learnt
from current nexthop.

ok laurent@

Correctly send notification messages when errors occur.

ok claudio@ laurent@

Welcome ldpd, the Label Distribution Protocol daemon.
Built using the imsg/three process framework, its main aim
is to redistribute MPLS labels between peers.

Right now it has some really basic functionalities,
the basic protocol works and peers are able to exchange
labels and insert them in the kernel.
It still does not react to changes of topology.

Not yet connected to the builds.

ok claudio@ deraadt@