# 2021q1 Homework2(quiz2)
contributed by < `kksweet8845` >

:::warning
Let's replace "question" with "problem."
Quoted from [What is the difference between a problem and a question?](https://www.quora.com/What-is-the-difference-between-a-problem-and-a-question):
> Problems are something to solve. Questions are something to ask.

:notes: jserv
:::

## Problem 1

### Description
This question uses `list.h` which implement the linked list as a module. That is, you can use this library to realize the multiple manupulation of linked list. The following is the description of some functions.

#### `list_add_tail`

According to the name of this function, we can realize that the function could add a node to the end of a list.

digraph G {
    
    node[shape="record"]
    rankdir=LR
    nodeA[label="node A"]
    list0[label="list Head"]
    list1[label="list 0"]
    list2[label="list 1"]
    list3[label="list 2"]
    
    list0 -> list1
    list1 -> list2
    list2 -> list3
}

That is, the node A will connect to the end of the list.

digraph G {
    
    node[shape="record"]
    rankdir=LR
    nodeA[label="node A"]
    list0[label="list Head"]
    list1[label="list 0"]
    list2[label="list 1"]
    list3[label="list 2"]
    
    list0 -> list1
    list1 -> list2
    list2 -> list3
    list3 -> nodeA
}

static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
    struct list_head *prev = head->prev;

    prev->next = node;
    node->next = head;
    node->prev = prev;
    head->prev = node;
}

We can see that the `prev` variable point to the `list 2`. And it just connect `list 2` and `node A` together.

#### `get_middle`
In this function, we can see that there are two pointer, slow and fast. `slow` step one node at a time and `fast` step twice at a time. And, if the `fast` pointer goes to the end, it means the `slow` one got the middle node. And, it should return the address of `slow`.

static list_ele_t *get_middle(struct list_head *list)
{
    struct list_head *fast = list->next, *slow;
    list_for_each (slow, list) {
        if (COND1 || COND2)
            break;
        fast = fast->next->next;
    }
    return list_entry(TTT, list_ele_t, list);
}

#### `container_of`

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

- `__extension__` which is just an empty literally.

#if !__GNUC_PREREQ (2,8)
# define __extension__		/* Ignore */
#endif

- `__typeof__` is the version of `typeof` in ansi C and ISO C, which have no extension `typeof`.
Right now, we can regard the code above as following.

