lab0-c

contributed by < Eric Lin >

lab0 is a homework of the course Linux 核心設計/實作 by jserv

• My fork: lab0-c
• Original source code: lab0-c

This lab aims to assessing one's C Programming Skills. Some of the skills tested are:

• Explicit memory management, as required in C.
• Creating and manipulating pointer-based data structures.
• Working with strings.
• Enhancing the performance of key operations by storing redundant information in data structures.
• Implementing robust code that operates correctly with invalid arguments, including NULL pointers.

Check C Programming Lab for more information.

Environment

$ gcc --version
gcc (Ubuntu/Linaro 8.4.0-3ubuntu2) 8.4.0

$ lscpu
Architecture:                       aarch64
CPU op-mode(s):                     64-bit
Byte Order:                         Little Endian
CPU(s):                             8
On-line CPU(s) list:                0-7
Thread(s) per core:                 1
Core(s) per socket:                 8
Socket(s):                          1
NUMA node(s):                       1
Vendor ID:                          0x00
Model:                              0
Stepping:                           0x0
BogoMIPS:                           48.00
NUMA node0 CPU(s):                  0-7

Overview

Structures

Source: cprogramminglab

The file queue.h and list.h contains declarations of the following structures:

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

typedef struct {
    char *value;
    struct list_head list;
} element_t;

• list_head is a circular doubly-linked list for queue contents.
• element_t has fields value and list, storing a pointer to a string and a structure of queue list.

In the starter code, the queue contains only a single field of typelist_head, but you can add other fields list which is intruded in element_t.

In the picture above is a singly-linked list rather than a doubly-linked list in our case of implementing queue.

Check the benefits of using intrusive-linked-lists.

Macro

offsetof

#include <linux/stddef.h>

#define offsetof(TYPE, MEMBER)  ((size_t)&((TYPE *)0)->MEMBER)

From man page:

The macro offsetof() returns the offset of the field member from the start of the structure type.

1. (TYPE *)0: casting the value 0 to the pointer type Type *. Which places a struct object at memory address zero.
2. &((TYPE *)0)->MEMBER: getting the address of struct field MEMBER of this struct object. Since the address of struct object is 0, the the address of MEMBER is the offset in bytes.
3. Casting the address to an size_t which has the same size as a pointer.

container_of

container_of() is a macro defined in <linux/kernel.h>.

#define container_of(ptr, type, member) \ 
((type *) ((char *) (ptr) - offsetof(type, member)))

From kernel doc:

What container_of() does is to obtain a pointer to the containing struct from a pointer to a member by a simple subtraction using the offsetof() macro from standard C, which allows something similar to object oriented behaviours.
Notice that the contained member must not be a pointer, but an actual member for this to work.

According to C99 Standard in chapter 6.5.6 Additive operators

7. For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.
8. When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression.

It is neccessary to do (char *) cast in this macro to ensure that pointer arithmetic operates on a byte level basis. When you subtract an offset from a pointer, you are moving the pointer backward by the number of bytes indicated by the offset. However, the actual size of the structure might be different due to padding and alignment requirements.

For this point, We can see the following example:

#include <stdio.h>

#define offsetof(TYPE, MEMBER)  ((size_t)&((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) \
            ((type *) ((char *) (ptr) - offsetof(type, member)))
            
#define wrong_container_of(ptr, type, member) \
            ((type *) ((ptr) - offsetof(type, member)))
    
struct demo {
  int v1;
  float v2;
};

int main()
{
    struct demo s1, *s2;
    
    float *f = &s1.v2;
    
    printf("int: %lu, float: %lu\n", sizeof(int), sizeof(float));
    printf("s1: %p\n", &s1);
    
    s2 = container_of(f, struct demo, v2);
    printf("s2: %p\n", s2);
    
    s2 = wrong_container_of(f, struct demo, v2);
    printf("s2: %p\n", s2);

    return 0;
}

result:

int: 4, float: 4
s1: 0x7ffd968da760
s2: 0x7ffd968da760
s2: 0x7ffd968da754

In the example, when we apply the container_of macro, the addresses of s1 and s2 match. However, when wrong_container_of macro is applied, 16 bytes(sizeof(float) * 4 == 16) of offset has been conduct, the addresses of two don't match.

Functions for Queue

q_new

Return NULL if a failing call to malloc().

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (!q)
        return NULL;
    INIT_LIST_HEAD(q);
    return q;
}

q_free

Traverse elements linked to list_head and free each of them.

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *entry = NULL, *next = NULL;
    list_for_each_entry_safe (entry, next, l, list)
        q_release_element(entry);
    free(l);
}

q_insert_head

