C H A P T E R  17

Semaphores in packetC

Locking and Unlocking

The complexities of parallel processing introduce the problem that generally leads to complex inter-process communications. With packetC, the notion of global data is ever-present and even though access to data elements is atomic, programs represent information in more complex structures than basic scalar types. As such, a mechanism for communication with other contexts is required in order to notify them to not touch portions of global memory that are in use, or more important, being manipulated by another context. Locking of memory can grind a parallel system to a halt. So, instead, packetC introduces a method of semaphores where any global int data element can be used as a semaphore representing whatever the application desires. It is a cooperative inter-process memory protection model that trades off some security in return for significant performance. Lock and unlock methods are applicable to global data elements which provide an atomic test-and-set, storing a magic number in the data element itself. Should the lock be successful, the application can proceed to work on other data elements safely, knowing it is not in competition.

C programmers beware: Any data element being a cooperative semaphore moves out of traditional C mechanisms pretty quickly into some new facets of C++ and other modern languages. That said, semaphores provide a critical role in the high-performance parallel processing controls required to build complex programs in packetC.

Lock and Unlock Operators

Lock and Unlock introduce a true test-and-set functionality found in parallel processing. This provides an almost unlimited number of available locks to be used as semaphores that are locked or unlocked. Any global, array, or matrix memory location can be used as a lock. This feature allows for both data-driven processing against packet flows as well as application-level critical-section locks. The lock and unlock operate in a cooperative locking mode.

One common area of use for lock and unlock in packet processing is managing multi-packet transactions, such as reassembling the payload of multiple TCP packets. Once a TCP flow is in reassembly, each packet can update its portion of a larger buffer without locking because TCP provides sequence numbers that identify which offset in the buffer to copy the payload into. At startup and teardown of a flow, however, there needs to be the guarantee that only one packetC context is managing the flow and tables control the transaction payload reconstruction. The Lock and Unlock functions are not a singular lock, but actually are functions that can turn any global variable location into an application-specific lock. This is generally called a cooperative locking environment where code is not prohibited from touching memory but rather properly written packetC code would check the Lock status before proceeding. In this model, doing a spin on the Lock is preferred because this minimizes the time the context is waiting for its turn. With the ability to create millions of locks, only two packets of a given flow being processed at the same time would test a given lock and potentially wait to begin processing the packet.

In a high-speed network or aggregation point, where many flows (50 or more) occur simultaneously, it actually turns out that this is better for the system. Should packets from these flows hit the box at the same time, it is unlikely that any two from the same flow need to be in the critical section at the same time. As such, the higher the performance and larger the number of concurrent flows, the less likely locks collide enabling parallel processing performance to continue unhindered. In the case that a large stream from a single source occurs, we suggest you design the use of locks judiciously and only in the tightest critical sections of code that require only a single context at any given time. The global memory that the lock and unlock methods operate on in packetC will often be called semaphores in other programming languages. The lock and unlock methods are cooperative in that they require all portions of the application to treat the memory location being used as a semaphore appropriately. Directly writing data to a semaphore may cause unexpected results as other contexts are depending on a specific lock value. The benefit, however, is that millions of semaphores can be created and no operational system needs to address adjustments to memory access during system operation when contention does not exist. Only in the case where a semaphore is locked by one context, and to the extent the application requires, another context requests to lock the same semaphore does this approach impact a concurrently processing context.

Lock Operator

Lock is a unary operator that returns a truth result, just as the equality and relational operators do. Its sole operand is a 32-bit global integer, which must be a scalar variable or an array element.

If the operand is not currently locked, lock sets its value to indicate that the program copy currently executing has locked the operand and returns a non-zero value to indicate success (i.e., “true”). If the operand is already locked, this operation does not change the operand's stored value and returns a zero value to indicate “false.” The range of values stored in the operand to identify which, if any, program copy (context) has locked it shall be implementation-defined. Programs should not depend on the operand's particular values (as opposed to the truth value of the operation) nor assign other values to lock operands. Thus, although lock operations can control access to global variables that are shared by multiple program copies (contexts), such variables should not be used as lock operands themselves.

Expressions that involve this operation can appear as stand-alone statements (as in the example above) or appear in any conditional context where an equality or relational operator could.

Unlock Operator

Unlock is a unary operator that returns a truth result, just as the equality and relational operators do. Its sole operand is a 32-bit global integer, which must be a scalar variable or an array element.

If the operand is currently locked and was locked by the instantiation of the packet application that contains this unlock, then the operation sets the operand value to indicate an unlocked state and returns a non-zero value to indicate success (i.e., “true”). If the operand is already unlocked, the operation returns a non-zero value. If the operand is locked and the locking was done by an executing context of the packetC application other than the one containing this unlock, this operation does not change the operand's stored value and it returns a zero value to indicate “false.”

Expressions that involve this operation can appear as stand-alone statements (as in the example above) or appear in any conditional context where an equality or relational operator could.

Using Lock and Unlock to Perform a Global Malloc() and Free()

The lock and unlock operators provide a mechanism for managing global, cross context, semaphore mechanisms such that shared resources can be managed without collision. Within packetC, there are cases where dynamic memory allocation may be required. While this is not a capability within the grammar and no direct equivalent to pointers exists, this does not restrict the ability of an application from employing a similar mechanism. An application may allocate a large region of memory within global application space and allocate portions of this memory for dynamic allocation to other functions or uses.

In the concept above, the array bigBlob is allocated with one million bytes of memory. Furthermore, bigBlobEntry contains a list of memory regions allocated. This list can start with 1 item (bigBlobEntrySize=1) in row 0 of bigBlobEntry where column 0 is 0, column 1 is 999,999 and column 2 is set to 1, identifying it as Free. Using the lock operator, bigBlobSemaphore is locked, identifying exclusive access to these variables and a function call emulating malloc() can manipulate bigBlobEntry[] to establish an allocated region of the number of bytes requested while also updating the free list. The application would be hard coded to access the variable bigBlob[]. Cooperatively, each portion of the application must ensure access is only to the portion of bigBlob[] allocated using an emulated malloc() and free() function which is using bigBlobEntry[] to manage this byte region.

The net result is, even in an environment without dynamic memory allocation, using lock and unlock with semaphores, multiple contexts over an extended period of time and packets can provide flexible memory allocation. This will elevate the security risks to within the application, however, tight controls and coding standards on accessing allocated memory segments can provide the appropriate level of security and audit required. This also helps to identify the potential risks that are present no matter how controlled a language is. The programmer can not only extend features beyond their intended result but can cause havoc no matter how strict the rules are.

As there are multiple methods for emulating a malloc() and free() as well as techniques which simplify the linked list management within the free list tracking, no specific implementation example is shown. Some applications may need simple implementations or possibly multiple independent implementations concurrently. In any case, the concept remains as simply allocating a singular global array of bytes and providing offsets within this array to different requestors such that they can share the large memory region. While risk exists with bad code accessing sections within the global allocated to other requestors, packetC will still protect the system from accessing outside of the global array.