# 2019q1 第 4 週測驗題 (下)
:::info
目的: 檢驗學員對 C 程式設計的認知
:::

---

### 測驗 `1`

考慮略為複雜的 reference counting 實作，如下:

#include <limits.h>                                                                                                                                           
#include <stddef.h>
#include <stdlib.h>

/**
 * Destructor callback.
 * \param ptr Pointer to space to destroy and free
 */
typedef void (*rc_dtor)(void *ptr);

typedef int volatile refcnt;
#define REFCOUNTER_MAX (INT_MAX / 2)

/* FIXME: reference counting should be robust against race conditions in
 * multi-threaded applications. Use C11 atomics.
 */
static inline refcnt refcnt_acquire(refcnt *dest) {
    return (*dest += 1) - 1;
}
static inline refcnt refcnt_release(refcnt *dest) {
    return (*dest -= 1) + 1;
}

struct refcnt_entry {
    refcnt n;
    rc_dtor dtor;
    void *ptr;
};

/**
 * \brief Allocate some reference counted space
 * \param sz Size of space in bytes
 * \param dtor Destructor to use in case of free
 * \return the space on sucess, NULL otherwise
 */
void *rc_malloc(size_t sz, rc_dtor dtor) {
    size_t const static rc_offset = offsetof(struct refcnt_entry, ptr);
    size_t const static max_size = (WW) - offsetof(struct refcnt_entry, ptr);
    if (sz >= max_size)
        goto reject;
    void *out = malloc(sz + rc_offset);
    if (out) { 
        struct refcnt_entry *const outref = (struct refcnt_entry *) out;
        outref->n = 1; 
        outref->dtor = dtor;
        return XX;
    }
reject:
    return NULL;
}

/**
 * \brief Acquire a reference to some space
 * \param ptr pointer, previously allocated with `rc_malloc`
 * \return the same pointer on sucess, NULL otherwise
 */ 
void *rc_acquire(void *ptr) {
    size_t const static rc_offset = offsetof(struct refcnt_entry, ptr);
    struct refcnt_entry *const ptrref =
        (struct refcnt_entry *) (void *) (((char *) ptr) - rc_offset);
    /* try to acquire a reference */
    refcnt next = refcnt_acquire(&ptrref->n);
    if (YY)
        return ptr;
    /* artifically refuse the reference */
    refcnt prev = refcnt_release(&ptrref->n);
    if (prev == 1) {
        if (ptrref->dtor)
            (*ptrref->dtor)(ptr);
        free(ptrref);
    }
    return NULL;
}

/**
 * \brief Release a reference to some space
 * \param ptr pointer, previously allocated with `rc_malloc`
 * \note If the reference count drops to zero, the space is freed.
 */
void rc_release(void *ptr) {
    size_t const static rc_offset = offsetof(struct refcnt_entry, ptr);
    if (!ptr)
        return;
    struct refcnt_entry *const ptrref =
        (struct refcnt_entry *) ZZ;
    /* release the reference */
    refcnt prev = refcnt_release(&ptrref->n);
    if (prev == 1) {
        if (ptrref->dtor)
            (*ptrref->dtor)(ptr);
        free(ptrref);
    }
}

/* -- unit test -- */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

static void test_destructor(void *);
static void *test_thread(void *);
struct test_box *test_constructor(int j);

struct test_box { int j; };

struct test_box *test_boxes[10] = {NULL, NULL, NULL, NULL, NULL,
                                   NULL, NULL, NULL, NULL, NULL};

int test_repeat_count = 1000000;

struct test_box *test_constructor(int j) {
    struct test_box *box = rc_malloc(sizeof(struct test_box), &test_destructor);
    assert(box != NULL);
    box->j = j;
    fprintf(stderr, "created item %d\n", box->j);
    return box;
}
void test_destructor(void *arg) {
    struct test_box *const box = (struct test_box *) arg;
    fprintf(stderr, "destroying item %d\n", box->j);
    box->j = -1;
    return;
}

void *test_thread(void *arg) {
    int const thread_id = *(int *) arg;
    int const repeat_count = test_repeat_count;
    int personal_refs[10];
    int faults = 0;
    int overdrops = 0;
    int outstanding = 0;
    fprintf(stderr, "[Thread %i starting]\n", thread_id);
    for (int i = 0; i < 10; ++i) {
        personal_refs[i] = 0;
    }
    for (int i = 0; i < repeat_count; ++i) {
        int const step_rand = rand();
        int command = step_rand % 2;
        int j = (step_rand / 2) % 10;
        if (command == 0) {
            /* acquire */
            struct test_box *box;
            box = rc_acquire(test_boxes[j]);
            if (box == test_boxes[j]) {
                personal_refs[j] += 1;
            } else
                faults += 1;
        } else {
            /* release */
            if (personal_refs[j] > 0) {
                rc_release(test_boxes[j]);
                personal_refs[j] -= 1;
            } else
                overdrops += 1;
        }
    }
    for (int i = 9; i >= 0; --i) {
        while (personal_refs[i] > 0) {
            rc_release(test_boxes[i]);
            outstanding += 1;
            personal_refs[i] -= 1;
        }
    }
    fprintf(stderr,
            "[Thread %i done: %i faults, %i overdrops, %i outstanding]\n",
            thread_id, faults, overdrops, outstanding);
    return NULL;
}

int main(int argc, char **argv) {
    int corrupt_count = 0;
    srand((int) (time(NULL)));
    /* make the boxes */ {
        for (int j = 0; j < 10; ++j) {
            test_boxes[j] = test_constructor(j);
        }
    }
    /* run thread start code */ {
        int thread_i = 0;
        test_thread(&thread_i);
    }
    /* inspect boxes */ {
        for (int j = 0; j < 10; ++j) {
            if (test_boxes[j]->j != j) {
                fprintf(stderr, "Box %i was corrupted.\n", j);
                corrupt_count += 1;
            }
            rc_release(test_boxes[j]);
            test_boxes[j] = NULL;
        }
    }
    return corrupt_count == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
}  

預期的輸出如下: (其中一例)

created item 0
created item 1
created item 2
created item 3
created item 4
created item 5
created item 6
created item 7
created item 8
created item 9
[Thread 0 starting]
[Thread 0 done: 0 faults, 2575 overdrops, 2721 outstanding]
destroying item 0
destroying item 1
destroying item 2
destroying item 3
destroying item 4
destroying item 5
destroying item 6
destroying item 7
destroying item 8
destroying item 9

請補完程式碼。

==作答區==

WW = ?
* `(a)` ptr
* `(b)` ~((uint8_t) 0U)
* `(c)` ~((size_t) 0U)

XX = ?
* `(a)` outref
* `(b)` outref->ptr
* `(c)` (*outref)->ptr
* `(d)` &(outref->ptr)

YY = ?
* `(a)` next == REFCOUNTER_MAX
* `(b)` next > REFCOUNTER_MAX
* `(c)` next < REFCOUNTER_MAX
* `(d)` next >= REFCOUNTER_MAX
* `(e)` 0

ZZ = ?
* `(a)` ptr
* `(b)` ~((size_t) 0U) - rc_offset
* `(c)` ptr - rc_offset
* `(d)` (char *) ptr - rc_offset
* `(e)` (void *) (((char *) ptr) - rc_offset)

:::success
延伸問題:
1. 在 Linux 核心找出類似的 reference counting 程式碼並解說;
2. 用上述的 reference counting 解釋 `lsmod` 命令輸出的 `Used by` 運作原理，需要分析程式碼並設計實驗
:::