Difference between revisions of "Containers"

Revision as of 14:53, 19 February 2010

Some (incomplete) ramblings about netsnmp_containers...

Introduction

Containers are a generic data interface, similar to a database. Like a database, you use an index (aka key) to access and sort the data. Containers use a compare function provided by the user to determine the sort order. The function is called with a pointer to two data items, and must return a value indicating which of the two has the lesser index value.

Types of Containers

There are several base types of containers:

sorted_singly_linked_list
unsorted_singly_linked_list
lifo (a last in, first out stack)
fifo (a first in, first out stack)
binary_array
null (for testing)

Some of these have aliases:

table_container (binary_array)
linked_list (sorted_singly_linked_list)
ssll_container (sorted_singly_linked_list)

Some types also come with a comparison routine other than the usual OID index:

string or string:binary_array (binary_array with a string comparison function)

Developer Tip:
 New types are registered via netsnmp_container_register() and netsnmp_container_register_with_compare().

Getting a Container

To get a container of a particular type,

netsnmp_container_find("type1:type2");

This will search for a container of "type1", and if not found, of "type2". It is a good idea to specify a custom name each time that you use a container. In the future, it will be possible to specify that certain tokens should map to certain container types. For example, say you are using a container while implementing the XyzWidgetMib, and you wanted to use a linked list, you could create your container like so:

container = netsnmp_container_find("XyzWidgetMib:linked_list");

