ASPA validation table

The aspa_table is an abstract data structure to organize the validated Autonomous System Provider Authorization data received from an RPKI-RTR cache server. More...

Data Structures
struct	aspa_record
	ASPA Record Customer (Customer Autonomous Systen, CAS) authorizes a set of provider AS numbers. More...
struct	aspa_table
	ASPA Table. More...
struct	aspa_store_node
	A linked list storing the bond between a rtr_socket and an aspa_array . More...
struct	aspa_update_operation
	A struct describing a specific type of operation that should be performed using the attached ASPA record. More...
struct	aspa_update
	Computed ASPA update. More...

Macros
#define	ASPA_NOTIFY_NO_OPS   0
#define	ASPA_DBG1(a)   lrtr_dbg("ASPA: " a)

Typedefs
typedef void(*	aspa_update_fp) (struct aspa_table *aspa_table, const struct aspa_record record, const struct rtr_socket *rtr_socket, const enum aspa_operation_type operation_type)
	A function pointer that is called if an record was added to the aspa_table or was removed from the aspa_table.

Enumerations
enum	aspa_status { ASPA_SUCCESS = 0 , ASPA_ERROR = -1 , ASPA_DUPLICATE_RECORD = -2 , ASPA_RECORD_NOT_FOUND = -3 }
	Possible return values for aspa_* functions. More...
enum	aspa_direction { ASPA_UPSTREAM , ASPA_DOWNSTREAM }
enum	aspa_verification_result { ASPA_AS_PATH_UNKNOWN , ASPA_AS_PATH_INVALID , ASPA_AS_PATH_VALID }
	AS_PATH verification result. More...
enum	aspa_hop_result { ASPA_NO_ATTESTATION , ASPA_NOT_PROVIDER_PLUS , ASPA_PROVIDER_PLUS }

Functions
enum	__attribute__ ((__packed__)) aspa_operation_type
	An enum describing the type of operation the ASPA table should perform using any given ASPA record.
void	aspa_table_init (struct aspa_table *aspa_table, aspa_update_fp update_fp)
	Initializes the aspa_table struct.
void	aspa_table_free (struct aspa_table *aspa_table, bool notify)
	Frees the memory associated with the aspa_table.
enum aspa_status	aspa_table_src_remove (struct aspa_table *aspa_table, struct rtr_socket *rtr_socket, bool notify)
	Removes all records in the aspa_table that originated from the socket.
enum aspa_verification_result	aspa_verify_as_path (struct aspa_table *aspa_table, uint32_t as_path[], size_t len, enum aspa_direction direction)
	Verifies an AS_PATH .
size_t	aspa_collapse_as_path (uint32_t as_path[], size_t len)
	Collapses an AS_PATH in-place, replacing in-series repetitions with single occurences.
enum aspa_hop_result	aspa_check_hop (struct aspa_table *aspa_table, uint32_t customer_asn, uint32_t provider_asn)
	Checks a hop in the given AS_PATH.
enum aspa_status	aspa_table_src_replace (struct aspa_table *dst, struct aspa_table *src, struct rtr_socket *rtr_socket, bool notify_dst, bool notify_src)
	Replaces all ASPA records associated with the given socket with the records in the src table.
enum aspa_status	aspa_table_update_swap_in_compute (struct aspa_table *aspa_table, struct rtr_socket *rtr_socket, struct aspa_update_operation *operations, size_t count, struct aspa_update **update)
	Computes an update structure that can later be applied to the given ASPA table.
void	aspa_table_update_swap_in_apply (struct aspa_update **update)
	Applies the given update, as previously computed by aspa_table_update_swap_in_compute, releases memory allocated while computing the update and unlocks update lock.
void	aspa_table_update_swap_in_discard (struct aspa_update **update)
	Discards the given update, releases memory allocated while computing the update and unlocks update lock.
enum aspa_status	aspa_table_update_in_place (struct aspa_table *aspa_table, struct rtr_socket *rtr_socket, struct aspa_update_operation *operations, size_t count, struct aspa_update_operation **failed_operation)
	Updates the given ASPA table.
enum aspa_status	aspa_table_update_in_place_undo (struct aspa_table *aspa_table, struct rtr_socket *rtr_socket, struct aspa_update_operation *operations, size_t count, struct aspa_update_operation *failed_operation)
	Tries to undo operations up to failed_operation and then releases all operations.
void	aspa_table_update_in_place_cleanup (struct aspa_update_operation **operations, size_t count)
	Releases operations and unused provider arrays.

Detailed Description

The aspa_table is an abstract data structure to organize the validated Autonomous System Provider Authorization data received from an RPKI-RTR cache server.

The aspa_table is an abstract data structure to organize the validated Autonomous System Provider Authorization data received from an RPKI-RTR cache server.

