2019q1 Homework7 (ringbuffer)
===
contributed by < `martinxluptak` >

## `mmap(2)`:
POSIX system call that maps files or devices onto memory. It naturally implements demand paging, because file contents are not read from disk initially and do not use physical RAM at all. The actual reads from disk are performed in a "lazy" manner, after a specific location is accessed.

## `mkstemp(3)`:
function generates a unique temporary filename from template, creates and opens the file, and returns an open file descriptor for the file. The last six characters of template must be "XXXXXX" and these are replaced with a string that makes the filename unique. Since it will be modified, template must not be a string constant, but should be declared as a character array.

Let's analyze the

## `cirbuf_offer()`:
Firstly, the following assignment is unnecessary:

written = size < written ? size : written;

We already know it will always evaluate to false because of the previous condition:

if (cirbuf_unusedspace(cb) <= size)
    return 0;

and simplify it accordingly:

/** Write data to the tail of the circular buffer.
 * Increases the position of the tail.
 * This copies data to the circular buffer using memcpy.
 * After calling you should free the data if you don't need it anymore.
 *
 * @param cb The circular buffer.
 * @param data Buffer to be written to the circular buffer.
 * @param size Size of the buffer to be added to the circular buffer in bytes.
 * @return number of bytes offered
 */
static inline int cirbuf_offer(cirbuf_t *cb,
                               const unsigned char *data,
                               const int size)
{
    /* prevent buffer from getting completely full or over commited */
    if (cirbuf_unusedspace(cb) <= size)
        return 0;

    memcpy(cb->data + cb->tail, data, size);
    cb->tail += size;

    if (cb->size < cb->tail)
            cb->tail -= cb->size;
    return size;
}

`cb->tail %= cb->size` is also valid, but unnecessary because of the aforementioned condition.

## `cirbuf_peek()`:

/** Look at data at the circular buffer's head.
 * Use cirbuf_usedspace to determine how much data in bytes can be read.
 * @param cb The circular buffer.
 * @return pointer to the head of the circular buffer
 */
static inline unsigned char *cirbuf_peek(const cirbuf_t *cb)

The function needs to return the position of `cb->head` which can be offset from the beginning of memory in case of freeing elements from the circular buffer. `cb->head` in this implementation is an integer rather than pointer, so we count the pointer position with `cb->data + cb->head`.

The original test suite does not check whether the mirroring is set up right. The underlying buffer's length must be a multiple of the system's page size so regions are mapped contiguously in virtual memory. Let's add a test which checks this condition. The return value of `cirbuf_new()` was modified to bool to indicate success or failure during initialization. In Linux, `getpagesize()` is a consistent way of detecting memory page size.

CuAssertTrue(tc, cirbuf_new(&cb, getpagesize()));

Additionally, we must check whether the circular property really works as expected and upon filling a page the buffer stays within address boundaries:

void TestCirbuf_page_flip(CuTest *tc)
{
    cirbuf_t cb;
    
    // fill up a memory page 
    CuAssertTrue(tc, cirbuf_new(&cb, getpagesize()));
    for (int i = 0 ; i < getpagesize() - 2 ; i+=2) {
            CuAssertTrue(tc, cirbuf_offer(&cb, (unsigned char *) "aa", 2) == 2);
    }

    // this should be one of the highest addresses in the buffer
    void * high = cirbuf_peek(&cb) + cb.tail;

    // release getpagesize() / 2 of buffer's memory
    cirbuf_poll(&cb, getpagesize() / 2 );
    void * high_peek = cirbuf_peek(&cb); 

    // further add getpagesize() / 4 characters to memory
    for (int i = 0 ; i < getpagesize() / 4 ; i += 2) {
            CuAssertTrue(tc, cirbuf_offer(&cb, (unsigned char *) "aa", 2) == 2);
    }
    
    // the tail will have crossed the boundary after adding getpagesize() / 4 characters
    // this address must be lower than 'void * high'
    void * low = cirbuf_peek(&cb) + cb.tail;
    CuAssertTrue(tc, high > low);

    // after the following release, head should also cross the boundary and return
    // to a low address position
    cirbuf_poll(&cb, (getpagesize() / 2) + 100); 
    void * low_peek = cirbuf_peek(&cb);
   CuAssertTrue(tc, high_peek > low_peek);
}

This buffer hack allows for precious execution time savings. Normally, we would want two `memcpy()` calls to write to non-contigious physical memory blocks, but this implementation only uses a single one.

## Circular buffer inside Linux
[Linux has its own circular buffer implementation/interface](https://elixir.bootlin.com/linux/latest/source/include/linux/circ_buf.h) which operates quickly when buffer space is an exact power of two.