strdup returns a pointer to a new string which is a duplicate of the string s. A terminating null byte ('\0') is also added.

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_ele = (element_t *) malloc(sizeof(element_t));
    if (!new_ele)
        return false;

    /* Make value point to a duplicate of s */
    if (!(new_ele->value = strdup(s))) {
        free(new_ele);
        return false;
    }

    list_add(&new_ele->list, head);

    return true;
}

q_insert_tail

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_ele = (element_t *) malloc(sizeof(element_t));
    if (!new_ele)
        return false;

    /* Make value point to a duplicate of s */
    if (!(new_ele->value = strdup(s))) {
        free(new_ele);
        return false;
    }

    list_add_tail(&new_ele->list, head);

    return true;
}

q_remove_head

Return NULL if head is NULL or empty.

Get the first element in queue by list_first_entry

strncpy copies the string pointed to by ele->value.

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ele = list_first_entry(head, element_t, list);
    list_del(&ele->list);

    if (sp) {
        strncpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return ele;
}

q_remove_tail

/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ele = list_last_entry(head, element_t, list);
    list_del(&ele->list);

    if (sp) {
        strncpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return ele;
}

q_size

Traverse each list in head and count them by i.

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    struct list_head *n = NULL;
    int i = 0;
    list_for_each (n, head)
        i++;

    return i;
}

q_delete_mid

Move the head node forward and the tail node backward untill reaching the middle node.

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;

    struct list_head *f = head->next;
    for (struct list_head *b = head->prev; b != f && f->next != b;) {
        b = b->prev;
        f = f->next;
    }

    list_del(f);
    q_release_element(list_entry(f, element_t, list));

    return true;
}

q_reverse

Traverse list and swap their next and prev.

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return;
    }

    struct list_head *pos = head, *tmp;

    // traverse list and swap their next and prev
    do {
        tmp = pos->next;
        pos->next = pos->prev;
        pos->prev = tmp;
        pos = pos->prev;
    } while (pos != head);
}

q_sort

Recursive quick sort.

struct list_head *merge_sort(struct list_head *start, struct list_head *end)
{
    // if only one node, just return
    if (start == end)
        return start;

    // find mid point and split into 2 parts
    struct list_head *mid = start, *flag = start;
    for (; flag->next && flag->next->next; flag = flag->next->next)
        mid = mid->next;

    flag = mid->next;
    mid->next = NULL;

    // keep spliting on both parts
    struct list_head *left = merge_sort(start, mid);
    struct list_head *right = merge_sort(flag, end);

    // merge 2 splited list
    struct list_head *new_head = start, **p_tmp = &new_head;

    for (element_t *l, *r; left && right; p_tmp = &(*p_tmp)->next) {
        l = list_entry(left, element_t, list);
        r = list_entry(right, element_t, list);

        struct list_head **next;
        next = strcmp(l->value, r->value) < 0 ? &left : &right;
        *p_tmp = *next;
        *next = (*next)->next;
    }

    *p_tmp = left ? left : right;

    return new_head;
}

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head || head->prev == head->next)
        return;

    // do merge sort on list
    struct list_head *start = head->next, *end = head->prev;
    end->next = NULL;

    // connect head and sorted list
    head->next = merge_sort(start, end);
    head->next->prev = head;

    // repair all prev links
    for (end = head; end->next; end = end->next)
        end->next->prev = end;
    end->next = head;
    head->prev = end;

    if (descend)
        q_reverse(head);
}

q_descend

First convert the list to non-circular by end->next = NULL to creating a stop condition.
If current value is not greater than the next value, delete the node.
In the end, convert the list back to circular list by linking the end and the head node.

static void descend(struct list_head *head);
static void descend(struct list_head *head)
{
    if (!head)
        return;

    descend(head->next);

    if (!head->next)
        return;

    element_t *e_cur = list_entry(head, element_t, list);
    element_t *e_next = list_entry(head->next, element_t, list);

    if (strcmp(e_cur->value, e_next->value) < 0) {
        list_del(head);
        q_release_element(e_cur);
    }
    return;
}

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    /* Convert to a null-terminated singly-linked list. */
    head->prev->next = NULL;

    descend(head->next);

    struct list_head *end = NULL;
    /* Repair end next link */
    for (end = head; end->next; end = end->next)
        ;
    end->next = head;
    head->prev = end;

    return q_size(head);
}

q_merge

Extract each link list from queue and join them in the first queue.
Do quick sort.

/* Merge all the queues into one sorted queue, which is in ascending/descending
 * order */
int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    struct list_head *cur = head->next, *l = NULL, *start = NULL;

    while ((uintptr_t) cur != (uintptr_t) head) {
        queue_contex_t *ctx = list_entry(cur, queue_contex_t, chain);
        l = ctx->q;
        cur = cur->next;

        if (!start)
            start = l;
        else
            list_splice_tail_init(l, start);
    }

    q_sort(start, descend);

    return q_size(start);
}