transaction blog
May 26, 2017 • 14 min read

Transactional Access to Arbitrary Memory Locations

In this blog post we are going to implement transactional semantics for arbitrary locations in main memory. So far our simpletm transaction manager can only handle integer values that we store in a dedicated data structure. At the end of this installment, we’ll be able to work with values of arbitrary types that are located (almost) anywhere in memory.

In the previous installments we finished our transaction manager simpletm to contain miminal functionality for detecting and resolving conflicts among transactions, and we separated the transaction manager from the application logic by creating a generic C interface.

Loads and Stores for Integer Resources

For transactional memory access, our example program executes load and store operations on dedicted data structures of type struct int_resource, which is shown below.

struct int_resource {
    int             value;
    int             local_value;
    unsigned long   flags;
    pthread_t       owner;
    pthread_mutex_t lock;
};

The shared integer value is stored in the field value. Each instance of the structure is owned by a single transaction that stores in the field local_value and loads from either value or local_value, depending whether a local value is present. The flags field tells us about this. During the owning transaction’s commit the local value is copied to the actual value, on rollback the local value is discarded.

The corresponding load/store interface for an application looks like this.

void
load_int(struct int_resource* res, int* value);

void
store_int(struct int_resource* res, int value);

It’s specific to integer values and the application has to know about the struct int_resource data structure. Instead we should prefer an interface that can store a value of any type at any location in memory.

Working With Arbitrary Types

To support arbitrary types, let us rework struct int_resource a bit. We call this new structure struct resource.

#define RESOURCE_BITSHIFT   (3)
#define RESOURCE_NBYTES     (1ul << RESOURCE_BITSHIFT)

/**
 * An integer value with an associated owner.
 */
struct resource {
    uintptr_t       base;
    uint8_t         local_value[RESOURCE_NBYTES];
    uint16_t        local_bits;
    pthread_t       owner;
    pthread_mutex_t lock;
};

First of all, we remove the field value. Instead the base field tells us where in memory the resource is located. The value in base is the address of the first byte of a transactional value.

The field local_value is now a fixed-size byte array. It still stores the local value, but it’s not any longer type specific. In our case the array is 8 byte in size, so we can operate on values up to 8 bytes. Further below we will see how to arrange the resources such that values of arbitrary size can be supported.

Finally we replaced the flags field by local_bits. The latter is a bit field, where each bit signals the present of a transaction-local value in local_value. So if bit 0 is set local_value[0] contains a local value, if bit 1 is set local_value[1] contains a local value, and so on.

Working With Arbitrary Memory Locations

Our local_value stores 8 bytes and base could be any address. If we align base such that it always contains an address at an 8-byte boundary, its lowest three bytes will always be zero. For a memory address, these bits contain the index into local_value.

Here are the bits of a 32-bit memory address with their meaning for access to struct resource.

    | 31 .. 13  12 11 10  9  8  7  6  5  4  3 |  2  1  0 |
    |                  Base                   |   Index  |

For mapping a memory address to a byte in a resource structure, first we have to make sure that the base values of address and resource are the same, then use the address’ lowest three bits as index into local_value.

So far we’ve had two values of type struct int_resource. If we had a single resource structure in our transaction manager, we could load and store 8 consecutive bytes for the transactions. To load and store more memory, we have to add more instances; let’s say 1024.

The code fragment below creates an array of 1024 resource structures.

#define NRESOURCES_BITSHIFT (10)
#define NRESOURCES          (1ul << NRESOURCES_BITSHIFT)

struct resource g_resource[NRESOURCES];

We could assign a base address to each array element and search in the array whenever we want to map an address to a resource with corresponding base address. While this would work, there’s an easy way to compute the correct element directly.

Storing the position of element of the array requires exactly 10 bit. These 10 bit are located in the memory address directly before the index; or in other words, they are the next higher bits above the index.

    | 31 .. 13 | 12 11 10  9  8  7  6  5  4  3 |  2  1  0 |
    |          |             Element           |          |
    |                   Base                   |   Index  |

For mapping a memory address to a byte in a resource structure, we can extract the element position (bits 3 to 12), get the element from the element array we declared, make sure that the base values of address and resource are the same, and then use the address’ lowest three bits as index into local_value.

This look-up scheme is very fast and ensures that resources are consecutive in memory as well as the bytes of each resource. It is therefore possible to operate on values that are larger than 8 bytes. For example, if we load or store a value of 16 bytes, we first operate on the resource structure covering the value’s first bytes, then operate on the resource structure covering the next bytes, and so on.

Loading and Storing

Before we go into the details of the load and store functions, let us look at the new interfaces. Because we don’t use int directly any more, the new interfaces take memory addresses and buffers.

void
load(uintptr_t addr, void* buf, size_t siz);

void
store(uintptr_t addr, const void* buf, size_t siz)

The value addr is the address of the shared value. The application logic is not required to know about the resource any more. The transaction manager maintains these internally. The values buf and siz give a transaction-local buffer and the number of bytes in the buffer.