#define container_of(ptr, type, member)                            \
    ({ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

- And the statement are enclosed with a pair of {},which is called compound statement. It may appear as an expression in GNU C. This allows you to use loops, switches, and local variables within an expression.

Let take a look at `&(((type *) 0)->member)`, according to the c standard, it said
- `(type*)0` : represent a null pointer constant of that type
- And the `NULL` expands to an implementation-defined null pointer constant
- >> It specifically defined that `&((type*0)->member)` is the offset in bytes, to the structure member(designated by member-designator), from the beginning of its structure(designed by type).
- That is, `((type *) 0)->member` means the member which derivated by member-designator.
- `__typeof__(((type *) 0)->member)` define the type of that struct member, which is used to declared a pointer to that sturct,`__typeof__(((type *) 0)->member) *`,named `__pmember`. Finally, let `__pmember` points to the given address of the specific structure address.

Now, it's time to consider the expression,`(type *) ((char *) __pmember - offsetof(type, member))`
- It converses `__pmember` to the type of pointer of char,which make the `__pmember` shifts according to its type, that is, one byte per shift.
- Then, The macro `offsetof(type,member)` is defined by c standard
> `offsetof(type, member-designator)`, which expands to an integer constant expression that has type `size_t`, the value of which is the offset in bytes, to the structure member(designated by member-designator), from the beginning of its tructure(designated by type).
- That is, `(type *) ((char *) __pmember - offsetof(type, member))` will return the address of the structure containing the given object of member structure.

### `Linux/list_sort.c`

#### `list_sort`
The `list_sort.c`, this function implements the merge sort algorithm and have two merge function, `merge` and `merge_final`.
- `merge`:
- which will merge a list to the another.
- `merge_final`:
- which will merge two lists into a list called `head`.

#### Optimization

The optimization method is to guarantee the worst case of 2:1 imbalance merge. Its method is to use the doublely linked list as a list of list, which means the `prev` points to the next list and `next` points to the next node. And, there will be several list of list.

digraph G {

    node[shape="box"]

    A_0[label="A 0"]
    A_1[label="A 1"]
    A_2[label="A 2"]
    A_3[label="A 3"]
    B_0[label="B 0"]
    B_1[label="B 1"]
    B_2[label="B 2"]
    C_0[label="C 0"]
    C_1[label="C 1"]
    C_2[label="C 2"]
    

    A_0 -> A_1 [label="next"]
    A_1 -> A_2 [label="next"]
    A_2 -> A_3 [label="next"]
    B_0 -> B_1 [label="next"] 
    B_1 -> B_2 [label="next"]
    {
        rank="same"
        A_0 -> B_0 [label="prev"]
        B_0 -> C_0 [label="prev"]
        
    }
    C_1 -> C_2 [label="next"]
    C_0 -> C_1 [label="next"]
}

And the optimization method is to add a node a list called `pending`, which is the head of list of list.

> Data structure invariants:
> - All lists are singly linked and null-terminated; prev
> pointers are not maintained.
> - pending is a prev-linked "list of lists" of sorted
> sublists awaiting further merging.
> - Each of the sorted sublists is power-of-two in size.
> - Sublists are sorted by size and age, smallest & newest at front.
> - There are zero to two sublists of each size.
> - A pair of pending sublists are merged as soon as the number
> of following pending elements equals their size (i.e.
> each time count reaches an odd multiple of that size).
> That ensures each later final merge will be at worst 2:1.
> - Each round consists of:
> - Merging the two sublists selected by the highest bit
> which flips when count is incremented, and
> - Adding an element from the input as a size-1 sublist.
>

The following graph demonstrates the quote above.
- Before the beginning of while loop

digraph G {
    rankdir=LR
    node[shape="box"]
    NULL[shape="plaintext"]
    pending -> NULL
}

- count = 0 (00)
- it executes the following code and a node moved from input list to pending.

/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;

digraph G {
    node[shape="box"]
    NULL[shape="plaintext"]
    NULL0[shape="plaintext", label="NULL"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    
    
    {
        rank="same"
        node0 -> NULL [label="prev"]
    }
    pending -> node0
    node0 -> NULL0 [label="next"]

}

- count = 1 (01), means a node have being added to the list `pending`.

The following code will find the least-significant clear bit in count.

/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
    tail = &(*tail)->prev;

Then if the `bits` is greater than 0, it will merge the list. However, there is only one node and the `tail` will point to `NULL`. The following code will ==not== be executed.

/* Do the indicated merge */
if (likely(bits)) { // expect to be 1 (true)
    struct list_head *a = *tail, *b = a->prev;

    a = merge(priv, (cmp_func)cmp, b, a);
    /* Install the merged result in place of the inputs */
    a->prev = b->prev;
    *tail = a;
}

Then add an element node to the pending list again.

digraph G {
    node[shape="box"]
    NULL[shape="plaintext"]
    NULL0[shape="plaintext", label="NULL"]
    NULL1[shape="plaintext", label="NULL"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    node1[label="node 1"]
    
    pending -> node1
    
    {
        rank="same"
        node1 -> node0 [label="prev"]
        node0 -> NULL  [label="prev"]
    }
    
    node1 -> NULL1 [label="next"]
    node0 -> NULL0 [label="next"]

}

- count = 2 (10)
It will merge the first and second node together by `merge` function.

digraph G {
    node[shape="box"]
    // NULL[shape="plaintext"]
    NULL0[shape="plaintext", label="NULL"]
    NULL1[shape="plaintext", label="NULL"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    node1[label="node 1"]
    
    pending -> node1
    
    {
        rank="same"
        node1 -> NULL1 [label="prev"]
    }
    
    node1 -> node0 [label="next"]
    node0 -> NULL0 [label="next"]

}

then add a node

digraph G {
    node[shape="box"]
    // NULL[shape="plaintext"]
    NULL0[shape="plaintext", label="NULL"]
    NULL1[shape="plaintext", label="NULL"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    node1[label="node 1"]
    node2[label="node 2"]
    
    pending -> node1
    
    {
        rank="same"
        node1 -> node2 [label="prev"]
        node2 -> NULL1 [label="prev"]
    }
    
    node1 -> node0 [label="next"]
    node0 -> NULL0 [label="next"]

}

- count = 3 (11)

digraph G {
    node[shape="box"]
    // NULL[shape="plaintext"]
    NULL0[shape="plaintext", label="NULL"]
    NULL1[shape="plaintext", label="NULL"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    node1[label="node 1"]
    node2[label="node 2"]
    node3[label="node 3"]
    
    pending -> node1
    
    {
        rank="same"
        node1 -> node2 [label="prev"]
        node2 -> node3 [label="prev"]
        node3 -> NULL1 [label="prev"]
    }
    
    node1 -> node0 [label="next"]
    node0 -> NULL0 [label="next"]

}

- count = 4 (100)

digraph G {
    node[shape="box"]
    NULL[shape="plaintext"]
    NULL0[shape="plaintext", label="NULL"]
    NULL1[shape="plaintext", label="NULL"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    node1[label="node 1"]
    node2[label="node 2"]
    node3[label="node 3"]
    node4[label="node 4"]
    
    pending -> node1
    
    {
        rank="same"
        node1 -> node2 [label="prev"]
        node2 -> node4 [label="prev"]
        node4 -> NULL  [label="prev"]
    }
    
    node1 -> node0 [label="next"]
    node0 -> NULL0 [label="next"]
    
    node2 -> node3 [label="next"]
    node3 -> NULL1 [label="next"]

}

- count = 5 (101)
NULL is ignored.

digraph G {
    node[shape="box"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    node1[label="node 1"]
    node2[label="node 2"]
    node3[label="node 3"]
    node4[label="node 4"]
    node5[label="node 5"]
    
    pending -> node3
    
    {
        rank="same"
        node3 -> node4 [label="prev"]
        node4 -> node5 [label="prev"]
        
    }
    
    node3 -> node2[label="next"]
    node2 -> node1[label="next"]
    node1 -> node0[label="next"]
    
    

}

- count = 6 (110)

digraph G {
    node[shape="box"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    node1[label="node 1"]
    node2[label="node 2"]
    node3[label="node 3"]
    node4[label="node 4"]
    
    pending -> node3
    
    {
        rank="same"
        node3 -> node5 [label="prev"]
        node5 -> node6
        
    }
    
    node3 -> node2[label="next"]
    node2 -> node1[label="next"]
    node1 -> node0[label="next"]
    
    node5 -> node4[label="next"]
    

}

- count = 7 (111)

digraph G {
    node[shape="box"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    node1[label="node 1"]
    node2[label="node 2"]
    node3[label="node 3"]
    node4[label="node 4"]
    node7[label="node 7"]
    
    pending -> node3
    
    {
        rank="same"
        node3 -> node5 [label="prev"]
        node5 -> node6 [label="prev"]
        node6 -> node7 [label="prev"]
        
    }
    
    node3 -> node2[label="next"]
    node2 -> node1[label="next"]
    node1 -> node0[label="next"]
    
    node5 -> node4[label="next"]
    

}

- count = 8 (1000)

digraph G {
    node[shape="box"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    node1[label="node 1"]
    node2[label="node 2"]
    node3[label="node 3"]
    node4[label="node 4"]
    node7[label="node 7"]
    node8[label="node 8"]
    
    pending -> node3
    
    {
        rank="same"
        node3 -> node5 [label="prev"]
        node5 -> node7 [label="prev"]
        node7 -> node8 [label="prev"]
        
    }
    
    node3 -> node2[label="next"]
    node2 -> node1[label="next"]
    node1 -> node0[label="next"]
    
    node5 -> node4[label="next"]
    
    node7 -> node6[label="next"]
    

}

- count = 9 (1001)

digraph G {
    node[shape="box"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    node1[label="node 1"]
    node2[label="node 2"]
    node3[label="node 3"]
    node4[label="node 4"]
    node7[label="node 7"]
    node8[label="node 8"]
    node9[label="node 9"]
    
    pending -> node3
    
    {
        rank="same"
        node3 -> node7 [label="prev"]
        node7 -> node8 [label="prev"]
        node8 -> node9 [label="prev"]
        
    }
    
    node3 -> node2[label="next"]
    node2 -> node1[label="next"]
    node1 -> node0[label="next"]
    
    node7 -> node6[label="next"]
    node6 -> node5[label="next"]
    node5 -> node4[label="next"]
    

}

- count = 10 (1010)

digraph G {
    node[shape="box"]
    pending[label="pending", shape="plaintext"]
    node0[label="node 0"]
    node1[label="node 1"]
    node2[label="node 2"]
    node3[label="node 3"]
    node4[label="node 4"]
    node7[label="node 7"]
    node8[label="node 8"]
    node9[label="node 9"]
    node10[label="node 10"]
    
    pending -> node3
    
    {
        rank="same"
        node3 -> node7 [label="prev"]
        node7 -> node8 [label="prev"]
        node8 -> node10 [label="prev"]
        
    }
    
    node3 -> node2[label="next"]
    node2 -> node1[label="next"]
    node1 -> node0[label="next"]
    
    node7 -> node6[label="next"]
    node6 -> node5[label="next"]
    node5 -> node4[label="next"]
    
    node8 -> node9[label="next"]
    

}

Finally, it will become a list of list sized power of 2. Then merge all the list. The following is the `list_sort.c` source code.


:::warning
Can you emphasize on the state of bit k of "count" in details?
:notes: jserv
:::

---

## Problem 2

### Description
In order to obtain the most significant set bit, perform the right shift operation. Trying to set the first in the right of each set bit and then two in the right of each set bit and sot on. Such as `N = b'0001 0000 0000'`

N |= N >> 1; // b'0001 1000 0000 0000'
N |= N >> 2; // b'0001 1110 0000 0000'
N |= N >> 4; // b'0001 1111 1110 0000'
N |= N >> 8; // b'0001 1111 1111 1111'

Then `(N+1) >> 1` will get the most significant set bit because `b'0001 1111 1111 1111` is $2^{n} - 1$, so $(N+1)>>1=2^{n-1}$

### `is_power_of_2`

static inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
	return (n != 0 && ((n & (n - 1)) == 0));
}

The `is_power_of_2` function to check whether there is only one set bit in binary representation.

### `__roundup_pow_of_two`

/**
 * __roundup_pow_of_two() - round up to nearest power of two
 * @n: value to round up
 */
static inline __attribute__((const))
unsigned long __roundup_pow_of_two(unsigned long n)
{
	return 1UL << fls_long(n - 1);
}

`fls_long` function could find the last set bit. And `n-1` to avoid the input number which is equal to $2^k$, is pow of 2.

### `__rounddown_pow_of_two`

/**
 * __rounddown_pow_of_two() - round down to nearest power of two
 * @n: value to round down
 */
static inline __attribute__((const))
unsigned long __rounddown_pow_of_two(unsigned long n)
{
	return 1UL << (fls_long(n) - 1);
}

`fls_long` function could find the last set bit. `fls_long(n) - 1` is also to avoid the input number which is equal to $2^k$, is pow of 2.

And, we know that this function is not constant time complexity function, it depends on the input number. So this function could be impemented in constant time complexity.

uint32_t __rounddown_pow_of_two_const(uint32_t N){
    N |= N >> 1;
    N |= N >> 2;
    N |= N >> 4;
    N |= N >> 8;
    N |= N >> 16;
    
    return (N+1) >> 1;
}

### `rounddup_pow_of_two(n)`

#define roundup_pow_of_two(n)			\
(						\
	__builtin_constant_p(n) ? (		\
		((n) == 1) ? 1 :		\
		(1UL << (ilog2((n) - 1) + 1))	\
				   ) :		\
	__roundup_pow_of_two(n)			\
 )

We can see that `roundup_pow_of_two` has two different implementation when the `__builtin_constant_p` is true. And, according to document of GCC, it said,

>You can use the built-in function __builtin_constant_p to determine if a value is known to be constant at compile time and hence that GCC can perform constant-folding on expressions involving that value. The argument of the function is the value to test. The function returns the integer 1 if the argument is known to be a compile-time constant and 0 if it is not known to be a compile-time constant. A return of 0 does not indicate that the value is not a constant, but merely that GCC cannot prove it is a constant with the specified value of the -O option.

In compile phrase, compiler can do the constant folding optimization and also this function will go to the former expression that is possibly constant number. And the `ilog2` also cover the optimization for constant number. We can see the following implementation of `ilog2`

#define ilog2(n) \
( \
	__builtin_constant_p(n) ?	\
	((n) < 2 ? 0 :			\
	 63 - __builtin_clzll(n)) :	\
	(sizeof(n) <= 4) ?		\
	__ilog2_u32(n) :		\
	__ilog2_u64(n)			\
 )

It can be computed in compile phrase. `__builtin_clzll` return the number of leading 0-bits in x, start at the most significant bit position. If x is 0, the result is undefined.

That is, it can be initilized in compile phrase for global variable. And also covering the none constant number. `rounddown_pow_of_two` has same mechanism for efficiency.

### Slab allocator

[Description](https://hackmd.io/@kksweet8845/rJdGY4UQu)

And, the code uses the `is_power_of_2` in `void create_boot_cache`.

void __init create_boot_cache(struct kmem_cache *s, const char *name,
		unsigned int size, slab_flags_t flags,
		unsigned int useroffset, unsigned int usersize)
{
	int err;
	unsigned int align = ARCH_KMALLOC_MINALIGN;

	s->name = name;
	s->size = s->object_size = size;

	/*
	 * For power of two sizes, guarantee natural alignment for kmalloc
	 * caches, regardless of SL*B debugging options.
	 */
	if (is_power_of_2(size))
		align = max(align, size);
	s->align = calculate_alignment(flags, align, size);

	s->useroffset = useroffset;
	s->usersize = usersize;

	err = __kmem_cache_create(s, flags);

	if (err)
		panic("Creation of kmalloc slab %s size=%u failed. Reason %d\n",
					name, size, err);

	s->refcount = -1;	/* Exempt from merging for now */
}

guarantee the cache of alignment of power of 2 sizes.

---

## Problem 3

### Code Description

## Problem 4

### Code Description

[cstr]() covers the following mechanism for which can perform the

digraph G {
    a -> b
}