C H A P T E R 14
packetC Database Types and Operations
In packetC, several extended data types are present that do not appear in standard C but do provide significant support for packet-processing applications. These data types are extensions of familiar C types with special characteristics, including the fact that they define objects with methods that operate on their data. These types are databases, descriptors, and searchsets.
Databases provide the ability to represent a table of data elements and search it for specific data. Additionally, bit-level masking can be used both in the database of entries as well as in the records used to search the database, allowing the queries to be field-specific much like a database server query. However, databases in packetC are atomic objects with direct methods for reference.
Databases in packetC are based on a collection of records which define the structure of a row. Different databases can have rows of various sizes. The packetC virtual machines will manage the underlying representation. Databases are fairly simple to define because they are modeled as arrays of structures. Earlier chapters highlighted that packetC arrays did not support non-scalar types, in part due to the special functionality applied to arrays. Databases are a special type of array of structs with its own set of special features, called methods, that operate against the database. In addition, a record is defined which represents a single row. One subtle but crucial difference that vastly changes databases and records from being simple arrays of structs is that notion of masks which can create a shadow second representation of the structure to contain the bit-level masking.
struct MyDBrec {
int srcIp;
int destIp;
...
};
// Create a database of 100 recs
database MyDbRec myDb[100];
record MyDbRec myRec;
Operations on databases are simple and intuitive.
myRec = myDb[5]; // Get a record
myDb[1].delete(); // Delete a record
myDb[1] = myRec; // Alter a record
myDb.insert( myRec ); // Insert a record
recNum = myDb.match( toFind ); // Record matching
Masking for masked databases allow for field-by-field masking.
struct MyDbRec {
int srcIp;
int destIp;
...
};
// Create a database of 100 recs
database MyDbRec myDb[100];
record MyDbRec tempRow;
tempRow.srcIp = 10.10.1.234;
tempRow.mask.srcIp = 255.255.255.0;
...
tempRow.destIp = 192.10.1.2;
tempRow.mask.destIp = 255.255.0.0;
...
Database Declarations
A packetC database is an aggregate data type, composed of multiple instances of user-specified packetC structures. A database acts much like a dynamic array, referencing individual elements via bracketed indices, deleting individual elements, and adding new elements.
However, a database differs from packetC arrays in several ways: only a single dimension of indexing is allowed, contiguous elements cannot be referenced by array slice syntax (see section on arrays), and the user cannot presume that the database is stored in local or global memory. This last difference frees implementations to store databases in specialized hardware designed to facilitate searching and matching operations.
A packetC database declaration creates a database with user-specified base type, name, number of elements and, if supplied, an initialization clause. The basic form of a database declaration is:
database typeId identifier [ constant_expression ] identifier_init_clauseOPT ;
Where typeId is an identifier that specifies a structure type and constant_expression is a compile-time constant expression that indicates the maximum size of the database.
- typeId is the type of the individual database elements.
- identifier is the name of the database.
- expression is a constant expression specifying the maximum number of elements.
// Example
struct BaseType { short src; short dest; };
database BaseType myDb[50];
Two kinds of syntax can appear within a database initialization clause:
- The explicit format is characterized by data and mask parts that are separated by a comma, where each part appears as a structure initialization expression within curly braces. This data/mask pair is surrounded by an outer set of curly braces.
- An implicit format omits the mask portion but still surrounds the data initialization expression with an outer set of curly braces. When the mask is omitted in this way, it is presumed to consist of all bits set (equal to one).
// Example explicit and implicit mask formats
database T Db1[50] = { {{5,12},{~0,~0}}, {{6,10},{~0,~0}} }; // explicit
database T Db2[50] = { {{5,12}}, {{6,10}} }; // implicit
When the declaration specifies that the database has n elements and the initialization clause contains p elements.
- If p <= n, then p initializing elements will be loaded into database elements 0 through p-1.
- If p > n, the results, such as initializing only the first n elements or issuing error messages, is implementation-defined.
A database can only be declared in a module's global scope. Otherwise, a database declared in a packet module's packet scope, for example, would require a different database for every instance (copy running in parallel) of the packet main application.
Databases and Masking
Packet processing often involves storing and searching data from multiple packet headers and payloads. This aggregate data can most efficiently be stored in a database. To provide both organization and flexibility, packetC organizes databases as aggregates of C-style structures. These databases have some similarities to a one-dimensional, dynamic array. However, in order to support the use of specialized, high-speed stores for searching and matching, packetC implementations can locate databases outside of local or global memory.
Operations on database contents may include searching and matching data that is associated with masks. For data organized as structures, each database component (structure) will be associated with a structure of equal size (its mask), which holds the corresponding mask bits. The mask controls which portions of the data field are used in database searching operations. If a mask bit is equal to 1, the corresponding data bit is considered in these operations; otherwise, the bit is ignored.
data: src field data: dest field mask: src field mask: dest field
0000000000000101 0000000000011101 0000000000000000 1111111111111111
In the example above, the mask bits that correspond to the dest field are all set, so the entire dest field will be used in database searching and matching operations. Since no src field mask bits are set, these operations will ignore that field.
A key aspect of packetC databases is automated masking. This consists of taking the database's structure base type, T, and recasting it to have two identical, nested structures: data and mask. Automated masking is performed when either a database or a database record is declared.
struct BaseType { short src; short dest; };
database BaseType myDb[50]; // has automated masking effects
Conceptually, the database is composed of structures with the following organization:
struct MyBaseStruct {
struct BaseType data;
struct BaseType mask;
};
The original user type's individual fields are still accessible as sub-fields. Since both the data and its associated mask are structures, setting mask values can be done by setting individual fields, rather than solely by using large constants to set the entire mask. A user may access the contents of the data portion by either using .data syntax or by omitting the name of the nested structure. The latter features are especially helpful if the user is not manipulating masks.
record BaseType myRec; // has automated masking effects
myRec.mask.src = 0xffff;
myRec.data.src = 256;
Conceptually, all packetC databases have associated mask bits. However, if a user never manipulates a database's mask bits, an implementation may optimize its representation appropriately. Both initialization clauses that specify mask bit values and operations that read or write mask bit values signify that a database actively uses mask bits.
The major components of the packetC approach to databases are:
- Databases: aggregates of C structures, which are automatically masked
- Database records: matches database's automatically masked structure
- Individual Masks: non-masked structure that is equivalent to a database record's mask portion
struct BaseType { short src; short dest; };
database BaseType myDb[50]; // database
record BaseType myRec; // database record
const BaseType myMask = {~0s, 0s}; // individual mask
The following sections discuss these components in greater detail.
Database Limitations and Padding
A packetC implementation can implement a database in a variety of ways, including using specialized associative memories or by using an array in ordinary memory to represent the database. Regardless of the implementation mechanism, the user may declare a database that is too large for the implementation to accommodate. When a packetC implementation cannot represent a user-defined database because of size constraints, it shall issue an appropriate fatal error message. The maximum size of a packetC database that can be accommodated is implementation-dependent.
An implementation may pad a database, for example by adding unused bits to the database's base type to make it match the size of a specialized memory used to hold databases. Such unused bits need not be exposed to the user.
struct BaseType { short src; short dest; };
database BaseType uDb[35]; // baseType may be padded to 128 or 512 bits
Database Records and Elements
When a database's masked bits will be accessed, the user declares a database record, which is automatically masked, just as a database is. Thus, the record has the same .data and .mask components as a database does, which has been made from the same structure base type.
struct BaseType { short src; short dest; };
database BaseType myDb[50];
record BaseType myRec;
Individual database elements are accessed like an array element by placing a single-dimension indexing expression within square brackets. The value of a database element can be “read” by assigning it to a structure variable with the same type as the database.
database BaseType myDb[35];
record BaseType myRec;
…
myRec = myDb[5];
myRec.data.dest = 10.10.1.1;
myDb[5] = myRec;
Similarly, an existing database element may be “written” by simply assigning it the value of a variable with the same structure type. A reference to the variable without specifying any field, accesses the entire structure. If an individual sub-field is referenced without prefacing it with .data or .mask, then .data is assumed.
// Both the same
MyDb[12].data.dest = myRec.data.dest;
MyDb[12].dest = myRec.dest;
MyDb[5] = myrecord;
Masks
A packetC mask is a bit pattern that corresponds to the base structure of a database or database record and that contains as many bits as the base-type structure does. A mask is not declared as a database record (since that would automatically mask a mask); instead it is declared as a structure of the same type as the base type of the relevant database.
struct BaseType { short src; short dest; };
database BaseType myDb[100];
record BaseType myRec;
const BaseType myMask = {~0s, 0s};
// Read mask and data from a DB; Alter data and mask
myRec = myDb[j]; // access entire structure
myRec.src = 17; // defaults to data.src field
myRec.mask.dest = ~0; // set bits in indicated mask portion field
// Write only the altered data portion to the original DB record
myDb[j].data = myRec.data;// Write altered data and mask to another DB record
myDb[m] = myRec;
A common application scenario involves defining a small number of masks that do not vary during execution. For example, one mask might be defined to regard all of a database structure as significant, and several masks could be defined that ignore all of the structure except for a single field or sub-field of interest.
A mask that does not change during application execution, such as those in the example above, should be defined with the const specifier. packetC implementations may use this information for optimizations.
Database Subscripting Operator
The subscripting operator works for databases in much the same way as it works for arrays. In both cases, a postfix expression is followed by an expression within square brackets, which designates an element of the aggregate (in this case, the database).
Indexing a packetC database, however, simply indicates an individual element in the database; the user should make no assumptions that database elements are present in memory, stored in row-major order, and so forth. Differences between packetC databases and arrays are enumerated in the section on the database type. Like arrays, databases are indexed by values that start at zero.
If the record does not exist in the database, the operator will throw the predefined error, ERR_DB_READ.
database MyStructType myDb[50];
MyStructType structVar;
...
// alter the contents of the 4th element of the database
myDb[3].data = structVar;
Database Delete
The operator for deleting a single database element consists of an indexed reference to a single database element, followed by a dot (“.”), the delete keyword, and empty parentheses. The operator deletes the indicated database element and effectively returns void (no meaningful result). Only a single item may be specified as an index. Multiple deletions must be carried out using multiple commands or an iterated loop.
database MyStructType myDb[75];
...
// Valid forms
myDb[34].delete();
myDb[j].delete();
// Error forms
myDb.delete(); // one specific database element must be specified
myDb[0:4].delete(); // only a single database element can be specified
Database Insert
A database insertion adds a new element to the database, using the specified argument of the database's base type, and returns an int value with the number of the database row where the information was inserted. An implementation may affect optimizations on the basis of whether the returned row number is ignored by user code.
If the database is full, the insert operator will throw the predefined error, ERR_DB_FULL.
struct BaseType { short src; short dest; };
BaseType myStruct = { 15, 17 };
database BaseType myDb[50];
int rowNum, oddUse;
...
rowNum = myDb.insert( myStruct ); // myDb insertion point data is used
myDb.insert( myStruct ); // Returned int is ignored
// database insert acts like an operator that produces
// int result in unlikely example below,
// where result = the insertion ‘row' number plus 500
oddUse = 500 + myDb.insert( myStruct );
The operand of the insert operator may be a structure or a record.
Database Match
The match operator returns an int value that indicates the database row that provided the first match for the initial argument.
Match compares each database row (structure), from first to last, to the operator's first argument. The row number of the first row to match is returned. If a second argument is present, it receives the contents of this matching row. Using the second argument with an unmasked database has little utility, since the matched data already exists in the first argument.
If no match is found, the match operator will throw the predefined error, ERR_DB_NOMATCH.
struct MyRecStruct {
short src;
short dest;
};
database MyRecStruct myDb[20] = {…};
record MyRecStruct searchStruct = { {16s, 32s},{~0s, 0s} }, retStruct;
int rowNum;
...
try {
...
// returns row number of match
rowNum = myDb.match(searchStruct);
// Also returns row number of match
rowNum = myDb.match(searchStruct, retStruct);
...
}
catch ( ERR_DB_NOMATCH ) {
...
}
Operator Invocations
packetC defines built-in functions or operators for its extended data types. These operators, which are described in the section on extended operators and operands, are invoked in much the same manner as user-defined functions are. Invoking built-in operators, however, differs from invoking user functions in the following ways:
- The invocation consists of a variable of the data type for which the operator is defined, a dot (“.”), the operator name, and a parenthesized argument list.
- The argument list cannot use the by-substitution mode of parameter passing.
struct StructType {
short src;
short dest;
};
database StructType myDb[20] = {…};
StructType searchStruct = { 16s, 32s };
int rowNum;
...
try {
rowNum = myDb.match(searchStruct); // legal
// ERROR: The example below attemps to use by-substitution
// param with an operation, which is not allowed
rowNum = myDb.match(@searchStruct);
}
Example Database Application
packet module databaseTable;
#include "cloudshield.ph"
#include "protocols.ph"
// global counters
int totalPkts_ = 0;
int readPass_ = 0;
int readFail_ = 0;
// Record structure of the database
struct DbStruct {
int data1, data2, data3, data4;
};
// Define unmasked databases using DbStruct
database DbStruct dbTable1[9] = {
#include "db_data1.px"
};
database DbStruct dbTable2[9] = {
#include "db_data2.px"
};
void main($PACKET pkt, $PIB pib, $SYS sys)
{
DbStruct readData;
int fail;
++totalPkts_;
try
{
readData = dbTable1[3].data;
++readPass_;
readData = dbTable2[3].data;
++readPass_;
}
catch (ERR_DB_READ)
{
++readFail_;
}
catch ( ... )
{
++fail;
}
pib.action = FORWARD_PACKET;
}
Example Database Application (ACL)
// Simplified Access Control List Example
packet module aclExample;
#include "cloudshield.ph"
// Define User Error Constant
const int ERR_BAD_PACKET = ERR_LAST_DEFINED + 1;
// Define Global variables
int notValidPacket_ = 0;
int matchPacketCounter_ = 0;
int noMatchPacketCounter_ = 0;
int fail_ = 0;
struct AclStruct {
int srcIp;
int destIp;
short srcPort;
short destPort;
};
descriptor IpDescriptor
{
int sourceAddress;
int destAddress;
} ip at pib.l3Offset + 12;
descriptor TcpDescriptorPorts
{
short sourcePort;
short destPort;
} tcp at pib.l4Offset;
database AclStruct aclDb[6] = {
{{ 10.10.20.80, 10.10.10.50, 25s, 8s }, { ~0, ~0, ~0s, ~0s }},
{{ 10.10.20.81, 10.10.10.50, 25s, 8s }, { ~0, ~0, ~0s, ~0s }},
{{ 10.10.20.82, 10.10.10.50, 25s, 8s }, { ~0, ~0, ~0s, ~0s }},
{{ 10.10.20.83, 10.10.10.50, 25s, 8s }, { ~0, ~0, ~0s, ~0s }},
{{ 10.10.20.84, 10.10.10.50, 25s, 8s }, { ~0, ~0, ~0s, ~0s }},
{{ 0.0.0.0, 0.0.0.0, 0s, 0s }, { ~0, ~0, ~0s, ~0s }}
};
void main($PACKET pkt, $PIB pib, $SYS sys)
{
// Assume
try {
if ( !pib.flags.l4CheckSumValid ||
!pib.flags.ipv4 ||
pib.l4Type != L4TYPE_ICMP
)
//User defined err
throw ERR_BAD_PACKET;
AclStruct acl;
acl.srcIp = ip.sourceAddress;
acl.destIp = ip.destAddress;
acl.srcPort = tcp.sourcePort;
acl.destPort = tcp.destPort;
// Look up this acl, throws ERR_DB_NOMATCH if not
// currently in the acl database.
int aclMatchRow;
aclMatchRow = aclDb.match( acl );
// Found in acl database
++matchPacketCounter_;
pib.action = FORWARD_PACKET; // Forward this packet
}
catch ( ERR_DB_NOMATCH ) {
++noMatchPacketCounter_;
// pib.action = DROP_PACKET; Default Drop this packet
}
catch ( ERR_BAD_PACKET ) {
++notValidPacket_;
}
catch ( ... ) {
// accident
++fail_;
}
}