Updating an ASPA table

ASPA tables implement aggregated updating using an array of 'add record' and 'remove record' operations – reducing iterations and memory allocations. E.g., these operations can be derived from a RTR cache response. Currently, two distinct update mechanisms are supported: Swap-In and In-Place updates. Use the macro ASPA_UPDATE_MECHANISM in rtr/packets.c to configure which implementation is used during syncing. The array of operations is effectively a diff to the table's previous state. This diff can be conveniently used to notify callers about changes once the update is applied.

Swap-In Update Mechanism

The ASPA table's Swap-In update mechanism avoids blocking callers who want to verify an AS_PATH (and therefore need read access to the table) while an update is in progress and removes the need for an undo mechanism in case the update to the ASPA table itself or some other action performed inbetween fails.

Performing an update using this mechanism involves these steps:

• Compute Update: Every time you want to update a given ASPA table, call aspa_table_update_swap_in_compute. This will create a new ASPA array, appending both existing records and new records. Everything needed to update the table is stored in an update structure.
• Apply Update or Discard Update: You either have to apply the update using aspa_table_update_swap_in_apply or discard it by calling aspa_table_update_swap_in_discard. This will either swap in the newly created ASPA array and notify clients about changes or discard and release data that's now unused.

The implementation guarantess no changes are made to the ASPA table between calling aspa_table_update_swap_in_compute and aspa_table_update_swap_in_apply or aspa_table_update_swap_in_discard.

In-Place Update Mechanism

The ASPA table's In-Place update mechanism involves in-place modifications to the array of records and an undo function that undoes changes made previously.

Performing an update using this mechanism involves these steps:

• Update: Every time you want to update a given ASPA table, call aspa_table_update_in_place. This will modify the ASPA array. If the update fails, failed_operation will be set to the operation where the error occurring.
• Undo Update: You may, but do not need to, undo the update using aspa_table_update_in_place_undo. This will undo all operations up to failed_operation or all operations.
• Clean Up: After computing the update you should go through a cleanup step using aspa_table_update_in_place_cleanup. This will deallocate provider arrays and other data created during the update that's now unused.

Special Cases

There're various cases that need to be handled appropriately by both implementations.

1. Add existing record: The caller attempts to add a record that's already present in the table (ASPA_DUPLICATE_RECORD).
2. Duplicate adds: The caller attempts to add two or more records with the same customer ASN (ASPA_DUPLICATE_RECORD).
3. Removal of unknown record: The caller attempts to remove a record from the table that doesn't exist (ASPA_RECORD_NOT_FOUND).
4. Duplicate removal: The caller attempts to remove a record twice or more (ASPA_RECORD_NOT_FOUND).
5. Complementary add/remove: The caller attempts to first add a record and then wants to remove the same record. This is equivalent to a no-op. ASPA_NOTIFY_NO_OPS (1 or 0) determines if clients are notified about these no-ops.

Implementation Details

Both update mechanism implementations tackle the beforementioned cases by first sorting the array of 'add' and 'remove' operations by their customer ASN stably. That is, 'add' and 'remove' operations dealing with matching customer ASNs will remain in the same order as they arrived. This makes checking for cases 2 - Duplicate Announcement and 4 - Duplicate Removal easy as possible duplicates are neighbors in the operations array. Ordering the operations also enables skipping annihilating operations as described in case 5 - Complementary Announcement/Withdrawal. Both implementations are comprised of a loop iterating over operations and a nested loop that handles records from the existing ASPA array with an ASN smaller than the current operation's ASN.

• If the record in the existing array and the current 'add' operation have a matching customer ASN, that's case 1 - Announcement of Existing Record.
• If the record in the existing array and the current 'remove' operation do not have a matching customer ASN, that's case 3 - Removal of Unknown Record.

Macro Definition Documentation

ASPA_DBG1

#define ASPA_DBG1

(

a

)

lrtr_dbg("ASPA: " a)

#include <rtrlib/aspa/aspa_private.h>

ASPA_NOTIFY_NO_OPS

#define ASPA_NOTIFY_NO_OPS   0

#include <rtrlib/aspa/aspa_private.h>

Typedef Documentation

aspa_update_fp

typedef void(* aspa_update_fp) (struct aspa_table *aspa_table, const struct aspa_record record, const struct rtr_socket *rtr_socket, const enum aspa_operation_type operation_type)

#include <rtrlib/aspa/aspa.h>

A function pointer that is called if an record was added to the aspa_table or was removed from the aspa_table.

Parameters

aspa_table	ASPA table which was updated.
record	ASPA record that was modified.
rtr_socket	The socket the record originated from
operation_type	The type of this operation.

Enumeration Type Documentation

aspa_direction

enum aspa_direction

