C H A P T E R 8 |
Access Control List Library API |
This chapter describes the Access Control List (ACL) library API. Topics include:
The Access Control List (ACL) library for Sun Netra DPS classifies IPv4 packets using a set of rules.
The classification can be done using the source/destination addresses and ports, as well as the protocol and the priority of the packet.
The algorithms are used in the library trade memory for speed. The rules are preprocessed to achieve high lookup rate while using a lot of memory.
The ACL library uses various algorithms to classify the packets.
This algorithm finds the Longest Matching Prefixes of the source and destination addresses and searches for the highest priority rule among all those rules matching the particular prefix pair. The Longest Prefix Match algorithm can use either Binary Search on Prefix Lengths (BSPL) or TRIE lookup (see TRIE Algorithm). The Longest Prefix Match algorithm provides a set of interface that can be used independently from the interface provided in the ACL library.
This algorithm is well suited for rulesets with a large number of rules (millions) where only a few rules (dozens) remain after the prefix lookups. The data structures can be updated quickly, enabling the addition or removal of thousands of rules each second. The initial rule insertion is even faster, that is, millions of rules can be added in a few seconds.
Binary Search on Prefix Lengths (BSPL) finds the longest matching prefix of an address by doing binary search on prefix length. That is, starting the search in the hash table containing median length prefixes and continuing in a hash table with longer prefixes if a match is found, shorter prefixes otherwise.
The TRIE (retrieval) algorithm uses a three-level prefix tree to find the longest matching prefix of an address.
The ACL functions use a pointer to a data structure that contains all data necessary to change the ruleset or match packets against them. This poiner enables changing the rulesets without disturbing the packet classification, by having two datasets and using one of them to classify packets while applying changes to the other. Once the changes are made the datasets can be swapped without affecting lookup performance. That is, no locks are necessary.
The ACL data structures can be copied to a new buffer or remapped to a new address without breaking the lookup algorithm. The ACL data structures enables preparing them in a domain and using them in another. That is, rule management and packet classification can be performed in separate domains if required.
Data types consist of packet and rule types.
The packets used by the ACL library are standard TCP/UDP over IPv4 packets.
A rule consists of six fields to match against TCP/IP packets:
The rule also contains a classification value (color) that is returned by the lookup algorithm when the packet matches the rule. The rules are ordered by the color in ascending order: the lookup returns the color of the lowest-color matching rule.
Initialization routine for the ACL. Based on the selected algorithm, this routine fills up the given buffer with data necessary to insert and remove rules and lookup packets. That is, the caller must allocate a buffer and pass it to acl_init and subsequent acl_* calls.
Error code is written in the provided variable.
void *acl_init(void *buf, size_t size, int alg, int *error);
buf - Pointer to the buffer to be filled with initialized data
alg - Algorithm selector (see Algorithms), in short: ACL_ALG_HYBRID_BSPL - Hybrid algorithm, LPM is using BSPL ACL_ALG_HYBRID_TRIE - Hybrid algorithm, LPM is using TRIE
ACL_ALG_HICUT - HiCut
error - Pointer to a variable where the error code is to be written
On success, it returns a pointer to the initialized ACL data or NULL in case of error. The error code is returned in case of error.
Inserts rules. Takes the rules from the given array and inserts them into the pre-initialized data structures. Then performs the necessary preprocessing and optimization, leaving the dataset ready to be used for packet lookup.
int acl_insert(void *acl, rule_t *rule, int num);
acl - Pointer to the initialized ACL data
rule - Pointer to the first rule in the array
num - Number of rules in the rule array
On success, it returns zero, or an error code in case of error.
Removes rules. Takes rules from the given array and removes each of them from the data structures.
int acl_remove(void *acl, rule_t *rule, int num);
acl - Pointer to the initialized ACL data
rule - Pointer to the first rule in the array
num - Number of rules in the rule array
On success, it returns zero, or an error code in case of error.
Lookup packet. Matches the packet against the rules and returns the classification value.
color_t acl_lookup(void *acl, packet_t *packet);
acl - Pointer to the initialized ACL data
packet - Pointer to the packet to be processed
Returns the color of the lowest-color matching rule or the default color value if none of the rules matches the packet.
Lists the current ruleset. Copies rules into the provided array.
int acl_list(void *buf, rule_t *rule, int num);
buf - Pointer to the initialized ACL data
rule - Array of rules to copy to
num - Maximum number of rules to copy
On success, returns the number of rules. If there are more rules to list than the provided array can store, then return (-num).
ACL_INIT_OK - Initialization was successful
ACL_INIT_FAILED - Initialization has failed
ACL_INIT_UNKNOWN_ALG - Invalid algorithm was passed ACL_INIT_MEMORY_ERROR - Buffer size is too small
ACL_INVALID_MAGIC - Corrupted data in ACL buffer
Initializes a three level 16-8-8 stride trie data structure using the provided buffer.
buf - Pointer to the trie data to be initialized
On success, returns the pointer to the trie data structure. Return NULL on failure.
Get the pointer to the buffer provided to trie_create.
void *trie_get_buf(void *trie);
trie - Pointer to the trie data structure.
Returns the pointer to the trie buffer.
int trie_add_prefix(void *trie, prefix_t *prefix, prefix_id_t value);
trie - Pointer to the trie data structure.
prefix - Pointer to the prefix to be added to trie.
value- Value to be returned when prefix matches.
On success, return zero. Otherwise, return non-zero value.
int trie_remove_prefix(void *trie, prefix_t *prefix);
trie - Pointer to the trie data structure.
prefix - Pointer to the prefix to be removed from trie.
On success, return zero. Otherwise, return non-zero value.
Find the longest matching prefix for the given address using trie algorithm and return the prefix ID.
prefix_id_t trie_lookup(void *trie, address_t address);
trie - Pointer to the trie data structure.
address - IPv4 address to be looked up.
Prefix ID of the longest matching prefix
Initializes a BSPL table using the provided buffer.
void *bspl_create(void *hybrid);
hybrid - Pointer to the hybrid data structure (used by acl_malloc). If input is NULL, then teja_malloc will be used to allocate BSPL table.
On success, returns the pointer to the initialized BSPL table. Return NULL on failure.
Free up resources associated with the BSPL table.
void bspl_destory(void *bspl);
bspl - Pointer to the BSPL table.
int bspl_add_prefix(void *bspl, prefix_t *prefix, prefix_id_t value);
bspl - Pointer to the bspl image.
prefix - Pointer to the prefix to be added to BSPL table.
value- Value to be returned when prefix matches.
On success, return zero. Otherwise, return non-zero value.
Add markers and BMPs to guide the binary search algorithm. It must be called before the newly added prefixes can be used.
void bspl_add_markers(void *bspl);
bspl- Pointer to the BSPL table.
int bspl_remove_prefix(void *bspl, prefix_t *prefix);
bspl- Pointer to the BSPL table.
prefix - Pointer to the prefix to be removed from BSPL table.
On success, return zero. Otherwise, return non-zero value.
Find the longest matching prefix for the given address using BSPL algorithm and return the prefix ID.
prefix_id_t bspl_lookup(void *bspl, address_t address);
bspl- Pointer to the BSPL table.
address - IP address to be looked up.
Prefix ID of the longest matching prefix
Initializes a BSPL table for IPv6 using the provided buffer.
void *bspl6_create(void *hybrid);
hybrid - Pointer to the hybrid data structure (used by acl_malloc). If input is NULL, then teja_malloc will be used to allocate BSPL table.
On success, returns the pointer to the initialized BSPL table. Return NULL on failure.
Free up resources associated with the IPv6 BSPL table.
void bspl6_destory(void *bspl);
bspl - Pointer to the BSPL table.
int bspl6_add_prefix(void *bspl, prefix6_t *prefix, prefix_id_t value);
bspl - Pointer to the BSPL image.
prefix - Pointer to the prefix to be added to BSPL table.
value- Value to be returned when prefix matches.
On success, return zero. Otherwise, return non-zero value.
Add markers and BMPs to guide the binary search algorithm for IPv6. It must be called before the newly added IPv6 prefixes can be used.
void bspl6_add_markers(void *bspl);
bspl - Pointer to the BSPL table.
int bspl_remove_prefix(void *bspl, prefix6_t *prefix);
bspl- Pointer to the BSPL table.
prefix - Pointer to the prefix to be removed from BSPL table.
On success, return zero. Otherwise, return non-zero value.
Find the longest matching prefix for the given IPv6 address using BSPL algorithm and return the prefix ID.
prefix_id_t bspl6_lookup(void *bspl, address6_t address);
bspl- Pointer to the BSPL table.
address - IPv6 address to be looked up.
Prefix ID of the longest matching prefix
Copyright © 2010, Oracle and/or its affiliates. All rights reserved.