The complexity is now in the implementation of the load and store function. Here is store().

void
store(uintptr_t addr, const void* buf, size_t siz)
{
    const uint8_t* mem = (const uint8_t*)buf;

    while (siz) {

        struct resource* res = acquire_resource(addr & BASE_BITMASK);
        if (!res) {
            tm_restart();
        }

        unsigned long index = addr & RESOURCE_BITMASK;
        unsigned long bits = 1ul << index;

        uint8_t* beg = arraybeg(res->local_value) + index;
        uint8_t* end = arrayend(res->local_value);

        while (siz && (beg < end)) {
            *beg = *mem;
            res->local_bits |= bits;

            bits <<= 1;
            --siz;
            ++addr;
            ++mem;
            ++beg;
        }
    }
}

store() transactionally stores all bytes in buf to the resources that cover addr and successiv memory locations. The function call to acquire_resource() acquires the resource for a specific base address and returns the resource’s data structure. If the resource cannot be acquired, the transaction is in conflict, NULL is returned and the transaction aborts.

Once we have the resource, we start filling its local_value field with the contents of buf. For each byte we copy, we set the corresponding bit in local_bits. We do this until we reach the end of either buf or local_value. If we reached the end of local_value and there are still bytes left in buf we continue the outer while loop with the next resource.

The load function is identical, except for the actual copy operation.

void
load(uintptr_t addr, void* buf, size_t siz)
{
    uint8_t* mem = (uint8_t*)buf;

    while (siz) {

        struct resource* res = acquire_resource(addr & BASE_BITMASK);
        if (!res) {
            tm_restart();
        }

        unsigned long index = addr & RESOURCE_BITMASK;
        unsigned long bits = 1ul << index;

        uint8_t* beg = arraybeg(res->local_value) + index;
        uint8_t* end = arrayend(res->local_value);

        while (siz && (beg < end)) {
            if (res->local_bits & bits) {
                *mem = *beg;
            } else {
                *mem = *((uint8_t*)addr);
            }

            bits <<= 1;
            --siz;
            ++addr;
            ++mem;
            ++beg;
        }
    }
}

Here we walk over the local values of the involved resources and copy into buf. In the inner while loop, we check if there’s a local value and either copy this or the globally shared value.

Our current setup can support 8192 bytes of transactional memory. If this limit is reached or if multiple memory locations map to the same resource, the transaction manager aborts the process. This would be detected by acquire_resource(). As a workaround to this limit the size of the resource array can be doubled until all variables are covered. A real-world implementation could also replace the array by a sparse look-up tree. That’s how it’s done in picotm.

For convenience, we can keep the load_int() and store_int() functions around. They are now mere wrappers around load() and store().

int
load_int(const int* addr)
{
    int value;
    load((uintptr_t)addr, &value, sizeof(value));
    return value;
}

void
store_int(int* addr, int value)
{
    store((uintptr_t)addr, &value, sizeof(value));
}

With helpers as simple as these, there can be plenty of type-specific functions that load and store float, long, complex double, or any other type.

Converting the Application

The old producer code looked like this.

struct int_resource g_int_resource[2];

static void
producer_func(void)
{
    unsigned int seed = 1;

    tm_save int i0 = 0;

    while (true) {

        sleep(1);

        ++i0;
        int i1 = rand_r(&seed);

        printf("Storing i0=%d, i1=%d\n", i0, i1);

        tm_begin

            store_int(g_int_resource + 0, i0);
            store_int(g_int_resource + 1, i1);

        tm_commit
    }
}

This translates into the following code.

static int g_i0;
static int g_i1;

static void
producer_func(void)
{
    unsigned int seed = 1;

    tm_save int i0 = 0;

    while (true) {

        sleep(1);

        ++i0;
        int i1 = rand_r(&seed);

        printf("Storing i0=%d, i1=%d\n", i0, i1);

        tm_begin

            store_int(&g_i0, i0);
            store_int(&g_i1, i1);

        tm_commit
    }
}

The global values of type struct int_resource are gone. Instead we work directly on integer types.

The consumer side looks similar.

static void
consumer_func(void)
{
    while (true) {

        sleep(1);

        int i0, i1;

        tm_begin

            i1 = load_int(&g_i1);
            i0 = load_int(&g_i0);

            verify_load(i0, i1);

        tm_commit

        printf("Loaded i0=%d, i1=%d\n", i0, i1);
    }
}

As in the previous post, we added a certain complexity to the transaction manager, but the application logic got a lot simpler. And just as before, we had to implement the transaction manager exactly once. Further application-specific changes are not required.

Summary

In this blog post, we removed the dedicated resource data structures from the interface of simpletm. The new interface loads and stores at arbitrary memory locations and all resource management is done internally.

You’ll find the full source code for this blog post on GitHub. If you’re interested in a more sophisticated C transaction manager, take a look at picotm.

If you like this series about writing a transaction manager in C, please subscribe to the RSS feed, follow on Twitter or share on social networks.

Post by: Thomas Zimmermann


Subscribe to news feed