#include <rtrlib/aspa/aspa.h>

Enumerator
ASPA_UPSTREAM
ASPA_DOWNSTREAM

aspa_hop_result

enum aspa_hop_result

#include <rtrlib/aspa/aspa_private.h>

Enumerator
ASPA_NO_ATTESTATION
ASPA_NOT_PROVIDER_PLUS
ASPA_PROVIDER_PLUS

aspa_status

enum aspa_status

#include <rtrlib/aspa/aspa.h>

Possible return values for aspa_* functions.

Enumerator
ASPA_SUCCESS	Operation was successful.
ASPA_ERROR	Error occurred.
ASPA_DUPLICATE_RECORD	The supplied aspa_record already exists in the aspa_table.
ASPA_RECORD_NOT_FOUND	aspa_record wasn't found in the aspa_table.

aspa_verification_result

enum aspa_verification_result

#include <rtrlib/aspa/aspa.h>

AS_PATH verification result.

Enumerator
ASPA_AS_PATH_UNKNOWN
ASPA_AS_PATH_INVALID
ASPA_AS_PATH_VALID

Function Documentation

__attribute__()

enum __attribute__

(

(__packed__)

)

#include <rtrlib/aspa/aspa.h>

An enum describing the type of operation the ASPA table should perform using any given ASPA record.

The existing record, identified by its customer ASN, shall be withdrawn from the ASPA table.

The new record, identified by its customer ASN, shall be added to the ASPA table.

aspa_check_hop()

enum aspa_hop_result aspa_check_hop	(	struct aspa_table *	aspa_table,
		uint32_t	customer_asn,
		uint32_t	provider_asn
	)

#include <rtrlib/aspa/aspa_private.h>

Checks a hop in the given AS_PATH.

Returns

aspa_hop_result .

aspa_collapse_as_path()

size_t aspa_collapse_as_path	(	uint32_t	as_path[],
		size_t	len
	)

#include <rtrlib/aspa/aspa.h>

Collapses an AS_PATH in-place, replacing in-series repetitions with single occurences.

Returns

Length of the given array.

aspa_table_free()

void aspa_table_free	(	struct aspa_table *	aspa_table,
		bool	notify
	)

#include <rtrlib/aspa/aspa.h>

Frees the memory associated with the aspa_table.

Parameters

[in]	aspa_table	aspa_table that will be initialized.
	notify	A boolean value determining whether to notify clients about records being removed from the table.

aspa_table_init()

void aspa_table_init	(	struct aspa_table *	aspa_table,
		aspa_update_fp	update_fp
	)

#include <rtrlib/aspa/aspa.h>

Initializes the aspa_table struct.

Parameters

[in]	aspa_table	aspa_table that will be initialized.
[in]	update_fp	Pointer to update function

aspa_table_src_remove()

enum aspa_status aspa_table_src_remove	(	struct aspa_table *	aspa_table,
		struct rtr_socket *	rtr_socket,
		bool	notify
	)

#include <rtrlib/aspa/aspa.h>

Removes all records in the aspa_table that originated from the socket.

Parameters

aspa_table	ASPA table to use.
rtr_socket	Record's origin socket.
notify	A boolean value determining whether clients should be notified about the records' removal.

Returns

SPKI_SUCCESS On success.

SPKI_ERROR On error.

aspa_table_src_replace()

enum aspa_status aspa_table_src_replace	(	struct aspa_table *	dst,
		struct aspa_table *	src,
		struct rtr_socket *	rtr_socket,
		bool	notify_dst,
		bool	notify_src
	)

#include <rtrlib/aspa/aspa_private.h>

Replaces all ASPA records associated with the given socket with the records in the src table.

Parameters

[in,out]	dst	The destination table. Existing records associated with the socket are replaced.
[in,out]	src	The source table.
[in]	rtr_socket	The socket the records are associated with.
	notify_dst	A boolean value determining whether to notify the destination table's clients.
	notify_src	A boolean value determining whether to notify the source table's clients.

Returns

ASPA_SUCCESS if the operation succeeds, ASPA_ERROR if it fails.

aspa_table_update_in_place()

enum aspa_status aspa_table_update_in_place	(	struct aspa_table *	aspa_table,
		struct rtr_socket *	rtr_socket,
		struct aspa_update_operation *	operations,
		size_t	count,
		struct aspa_update_operation **	failed_operation
	)

#include <rtrlib/aspa/aspa_private.h>

Updates the given ASPA table.

Note

Each record in an 'add' operation may have a provider array associated with it. Any record in a 'remove' operation must have its provider_count set to 0 and provider_array set to NULL.

Parameters

[in]	aspa_table	ASPA table to store new ASPA data in.
[in]	rtr_socket	The socket the updates originate from.
[in]	operations	Add and remove operations to perform.
[in]	count	Number of operations.
[out]	failed_operation	Failed operation, filled in if update fails.

