2021q1 Homework2 (quiz2)

tags: linux2021

contributed by < Billy4195 >

Problem Set

Problem 1

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);
}

Explanation

get_middle() uses two pointer fast and slow to traverse the linked-list try to get the middle element. The algorithm is that the fast pointer move two-step(two elements) in each iteration. When it reach the end of the list, the middle element is pointed by the slow pointer.

So the end condition for the traverse is when the fast pointer reach the end of the linked-list.

COND1 = ?
(c) fast->next == list

COND2 = ?
(b) fast->next->next == list

MMM = ?
(e) &get_middle(&q->list)->list

TTT = ?
(a) slow

Extened questions

• Explain the implementation
  • Try to improve the implementation
• Read the lib/list_sort.c in Linux kernel, and learn from sysprog21/linux-list.
  • Extract the lib/list_sort.c to be a standalone user level application.
  • Design profiling experiments and explain the optimization in Linux kernel
• Improve implementation of quiz1 and compare with lib/list_sort.c using benchmark

Quiz 2

The func receive an 16bits unsigned int N, it will return an number which is power of 2 and less than or equal to N

Explanation

uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> X;
    N |= N >> Y;
    N |= N >> Z;

    return (N + 1) >> 1;
}

At the first glance, it's hard to understand how it works. However, I guess the answers of X, Y, Z may have something to do with power of 2.

I write a simple program to test the behavior of this function, and fill the X, Y and Z with 2, 4, 8, respectively.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> 2;
    N |= N >> 4;
    N |= N >> 8;

    return (N + 1) >> 1;
}

int main() {
    uint16_t ret = 0;
    ret = func(7);
    printf("func(7) = %u\n", ret);
    ret = func(26);
    printf("func(26) = %u\n", ret);

    return 0;
}

$ gcc -o test main.c
$ ./test
func(7) = 4
func(26) = 16

The program works as expected so far, and we need to understand what it did.

For N = 7

If the given N for the func is 7, the binary expression is 0000111

After Line 7 executed (N |= N >> 1), N is still 7. After Line 7-10 is executed, the N remains 7.

The finaly statement add 1 to N (N=8 00001000), and right shift 1 bit will be 4 (00000100).

For N = 26

The binary expression of 26 is 00011010

N |= N >> 1

N = 00011111 = 31

N |= N >> 2

N = 00011111 = 31

N |= N >> 4

N = 00011111 = 31

N |= N >> 8

N = 00011111 = 31

(N+1) >> 1

N = 00001000 = 16

---

According above two cases, I guess the func will fill all the bits on the right hand side of the leading 1 bit with 1, and the add 1 to make it be an number is power of 2 and larger than N. Then the right shift 1 bit to make it to be an power of 2 and less than or equal to N.

Prove from the simplified uint8_t cases

To prove my guessing is correct, I take a simplified case for uint8.

The func will become as follows:

uint8_t func(uint8_t N) {
    N |= N >> 1;
    N |= N >> 2;
    N |= N >> 4;
    
    return (N+1) >> 1;
}

For the given unsigned 8 bits integer

For the given N is 128

For N |= N >> 1

For N |= N >> 2

For N |= N >> 4

---

TODO: Explain implementation
TODO: Add more complex test cases
Discuss the case of N = MAX_UINT16 or 0

X = ?
(b) 2

Y = ?
(d) 4

Z = ?
(h) 8

Quiz 3

#include <stdint.h>

void bitcpy(void *_dest,      /* Address of the buffer to write to */
            size_t _write,    /* Bit offset to start writing to */
            const void *_src, /* Address of the buffer to read from */
            size_t _read,     /* Bit offset to start reading from */
            size_t count)
{
    size_t read_lhs = _read & 7;
    size_t read_rhs = 8 - read_lhs;
    const uint8_t *source = (const uint8_t *) _src + (_read / 8);
    size_t write_lhs = _write & 7;
    size_t write_rhs = 8 - write_lhs;
    uint8_t *dest = (uint8_t *) _dest + (_write / 8);

    static const uint8_t read_mask[] = {
        0x00, /*    == 0    00000000b   */
        0x80, /*    == 1    10000000b   */
        0xC0, /*    == 2    11000000b   */
        0xE0, /*    == 3    11100000b   */
        0xF0, /*    == 4    11110000b   */
        0xF8, /*    == 5    11111000b   */
        0xFC, /*    == 6    11111100b   */
        0xFE, /*    == 7    11111110b   */
        0xFF  /*    == 8    11111111b   */
    };

    static const uint8_t write_mask[] = {
        0xFF, /*    == 0    11111111b   */
        0x7F, /*    == 1    01111111b   */
        0x3F, /*    == 2    00111111b   */
        0x1F, /*    == 3    00011111b   */
        0x0F, /*    == 4    00001111b   */
        0x07, /*    == 5    00000111b   */
        0x03, /*    == 6    00000011b   */
        0x01, /*    == 7    00000001b   */
        0x00  /*    == 8    00000000b   */
    };

    while (count > 0) {
        uint8_t data = *source++;
        size_t bitsize = (count > 8) ? 8 : count;
        if (read_lhs > 0) {
            RRR;
            if (bitsize > read_rhs)
                data |= (*source >> read_rhs);
        }

        if (bitsize < 8)
            data &= read_mask[bitsize];

        uint8_t original = *dest;
        uint8_t mask = read_mask[write_lhs];
        if (bitsize > write_rhs) {
            /* Cross multiple bytes */
            *dest++ = (original & mask) | (data >> write_lhs);
            original = *dest & write_mask[bitsize - write_rhs];
            *dest = original | (data << write_rhs);
        } else {
            // Since write_lhs + bitsize is never >= 8, no out-of-bound access.
            DDD;
            *dest++ = (original & mask) | (data >> write_lhs);
        }

        count -= bitsize;
    }
}

Explanation

RRR = ?

(a) data <<= read_lhs

For line 43-47, data will store the first 1 bytes data from source.

If read_lhs == 0, then data is just the same as source
If read_lhs > 0, we need to eliminate the bits of left hand side.
Therefore, RRR should be (a) which left shift read_lhs bits to make the extra bits of source to be deleted.

DDD = ?

(b) mask |= write_mask[write_lhs + bitsize]

Quiz 4

CCC = ?

​​​​(a) strlen(str) + 1
​​​​(b) strlen(str) * 2
​​​​(c) s->hash_size
​​​​(d) s->size
​​​​(e) strlen(s->cstr) + 1