Intent

Provide a local, mote-specific namespace for referring to distinct elements or data types.

Also Known As

unique ids

Example TinyOS Components

TimerC, MContextSynch, Matchbox

Motivation

A typical TinyOS application has to manage several data items or types at once. Processing them properly requires having a unique name for each one. As the use of these names is internal to a given mote, the names themselves are not important. Correspondingly, the names can be chosen to optimize their storage or use.

The Service Instance pattern is an example of this need. An application requires several instances of a service, and needs to be able to refer to each one uniquely. Additionally, because the identifiers for the service instances can be chosen freely, they can be selected to allow easy state management (storing per-instance state in an array).

The Local Keyset provides a way to generate and maintain a concise namespace; it is a local keyset in that other motes running different applications may not agree on the keys in the keyset: their use is limited to a particular application. For example, the Service Instance pattern uses a Local Keyset to keep track of the instances. However, if two applications include a component that uses an instance of the service, the identifier of the instance they use may be different.

nesC supports the Local Keyset pattern through the unique function. unique takes a single parameter, a constant string representing the keyset a key is needed from. The nesC compiler resolves the function to a constant at compile-time.

Applicability

Use the Local Keyset pattern when:

• You need to keep track of a number of elements locally on a mote
• The number of elements isn't known until a complete application is composed
• The exact identifiers used for the elements is not important

Consequences

The Local Keyset allows a component to request unique keys from a keyset at compile time. This means that the compiler can generate a concise namespace, as well as enumerate the elements of the namespace. Pushing this logic to compile-time reduces RAM utilization (keyset state), CPU overhead (keys are constants in code), and enables compile-time checks on keyset values.

Motes cannot safely communicate with one another in terms of Local Keysets, as they may have different key-value mappings. Additionally, although each element of a keyset is unique, there nesC provides no type checking on keys: they are just integer values. This means that programs can confuse keysets and possibly cause run-time issues (e.g., using a key from set X on a component that expects keys from set Y).

The component model of TinyOS means that it can be difficult to figure out what components are requesting keys from a local key set. Similarly, being able to map local keys to user-comprehensible names (say, for external tools) can be problematic. In this case -- where other programs need to communicate with motes in terms of keys -- a Local Keyset may not be well suited; a Global Keyset may be preferrable.

Implementation

Components generate keys from a keyset with the unique() function, with a string parameter describing which keyset the key is from. A program can determine the number of elements in a Local Keyset with the uniqueCount function.

Sample Code

The Maté virtual machine maintains locks for resources that concurrent programs may access. The set of shared resources depends on what customized VM a user builds. These locks are handled internally by the VM engine, which locks and unlocks them as needed: user programs can refer to a resource's lock by its logical name (e.g., "shared variable X"). The VM translates this logical name to a lock name.

The VM maintains the set of locks as a local keyset. If a component needs a unique lock (it has a shared resource), then it allocates one with unique:

enum {
  MYCOMPONENT_LOCKNUM = unique("MateLock");
}

The component can then use this key in requests to the locking subsystem:

if (!call Locks.isHeldBy(MYCOMPONENT_LOCKNUM, context)) {
  call Error.error(context, MATE_ERROR_INVALID_ACCESS);
  return FAIL;
}

Known Uses

Many components use local keysets: they are a fundamental part of the Service Instance pattern.

TimerC uses a local keyset to keep track of different timers that components use.

MContextSynch uses a local keyset to keep track of Maté shared resource locks.

Matchbox uses a local keyset for file handles.

Related Patterns

The Global Keyset pattern also establishes a keyset, but for the purpose of inter-mote communication: the keys are globally valid. The Keyset Map pattern provides a simple way to map between local and global keysets, if a program needs to have a concise local representation of globally acccessible names (e.g., send queues for several AM types).

The Service Instance pattern uses a Local Keyset to refer to instances of the service.