2022q1 Quiz1 - HackMD

# 2022q1 Quiz1 contributed by Shawn Hisao <shawn5141> ## [測驗 1](https://hackmd.io/@sysprog/linux2022-quiz1#%E6%B8%AC%E9%A9%97-1) ```cpp= void map_add(map_t *map, int key, void *data) { struct hash_key *kn = find_key(map, key); if (kn) return; kn = malloc(sizeof(struct hash_key)); kn->key = key, kn->data = data; struct hlist_head *h = &map->ht[hash(key, map->bits)]; struct hlist_node *n = &kn->node, *first = h->first; AAA; if (first) first->pprev = &n->next; h->first = n; BBB; } ``` - kn is newly allocated memory (new hash_key) which need to insert into hlist list. - h is hlist head retrived from ht (hash table) using hash value. - n is kn's hlist_node. - first is first node head point to. According to line 13 and line 14, we saw that it make `first->pprev` point to this newly allocated hlist_node (n). Which means that we want to insert this node between head and first if first ever exist. To do that, we need to think about how to handle pprev and next pointer of newly allocated node. ### AAA = ? (c) n->next = first Having AAA equal to `n->next = first` will handle `n->next` properly no matter whether there are first exist or not. ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] list_head[label = "<m>list_head | <n>first"] node_1[label = "<m>new hlist_node | {pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node_1 | {pprev | <n>next}", group = list]; node_3[label = "<m>hlist_node_2 | {pprev | <n>next}", group = list]; NULL[shape = plaintext, label = "NULL", group = list] {rank = "min" list_head} list_head -> node_1 -> node_2 -> node_3[ weight = 10, style = invis ] list_head:n -> node_1:m; node_1:p -> list_head:n; node_1:n -> node_2:m[color="red"]; node_2:p -> node_1:n; node_2:n -> node_3:m; node_3:p -> node_2:n; node_3:n -> NULL; } ``` ### BBB = ? (a) n->pprev = &h->first After handling AAA and let `h->first` point to `n` in line 15, we need to handle `n->pprev`. So making `n->prev` point to `&h->first` ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] list_head[label = "<m>list_head | <n>first"] node_1[label = "<m>new hlist_node | {pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node_1 | {pprev | <n>next}", group = list]; node_3[label = "<m>hlist_node_2 | {pprev | <n>next}", group = list]; NULL[shape = plaintext, label = "NULL", group = list] {rank = "min" list_head} list_head -> node_1 -> node_2 -> node_3[ weight = 10, style = invis ] list_head:n -> node_1:m; node_1:p -> list_head:n[color="red"]; node_1:n -> node_2:m; node_2:p -> node_1:n; node_2:n -> node_3:m; node_3:p -> node_2:n; node_3:n -> NULL; } ``` ### 1. 解釋上述程式碼運作原理 - 使用中文註釋來解釋 ```cpp= #include <stddef.h> #include <stdlib.h> // hash table 的 node 和 head 的structure。詳細請見上圖 struct hlist_node { struct hlist_node *next, **pprev; }; struct hlist_head { struct hlist_node *first; }; // hash map 本身 typedef struct { int bits; struct hlist_head *ht; } map_t; #define MAP_HASH_SIZE(bits) (1 << bits) map_t *map_init(int bits) { map_t *map = malloc(sizeof(map_t)); if (!map) return NULL; map->bits = bits; // malloc size for hlist_head table map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits)); if (map->ht) { //如果allocate成功，就intialize first pointer for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) (map->ht)[i].first = NULL; } else { free(map); map = NULL; } return map; } struct hash_key { int key; void *data; struct hlist_node node; }; #define container_of(ptr, type, member) \ ({ \ void *__mptr = (void *) (ptr); \ ((type *) (__mptr - offsetof(type, member))); \ }) #define GOLDEN_RATIO_32 0x61C88647 static inline unsigned int hash(unsigned int val, unsigned int bits) { /* High bits are more random, so use them. */ return (val * GOLDEN_RATIO_32) >> (32 - bits); } static struct hash_key *find_key(map_t *map, int key) { //找出key hash之後的head struct hlist_head *head = &(map->ht)[hash(key, map->bits)]; // Iterate 一遍 linked list，然後用container_of 找出hash_key的start pointer， for (struct hlist_node *p = head->first; p; p = p->next) { struct hash_key *kn = container_of(p, struct hash_key, node); // 如果iterated node的key等於要找的key就回傳 if (kn->key == key) return kn; } return NULL; } void *map_get(map_t *map, int key) { struct hash_key *kn = find_key(map, key); // 如果有找到node的話就回傳data return kn ? kn->data : NULL; } void map_add(map_t *map, int key, void *data) { struct hash_key *kn = find_key(map, key); // 如果有找到node的話就直接return if (kn) return; kn = malloc(sizeof(struct hash_key)); kn->key = key, kn->data = data; struct hlist_head *h = &map->ht[hash(key, map->bits)]; struct hlist_node *n = &kn->node, *first = h->first; AAA; if (first) first->pprev = &n->next; h->first = n; BBB; } void map_deinit(map_t *map) { if (!map) return; // Iterate through table 中的每一個head for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) { struct hlist_head *head = &map->ht[i]; // 從head開始iterate through linked list for (struct hlist_node *p = head->first; p;) { struct hash_key *kn = container_of(p, struct hash_key, node); struct hlist_node *n = p; p = p->next; if (!n->pprev) /* unhashed */ goto bail; struct hlist_node *next = n->next, **pprev = n->pprev; *pprev = next; if (next) next->pprev = pprev; n->next = NULL, n->pprev = NULL; bail: free(kn->data); free(kn); } } free(map); } int *twoSum(int *nums, int numsSize, int target, int *returnSize) { map_t *map = map_init(10); *returnSize = 0; int *ret = malloc(sizeof(int) * 2); if (!ret) goto bail; for (int i = 0; i < numsSize; i++) { int *p = map_get(map, target - nums[i]); if (p) { /* found */ ret[0] = i, ret[1] = *p; *returnSize = 2; break; } p = malloc(sizeof(int)); *p = i; map_add(map, nums[i], p); } bail: map_deinit(map); return ret; } ``` map_deinit explanation - #102 if `!n->pprev`, go to bail，代表如果first is null的話就可以把自己(kn) free掉 - go to 怎麼運作可以參考[goto 和流程控制篇](https://hackmd.io/@sysprog/c-control-flow?type=view) ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] list_head[label = "<m>list_head | <n>first"] kn node_1[label = "<m>n | {pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node_1 | {pprev | <n>next}", group = list]; node_3[label = "<m>hlist_node_2 | {pprev | <n>next}", group = list]; NULL[shape = plaintext, label = "NULL", group = list] {rank = "min" list_head} list_head -> node_1 -> node_2 -> node_3[ weight = 10, style = invis ] kn:p->node_1 p->node_2 list_head:n -> node_1:m; node_1:p -> list_head:n[color="red"]; node_1:n -> node_2:m; node_2:p -> node_1:n; node_2:n -> node_3:m; node_3:p -> node_2:n; node_3:n -> NULL; } ``` - #105 *next 指向n->next ```cpp= struct hlist_node *next = n->next, **pprev = n->pprev; ``` 代表產生一個next pointer 和pointer to pointer to n->prev。 ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] list_head[label = "<m>list_head | <n>first"] node_1[label = "<m>n | {pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node1 | {pprev | <n>next}", group = list]; node_3[label = "<m>hlist_node_2 | {pprev | <n>next}", group = list]; NULL[shape = plaintext, label = "NULL", group = list] {rank = "min" list_head} list_head -> node_1 -> node_2 -> node_3[ weight = 10, style = invis ] _next[label = "next"] p->node_2 pprev[label = "pprev"] _pprev[label = "*pprev"] _pprev:p -> list_head:n[color="blue"] pprev:p -> _pprev:m list_head:n -> node_1:m; node_1:p -> list_head:n; _next:m ->node_2:m node_1:n -> node_2:m; node_2:p -> node_1:n; node_2:n -> node_3:m; node_3:p -> node_2:n; node_3:n -> NULL; } ``` - #106則是把next assign to *prev ```cpp= *pprev = next; ``` ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] list_head[label = "<m>list_head | <n>first"] node_1[label = "<m>n | {pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node1 | {pprev | <n>next}", group = list]; node_3[label = "<m>hlist_node_2 | {pprev | <n>next}", group = list]; NULL[shape = plaintext, label = "NULL", group = list] {rank = "min" list_head} list_head -> node_1 -> node_2 -> node_3[ weight = 10, style = invis ] _next[label = "*pprev|next"] pprev[label = "pprev"] pprev:p -> _next:m list_head:n -> node_1:m; node_1:p -> list_head:n; _next:m ->node_2:m node_1:n -> node_2:m; node_2:p -> node_1:n; node_2:n -> node_3:m; node_3:p -> node_2:n; node_3:n -> NULL; } ``` - #107-109 如果next存在，則把pprev assign 給next 的pprev。則把pprev assign 給next 的pprev。。然後n的pprev跟next都assign null ```cpp= if (next) next->pprev = pprev; n->next = NULL, n->pprev = NULL; ``` ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] list_head[label = "<m>list_head | <n>first"] node_1[label = "<m>n | {pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node1 | {pprev | <n>next}", group = list]; node_3[label = "<m>hlist_node_2 | {pprev | <n>next}", group = list]; NULL[shape = plaintext, label = "NULL", group = list] null[shape = plaintext, label = "NULL", group = list] {rank = "min" list_head} list_head -> node_1 -> node_2 -> node_3[ weight = 10, style = invis ] _next[label = "*pprev|next"] p->node_2 pprev[label = "pprev"] pprev:p -> _next:m list_head:n -> node_1:m; node_1:p -> null _next:m ->node_2:m node_1:n ->null node_2:p -> pprev:n; node_2:n -> node_3:m; node_3:p -> node_2:n; node_3:n -> NULL; } ``` ### 2.解釋 linuxhash table 的設計和實作手法，並留意到 tools/include/linux/hash.h 的 GOLDEN_RATIO_PRIME，探討其實作考量 #### [Golden ratio prime](https://www.johndcook.com/blog/2019/05/12/golden-ratio-primes/ ) A prime number p is a golden ratio prime if there exists an integer φ such that ![](https://i.imgur.com/SZhXV2N.png) and [hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) implimentation use different value for different word size machine (32bits or 64bits) ```cpp= #ifndef _LINUX_HASH_H #define _LINUX_HASH_H /* Fast hashing routine for ints, longs and pointers. (C) 2002 Nadia Yvette Chambers, IBM */ #include <asm/types.h> #include <linux/compiler.h> /* * The "GOLDEN_RATIO_PRIME" is used in ifs/btrfs/brtfs_inode.h and * fs/inode.c. It's not actually prime any more (the previous primes * were actively bad for hashing), but the name remains. */ #if BITS_PER_LONG == 32 #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_32 #define hash_long(val, bits) hash_32(val, bits) #elif BITS_PER_LONG == 64 #define hash_long(val, bits) hash_64(val, bits) #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_64 #else #error Wordsize not 32 or 64 #endif /* * This hash multiplies the input by a large odd number and takes the * high bits. Since multiplication propagates changes to the most * significant end only, it is essential that the high bits of the * product be used for the hash value. * * Chuck Lever verified the effectiveness of this technique: * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf * * Although a random odd number will do, it turns out that the golden * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice * properties. (See Knuth vol 3, section 6.4, exercise 9.) * * These are the negative, (1 - phi) = phi**2 = (3 - sqrt(5))/2, * which is very slightly easier to multiply by and makes no * difference to the hash distribution. */ #define GOLDEN_RATIO_32 0x61C88647 #define GOLDEN_RATIO_64 0x61C8864680B583EBull #ifdef CONFIG_HAVE_ARCH_HASH /* This header may use the GOLDEN_RATIO_xx constants */ #include <asm/hash.h> #endif /* * The _generic versions exist only so lib/test_hash.c can compare * the arch-optimized versions with the generic. * * Note that if you change these, any <asm/hash.h> that aren't updated * to match need to have their HAVE_ARCH_* define values updated so the * self-test will not false-positive. */ #ifndef HAVE_ARCH__HASH_32 #define __hash_32 __hash_32_generic #endif static inline u32 __hash_32_generic(u32 val) { return val * GOLDEN_RATIO_32; } static inline u32 hash_32(u32 val, unsigned int bits) { /* High bits are more random, so use them. */ return __hash_32(val) >> (32 - bits); } #ifndef HAVE_ARCH_HASH_64 #define hash_64 hash_64_generic #endif static __always_inline u32 hash_64_generic(u64 val, unsigned int bits) { #if BITS_PER_LONG == 64 /* 64x64-bit multiply is efficient on all 64-bit processors */ return val * GOLDEN_RATIO_64 >> (64 - bits); #else /* Hash 64 bits using only 32x32-bit multiply. */ return hash_32((u32)val ^ __hash_32(val >> 32), bits); #endif } static inline u32 hash_ptr(const void *ptr, unsigned int bits) { return hash_long((unsigned long)ptr, bits); } /* This really should be called fold32_ptr; it does no hashing to speak of. */ static inline u32 hash32_ptr(const void *ptr) { unsigned long val = (unsigned long)ptr; #if BITS_PER_LONG == 64 val ^= (val >> 32); #endif return (u32)val; } #endif /* _LINUX_HASH_H */ ``` #### Before diving into this code, let's review some hasing theory. There are 3-4 popular hasing theory. One of them is called multiplication hashing method. The steps are described as below ![](https://i.imgur.com/VFn01Mm.png) ![](https://i.imgur.com/gEiFNz5.png) ![](https://i.imgur.com/Lt0HCWe.png) 得到的r0=17/32其實就是KA的小數部分(fractional part)，亦即r0=KA−⌊KA⌋，也就等於圖七(a)中的「f」。 ![](https://i.imgur.com/SDfhxiV.png) ![](https://i.imgur.com/C5FiR9U.png) 三者相加得到的，因為參與的「部位」變多了，那麼隨機性也就增加了，如此h(Key)便能得到較為隨機的結果。 ![](https://i.imgur.com/51bnyvF.png) - From above discussion, we know that hashing theory first of all let the value times some constant. - Back to our hash.h code above, hash_32 and hash_long are two functions used in hash_min. sizeof(val) will reflect the word of variable. If it is smaller than 4 byte, then apply hash_32 otherwise use hash_long ```cpp= /* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */ #define hash_min(val, bits) sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits) ``` #### How does hash_32 been implement? - It would call __hash_32 which will time val with GOLDEN_RATIO_32 so return value will overflow in 32bits kernel. Then having `>> (32-bits)` will left shift the value till only bits long digit remains. ```cpp= static inline u32 __hash_32_generic(u32 val) { return val * GOLDEN_RATIO_32; } static inline u32 hash_32(u32 val, unsigned int bits) { /* High bits are more random, so use them. */ return __hash_32(val) >> (32 - bits); } ``` #### How does hash_64 been implement? - BIT_PER_LONG == 64 means it's long occupied 8 byte, which means it's 64 bit machine. But something I do not understand is below snippest for `hash_64_generic`. Can hash_64 be called in 32 bits kernel machine? If it could not, then having second part of 32x32-bit multiply does not make sense to me. ```cpp= #ifndef HAVE_ARCH_HASH_64 #define hash_64 hash_64_generic #endif static __always_inline u32 hash_64_generic(u64 val, unsigned int bits) { #if BITS_PER_LONG == 64 /* 64x64-bit multiply is efficient on all 64-bit processors */ return val * GOLDEN_RATIO_64 >> (64 - bits); #else /* Hash 64 bits using only 32x32-bit multiply. */ return hash_32((u32)val ^ __hash_32(val >> 32), bits); #endif } ``` ## [測驗 2](https://hackmd.io/@sysprog/linux2022-quiz1#%E6%B8%AC%E9%A9%97-2) ### COND1 head->next && head->val == head->next->val ### COND2 head->next && head->val == head->next->val ### Rewrite w/o recursive ```cpp= #include <stddef.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode *deleteDuplicates(struct ListNode *head) { struct ListNode result; struct ListNode *prev = &result, *out = &result, *tmp; result.next = head; while (head) { if (head->next != NULL && head->val == head->next->val) { while (head->next != NULL && head->val == head->next->val) { tmp = head; head = head->next; free(tmp); } prev->next = head->next; } else prev = prev->next; head = head->next; } return out->next; } ``` ## [測驗三](https://hackmd.io/@sysprog/linux2022-quiz1#%E6%B8%AC%E9%A9%97-3) ### 1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作 ```cpp= #include <stdio.h> #include <stdlib.h> #include "list.h" typedef struct { int capacity, count; struct list_head dhead, hheads[]; } LRUCache; typedef struct { int key, value; struct list_head hlink, dlink; } LRUNode; LRUCache *lRUCacheCreate(int capacity) { // 用malloc 產生數量是capacity大的LRU cache LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head)); obj->count = 0; obj->capacity = capacity; INIT_LIST_HEAD(&obj->dhead); // Initilize 在obj中的每個hheads for (int i = 0; i < capacity; i++) INIT_LIST_HEAD(&obj->hheads[i]); return obj; } void lRUCacheFree(LRUCache *obj) { LRUNode *lru, *n; list_for_each_safe (lru, n, &obj->dhead, dlink) { list_del(&lru->dlink); free(lru); } free(obj); } int lRUCacheGet(LRUCache *obj, int key) { LRUNode *lru; int hash = key % obj->capacity; list_for_each (lru, &obj->hheads[hash], hlink) { //就把它放到最前面，並且更新他的值 if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); return lru->value; } } return -1; } void lRUCachePut(LRUCache *obj, int key, int value) { LRUNode *lru; int hash = key % obj->capacity; // Iterate through hlink list_for_each (lru, &obj->hheads[hash], hlink) { // 如果lru node 其中有key等於要放進來的key就把它放到最前面，並且更新他的值 if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); lru->value = value; return; } } if (obj->count == obj->capacity) { // 把最後一個拿出來刪掉 lru = list_last_entry(&obj->dhead, LRUNode, dlink); list_del(&lru->dlink); list_del(&lru->hlink); } else { //不夠的話，就產生新的node lru = malloc(sizeof(LRUNode)); obj->count++; } lru->key = key; list_add(&lru->dlink, &obj->dhead); list_add(&lru->hlink, &obj->hheads[hash]); lru->value = value; } ``` ### 2. 在 Linux 核心找出 LRU 相關程式碼並探討 [lru_cache.h in linux](https://github.com/torvalds/linux/blob/9b76d71fa8be8c52dbc855ab516754f0c93e2980/include/linux/lru_cache.h) - lc_element ```cpp= /* this defines an element in a tracked set * .colision is for hash table lookup. * When we process a new IO request, we know its sector, thus can deduce the * region number (label) easily. To do the label -> object lookup without a * full list walk, we use a simple hash table. * * .list is on one of three lists: * in_use: currently in use (refcnt > 0, lc_number != LC_FREE) * lru: unused but ready to be reused or recycled * (lc_refcnt == 0, lc_number != LC_FREE), * free: unused but ready to be recycled * (lc_refcnt == 0, lc_number == LC_FREE), * * an element is said to be "in the active set", * if either on "in_use" or "lru", i.e. lc_number != LC_FREE. * * DRBD currently (May 2009) only uses 61 elements on the resync lru_cache * (total memory usage 2 pages), and up to 3833 elements on the act_log * lru_cache, totalling ~215 kB for 64bit architecture, ~53 pages. * * We usually do not actually free these objects again, but only "recycle" * them, as the change "index: -old_label, +LC_FREE" would need a transaction * as well. Which also means that using a kmem_cache to allocate the objects * from wastes some resources. * But it avoids high order page allocations in kmalloc. */ struct lc_element { struct hlist_node colision; struct list_head list; /* LRU list or free list */ unsigned refcnt; /* back "pointer" into lc_cache->element[index], * for paranoia, and for "lc_element_to_index" */ unsigned lc_index; /* if we want to track a larger set of objects, * it needs to become an architecture independent u64 */ unsigned lc_number; /* special label when on free list */ #define LC_FREE (~0U) /* for pending changes */ unsigned lc_new_number; }; ``` - #38 #define LC_FREE (~0U) means bitwise not; all bits in the integer will be flipped, which in this case produces a number where all bits are 1. ``` (Assuming a 32 bit uint) 0u 00000000 00000000 00000000 00000000 ~0u 11111111 11111111 11111111 11111111 3 00000000 00000000 00000000 00000011 ~3 11111111 11111111 11111111 11111100 ``` - lru_cache struct - there are four list_head. - use ([kmem_cache](https://github.com/torvalds/linux/blob/e3a8b6a1e70c37702054ae3c7c07ed828435d8ee/mm/slab.h#:~:text=%23ifdef%20CONFIG_SLOB-,/*,%7D%3B,-%23endif%20/*%20CONFIG_SLOB%20*/)). It's a slab cache. More about [Slab Allocator](https://hammertux.github.io/slab-allocator). ```cpp= struct lru_cache { /* the least recently used item is kept at lru->prev */ struct list_head lru; struct list_head free; struct list_head in_use; struct list_head to_be_changed; /* the pre-created kmem cache to allocate the objects from */ struct kmem_cache *lc_cache; /* size of tracked objects, used to memset(,0,) them in lc_reset */ size_t element_size; /* offset of struct lc_element member in the tracked object */ size_t element_off; /* number of elements (indices) */ unsigned int nr_elements; /* Arbitrary limit on maximum tracked objects. Practical limit is much * lower due to allocation failures, probably. For typical use cases, * nr_elements should be a few thousand at most. * This also limits the maximum value of lc_element.lc_index, allowing the * 8 high bits of .lc_index to be overloaded with flags in the future. */ #define LC_MAX_ACTIVE (1<<24) /* allow to accumulate a few (index:label) changes, * but no more than max_pending_changes */ unsigned int max_pending_changes; /* number of elements currently on to_be_changed list */ unsigned int pending_changes; /* statistics */ unsigned used; /* number of elements currently on in_use list */ unsigned long hits, misses, starving, locked, changed; /* see below: flag-bits for lru_cache */ unsigned long flags; void *lc_private; const char *name; /* nr_elements there */ struct hlist_head *lc_slot; struct lc_element **lc_element; }; ``` - flag_bit - do right shift for enum number ```cpp= /* flag-bits for lru_cache */ enum { /* debugging aid, to catch concurrent access early. * user needs to guarantee exclusive access by proper locking! */ __LC_PARANOIA, /* annotate that the set is "dirty", possibly accumulating further * changes, until a transaction is finally triggered */ __LC_DIRTY, /* Locked, no further changes allowed. * Also used to serialize changing transactions. */ __LC_LOCKED, /* if we need to change the set, but currently there is no free nor * unused element available, we are "starving", and must not give out * further references, to guarantee that eventually some refcnt will * drop to zero and we will be able to make progress again, changing * the set, writing the transaction. * if the statistics say we are frequently starving, * nr_elements is too small. */ __LC_STARVING, }; #define LC_PARANOIA (1<<__LC_PARANOIA) #define LC_DIRTY (1<<__LC_DIRTY) #define LC_LOCKED (1<<__LC_LOCKED) #define LC_STARVING (1<<__LC_STARVING) ``` - [lc_create](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/lib/lru_cache.c#L88) - prepares to track objects in an active set. Returns a pointer to a newly initialized struct lru_cache on success, or NULL on (allocation) failure. * @name: descriptive name only used in lc_seq_printf_stats and lc_seq_dump_details * @cache: cache root pointer * @max_pending_changes: maximum changes to accumulate until a transaction is required * @e_count: number of elements allowed to be active simultaneously * @e_size: size of the tracked objects * @e_off: offset to the &struct lc_element member in a tracked object ```cpp= extern struct lru_cache *lc_create(const char *name, struct kmem_cache *cache, unsigned max_pending_changes, unsigned e_count, size_t e_size, size_t e_off); ``` [lru_cache.c in linux](https://github.com/torvalds/linux/blob/master/lib/lru_cache.c) ## [測驗 4](https://hackmd.io/@sysprog/linux2022-quiz1#%E6%B8%AC%E9%A9%97-4) ```cpp= #include <stdio.h> #include <stdlib.h> #include "list.h" struct seq_node { int num; struct list_head link; }; static struct seq_node *find(int num, int size, struct list_head *heads) { struct seq_node *node; int hash = num < 0 ? -num % size : num % size; list_for_each_entry (node, &heads[hash], link) { if (node->num == num) return node; } return NULL; } int longestConsecutive(int *nums, int n_size) { int hash, length = 0; struct seq_node *node; // Allocate n_size of list_head array struct list_head *heads = malloc(n_size * sizeof(*heads)); // Initialize newly created head_list to piont to themselves for (int i = 0; i < n_size; i++) INIT_LIST_HEAD(&heads[i]); for (int i = 0; i < n_size; i++) { // Iterate through nums array and if not find in list_head array, add it to this list_head list in hashmap if (!find(nums[i], n_size, heads)) { hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size; node = malloc(sizeof(*node)); node->num = nums[i]; list_add(&node->link, &heads[hash]); } } for (int i = 0; i < n_size; i++) { int len = 0; int num; // Iterate through nums array and find out the head from hashmap node = find(nums[i], n_size, heads); while (node) { len++; num = node->num; list_del(&node->link); int left = num, right = num; // Find if the node->value are decremental by one in hashmap // If found, continue while ((node = find(--left, n_size, heads))) { len++; list_del(&node->link); } // Find if the node->value are incremental by one in hashmap // If found, continue while ((node = find(++right, n_size, heads))) { len++; list_del(&node->link); } // Get maximum of length length = len > length ? len : length; } } return length; } int main() { int arr[5] = {0,2,3,4,7}; int len = 5; printf("Expected to see: %d \nLongest Consecutive length %d", 3,longestConsecutive(arr, 5)); } ``` - 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作 - Refers to above comments - 嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼 ### Refs - [Hash Table：Intro(簡介)](http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.