This would look for an XyzWidgetMib container (which doesn't exist), and then default to using a linked list container. Once implemented, a configure option will allow you to alias XyzWidgetMib to an existing container type (e.g. a binary array), allowing the runtime-configuration to change the container type to a binary array, should the linked list perform poorly with a large data set.

MIB indexes vs Container indexes

SNMP tables have one or more indexes. A table index may have multiple components which, taken together, uniquely identify a row. All of the MIB indexes, taken together, are the primary container index. Even if a MIB table has a dozen indexes, the container only has one.

To clarify futher, here's an example. Let's say we are creating a SNMP interface to a hotel reservation system. The (simplified) table looks like this:

guestTable

 guestEntry INDEX { building, room }
   building INTEGER
   room     INTEGER
   name     STRING

So, the MIB has two indexes, the building and room numbers. The primary MIB index is the building, and the secondary MIB index is the room. However, the primary index of the container will be the combined table index OIDs (building.room).

Comparison routines

The default compare routine for containers assumes that the data record's first component is a netsnmp_index, so when using an OID as a key, you don't need to provide a comparison routine. If you wanted to provide your own compare routine, the primary container index compare function might look something like this:

 int
 _compare_room(guestTable *lh_guest, guestTable *rh_guests)
 {
   /* compare building, then room */
   if(lh_guest->building == rh_guest->building) {
       if(lh_guest->room == rh_guest->room)
          return 0;
       else {
          if(lh_guest->room < rh_guest->room)
             return -1;
          else
             return 1;
       }
   }
   else {
      if(lh_guest->building < rh_guest->building)
        return -1;
      else
        return 1;
   }
 }

So we now have a container with the guest data, and we can look up data by building and room number.

netsnmp_container *
netsnmp_hotel_container_init(void)
{
    netsnmp_container *container;

    // default to a table_container if no 'guest room' container is found
    container = netsnmp_container_find("guest room:table_container");
    if (NULL == container)
        return NULL;
    container->container_name = strdup("room container");

    // use our custom ordering routine
    container->compare = (netsnmp_container_compare*)_compare_room;

    return container;
}

Subcontainers

A container can have a sub-container. There are two types of sub-containers: secondary indexes, and subsets.

Secondary Indexes

So we now have a container with the guest data, and we can look up data by building and room number. What if our application now needs to generate a guest report, but sorted by name? We have the data, but in the wrong sort order. This is where you would use a secondary index to the container. The new compare might look like this:

int
_compare_names(guestTable *lh_guest, guestTable *rh_guests)
{
   /* compare name, then building and room */
   int rc = strcmp(lh_guest->name,rh_guest->name);
   if(rc != 0)
      return rc;

   return _compare_rooms(lh_guest, rh_guest); // defined above
}

Setting up the container with two indexes would look something like this:

netsnmp_container *
netsnmp_hotel_container_init(void)
{
    netsnmp_container *container1, *container2;

    /** create 2 containers */
    container1 = netsnmp_container_find("guest room:table_container");
    if (NULL == container1)
        return NULL;
    container1->container_name = strdup("room container");

    container2 = netsnmp_container_find("guest name:table_container");
    if (NULL == container2) {
        CONTAINER_FREE(container1);
        return NULL;
    }
    container2->container_name = strdup("guest container");
    container2->compare = (netsnmp_container_compare*) _compare_name;

    /** add secondary index to container */
    netsnmp_container_add_index(container1, container2);

    return container1;
}

Sub-sets

Sometimes, it can be useful to access a sub-set of a data set. For example, if you have a container of all the IP addresses for some system, it might be useful to be able to work with only the IPv4 addresses, without having to iterate over all the addresses and ignore the IPv6 (or other) addresses. This can be done with a secondary index with a filter (only available in more recent releases). The secondary index container would share the same sort function as the primary container, but the secondary container would have a filter function which would filter out inserts of IPv6 addresses.

int
_ipv4_only_filter(struct netsnmp_container_s *, const void *data) {
   struct my_datatype *my_data = (struct my_datatype*) data;

   /** return 1 to filter data, 0 to allow */
   if (my_data->type == IPv6)
      return 1;

   return 0;
}

Container Operations

Several functions are provided for easy use of containers. These functions should be used is almost all cases, since they do the 'right' thing for special cases such as insert filters and subcontainers.

Creating a container

Adding and removing data

CONTAINER_INSERT

The container insert function inserts an item into a container. Note that an insert_filter may prevent some items from being inserted into the container or sub-containers.

 CONTAINER_INSERT(thecontainer, thedata);

CONTAINER_REMOVE

The container remove function removes an item from a container. It does not free the item.

CONTAINER_CLEAR

CONTAINER_CLEAR(container, callback, context)

The container clear function is a special function that is optimized for clearing a container. It is effectively the same as iterating over the container and calling CONTAINER_REMOVE for each item, calling the specified callback function as you go. The context parameter is for you use, and is also passed to the callback function. Pass NULL if you don't need any context. If you simple need to free the pointer stored for each item, use netsnmp_container_simple_free as the callback. If your structure has additional memory allocated, or you need to perform some action for each item to release other resources, you will have to provide a custom callback function.

/* clear a container that only needs a simple free() call on each item. */
CONTAINER_CLEAR(container,
                (netsnmp_container_obj_func*)netsnmp_container_simple_free,
                 NULL);

/*
 * here is an example of a function that could be passed for a more
 * complex free
 */
static void 
_complex_free(void *data, void *context)
{
    struct mystruct *mydata = (struct mystruct *)data;

    if (data == NULL)
	return;
    free(mydata->some_ptr);
    free(mydata);
 }

Finding data in a container

CONTAINER_FIND

CONTAINER_FIND searches for data in a given container. You must pass in a data object with the index object filled out and it will return the object in the container matching that index set.

 data = CONTAINER_FIND(container, template_index);

Iterating over items in a container

There are 3 methods available for iterating over items in a container;

CONTAINER_FIRST and CONTAINER_NEXT

You can use CONTAINER_FIRST and CONTAINER_NEXT to iterate over a container:

netsnmp_container *c = netsnmp_container_find("binary_array");
void              *data;

for( data = CONTAINER_FIRST(c); data; data = CONTAINER_NEXT(c, data)) {
   fprintf(stdout, "data %x\n", data);
}

The disadvantage of this is that CONTAINER_NEXT does a search to find the previous item before it can return the next item. This is pretty inefficient, thus this method is not recommended.

CONTAINER_FOR_EACH

You can define a callback function and pass it to CONTAINER_FOR_EACH, like so:

void my_callback(void *data, void* context) {
   fprintf(stdout,"callback for data %x and context %x\n", data, context);
}

int main(int argc, char **argv) {
   void              *my_context = 0xdeadbeef;
   netsnmp_container *c = netsnmp_container_find("binary_array");

   /* for each data element in the container, run my_callback on it */
   CONTAINER_FOR_EACH(c, my_callback, my_context);
}

The function my_callback will be called for each data item in the container.

CONTAINER_ITERATOR(x)

Some containers support iterating over the contents, like so:

netsnmp_container *c = get_my_container();
netsnmp_iterator  *it;
void *data;

it = CONTAINER_ITERATOR(c);
if (NULL == it)
   return -1;
for( data = ITERATOR_FIRST(it); data ; data = ITERATOR_NEXT(it) {
   fprintf(stdout, "data %x\n", data);
}
ITERATOR_RELEASE(it);

Which method to choose?

As mentioned above, CONTAINER_FIRST and CONTAINER_NEXT should only be used for really small containers where performance isn't important. The decision between the CONTAINER_FOR_EACH and CONTAINER_ITERATOR methods is largely one of style. CONTAINER_ITERATOR is easy to read, and looks like a traditional loop over a linked list. CONTAINER_FOR_EACH offers a better opportunity for reuse, allowing a callback to be applied to multiple containers, in different places in the code, using the context to differentiate as needed.

Miscellaneous operations

CONTAINER_SIZE

This function returns the number of items currently in the container.

Releasing a container

CONTAINER_FREE

The container free function releases internal resources used by the container and frees the container itself. It does not release the memory used by any items contained within the container. You must use either the CONTAINER_REMOVE or CONTAINER_CLEAR functions to release resources used by the items in the container before calling CONTAINER_FREE.

Advanced topics

CONTAINER_SET_OPTIONS and CONTAINER_CHECK_OPTION

CONTAINER_SET_OPTIONS copies the specified flags to the container options. It DOES NOT OR the flags with existing flags, so it allows one to overwrite existing flags. Unfortunately, there doesn't seem to be a way to get the existing flags, making addition of a single flag difficult.

CONTAINER_CHECK_OPTION returns 1 if the specified flags are set, or 0 if they are not set.

CONTAINER_GET_SUBSET

Note: get subset returns allocated memory (netsnmp_void_array). User is responsible for releasing this memory (free(array->array), free(array)). DO NOT FREE ELEMENTS OF THE ARRAY, because they are the same pointers stored in the container.

CONTAINER_COMPARE(x,l,r)

tbd

Shared Container/cache

Often multiple MIB implementations will need to use the same data. Instead of having redundant copies of the data, they can use the same container. This example code is based on the ifTable/ifXTable code, and uses the cache helper as well.

/** ifXTable uses the same cache (and thus container) as ifTable */
if_ctx->cache =
    netsnmp_cache_find_by_oid(ifTable_oid, ifTable_oid_size);
if (NULL != if_ctx->cache) {
    if_ctx->container = (netsnmp_container *) if_ctx->cache->magic;

Generic Container Example

The following code demonstrates how containers can be used to store arbitrary data indexed by an OID using the container system. You can also see a

 /*
  * This code takes the approach of using a standard binary_array
  * container with a default index type of an OID.  We'll pretend, for
  * this example, that a standards body ("ice cream eaters anonymous")
  * has defined the following standardized OID to flavor mappings:
  *
  * .1.2.3      chocolate
  * .1.3.4.5    vanilla
  * .1.2        strawberry
  *
  * We'll create a database of these flavors indexed by their
  * standardized OID assignments and store the name of the flavor and
  * the number of votes it received in a popularity contest.
  *
  * Compile this file using:
  *
  *   cc -g -o container_test container_test.c -lnetsnmp
  *
  * And test it by running: ./container_test
  */
 
 #include <net-snmp/net-snmp-config.h>
 
 #include <net-snmp/net-snmp-includes.h>
 #include <net-snmp/library/container.h>
 
 /* our bogus data structure; self defined. */
 typedef struct my_data_s {
 
    /* This *MUST* be first in the structure */
    netsnmp_index oid_index;
 
    /* We don't have OIDs longer than 4, so we'll just use a short buffer */
    oid           oid_buf[4];
 
    /* And the data we want to store */
    char          ice_cream_flavor[128];
    int           votes;
 } my_data;
 
 int
 main() {
 
     netsnmp_container *test;
     my_data *data;
     my_data index_template;
 
     /* required to bootstrap the container system */
     init_snmp("container_test");
     
     /* create our container */
     test = netsnmp_container_find("binary_array");
 
     /* create our first entry; malloced for handing to the system */
     data = SNMP_MALLOC_TYPEDEF(my_data);
     data->oid_index.oids = data->oid_buf;
     data->oid_buf[0] = 1;  /* lets pretend .1.2.3 is standard for chocolate */
     data->oid_buf[1] = 2;
     data->oid_buf[2] = 3;
     data->oid_index.len = 3;
     strcpy(data->ice_cream_flavor, "chocolate");
     data->votes = 42;
     CONTAINER_INSERT(test, data);
 
     /* create and add our second entry: vanilla */
     data = SNMP_MALLOC_TYPEDEF(my_data);
     data->oid_index.oids = data->oid_buf;
     data->oid_buf[0] = 1;  /* lets pretend .1.3.4.5 is standard for vanilla */
     data->oid_buf[1] = 3;
     data->oid_buf[2] = 4;
     data->oid_buf[3] = 5;
     data->oid_index.len = 4;
     strcpy(data->ice_cream_flavor, "vanilla");
     data->votes = 30;
     CONTAINER_INSERT(test, data);
 
     /* create and add our final entry: strawberry */
     data = SNMP_MALLOC_TYPEDEF(my_data);
     data->oid_index.oids = data->oid_buf;
     data->oid_buf[0] = 1;  /* lets pretend .1.2 is standard for strawberry */
     data->oid_buf[1] = 2;
     data->oid_index.len = 2;
     strcpy(data->ice_cream_flavor, "strawberry");
     data->votes = 10;
     CONTAINER_INSERT(test, data);
 
 
     /*
      * now we have a database, organized by OID for flavor/vote pairs
      */
 
     /* lets find whatever flavor is at .1.3.4.5 */
     /* we do this by creating a new data structure with the indexes
        filled in to look for */
     data = SNMP_MALLOC_TYPEDEF(my_data);
     index_template.oid_index.oids = index_template.oid_buf;
     index_template.oid_buf[0] = 1;
     index_template.oid_buf[1] = 3;
     index_template.oid_buf[2] = 4;
     index_template.oid_buf[3] = 5;
     index_template.oid_index.len = 4;
 
     /* and we call CONTAINER_FIND to search for the real data */
     data = CONTAINER_FIND(test, &index_template);
 
     fprintf(stderr, "the flavor is %s and it's votes are %d\n",
             data->ice_cream_flavor,
             data->votes);
 }

This code obviously doesn't clean up properly at the end nor does it show all the other features/functions of containers (like secondary indexes) but it at least shows how to bootstrap something in a very basic manner.

You can also take a look at the simple test code in snmplib/test_binary_array.c