Returns

ASPA_SUCCESS On success.

ASPA_RECORD_NOT_FOUND If a records is supposed to be removed but cannot be found.

ASPA_DUPLICATE_RECORD If a records is supposed to be added but its corresponding customer ASN already exists.

ASPA_ERROR On other failures.

aspa_table_update_in_place_cleanup()

void aspa_table_update_in_place_cleanup	(	struct aspa_update_operation **	operations,
		size_t	count
	)

#include <rtrlib/aspa/aspa_private.h>

Releases operations and unused provider arrays.

Parameters

[in]	operations	Add and remove operations.
[in]	count	Number of operations.

aspa_table_update_in_place_undo()

enum aspa_status aspa_table_update_in_place_undo	(	struct aspa_table *	aspa_table,
		struct rtr_socket *	rtr_socket,
		struct aspa_update_operation *	operations,
		size_t	count,
		struct aspa_update_operation *	failed_operation
	)

#include <rtrlib/aspa/aspa_private.h>

Tries to undo operations up to failed_operation and then releases all operations.

Parameters

[in]	aspa_table	ASPA table to store new ASPA data in.
[in]	rtr_socket	The socket the updates originate from.
[in]	operations	Add and remove operations to perform.
[in]	count	Number of operations.
[in]	failed_operation	Failed operation.

Returns

ASPA_SUCCESS On success.

ASPA_RECORD_NOT_FOUND If a records is supposed to be removed but cannot be found.

ASPA_DUPLICATE_RECORD If a records is supposed to be added but its corresponding customer ASN already exists.

ASPA_ERROR On other failures.

aspa_table_update_swap_in_apply()

void aspa_table_update_swap_in_apply

(

struct aspa_update **

update

)

#include <rtrlib/aspa/aspa_private.h>

Applies the given update, as previously computed by aspa_table_update_swap_in_compute, releases memory allocated while computing the update and unlocks update lock.

The update is consumed.

Parameters

update

The update that will be applied.

aspa_table_update_swap_in_compute()

enum aspa_status aspa_table_update_swap_in_compute	(	struct aspa_table *	aspa_table,
		struct rtr_socket *	rtr_socket,
		struct aspa_update_operation *	operations,
		size_t	count,
		struct aspa_update **	update
	)

#include <rtrlib/aspa/aspa_private.h>

Computes an update structure that can later be applied to the given ASPA table.

Note

Each record in an 'add' operation may have a provider array associated with it. Any record in a 'remove' operation must have its provider_count set to 0 and provider_array set to NULL.

This function acquires an update lock on the given ASPA table ensuring no mutations occur while computing the update or before the update is applied. You must call aspa_table_update_swap_in_apply or aspa_table_update_swap_in_discard to either apply or discard the update.

Parameters

[in]	aspa_table	ASPA table to store new ASPA data in.
[in]	rtr_socket	The socket the updates originate from.
[in]	operations	Add and remove operations to perform.
[in]	count	Number of operations.
	update	The computed update. The update pointer must be non-NULL, but may point to a NULL value initially. Points to an update struct after this function returns.

Returns

ASPA_SUCCESS On success.

ASPA_RECORD_NOT_FOUND If a records is supposed to be removed but cannot be found.

ASPA_DUPLICATE_RECORD If a records is supposed to be added but its corresponding customer ASN already exists.

ASPA_ERROR On other failures.

aspa_table_update_swap_in_discard()

void aspa_table_update_swap_in_discard

(

struct aspa_update **

update

)

#include <rtrlib/aspa/aspa_private.h>

Discards the given update, releases memory allocated while computing the update and unlocks update lock.

The update is consumed.

Parameters

update

The update to discard.

aspa_verify_as_path()

enum aspa_verification_result aspa_verify_as_path	(	struct aspa_table *	aspa_table,
		uint32_t	as_path[],
		size_t	len,
		enum aspa_direction	direction
	)

#include <rtrlib/aspa/aspa.h>

Verifies an AS_PATH .

Implements an optimized version of the ASPA verification algorithm described in section 6 of https://datatracker.ietf.org/doc/draft-ietf-sidrops-aspa-verification/16/ .

Parameters

[in]	aspa_table	ASPA table to use.
[in]	direction	AS_PATH direction, as explained in the draft
[in]	as_path	AS_PATH array to be validated: concatenated of BGP UPDATEs' AS_PATHs
[in]	len	the length of as_path array

Returns

ASPA_AS_PATH_UNKNOWN if the AS_PATH cannot be fully verified

ASPA_AS_PATH_INVALID if AS_PATH is invalid

ASPA_AS_PATH_VALID if AS_PATH is valid