#
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
int *reval = (int *)malloc(sizeof(int) * 2);//这一个是返回的数组
*returnSize = 2;// 这是leetcode 的一个特色，要告诉调用者分配的数组的大小，看注释要求
int left = 0, right = numbersSize - 1;
for(;;){
if(numbers[left] + numbers[right] > target){
right--;
} else if(numbers[left] + numbers[right] < target){
left++;
}else
{
reval[0] = left + 1;
reval[1] = right + 1;
return reval;
}
}
}
convert-sorted-array-to-binary-search-tree （108）主要的一个思想就是二叉搜索树的中序遍历就是有序数组，或者说有序数组的中间位置就是BST的根节点。
path-sum【112】 给一个数字，让你计算下从root到levies的和是否等于这个数。递归的想法；
bool hasPathSum(struct TreeNode* root, int sum) {
if (!root)
return false;
if (!root->left && !root->right)
return sum == root->val;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
给定两棵树的根节点，判断这两棵树是否为相同的树。
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL)
return true; // 根节点为空
if((p == NULL && q != NULL) || (p != NULL && q == NULL))
return false;
else if (p->val != q->val)
return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
全篇没有使用 p->val == q->val 的使用条件，难以理解！ 好，下面的代码使用了这个条件，而且速度比这个快太多了。
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL)
return true; // 首先判断两个根节点(对于左右子树而言也对)
if (!p || !q)
return false; // 有了前面的基础，有其中一个根节点为空，则f
if (p->val == q->val) // 也许这一步是关键，不满足直接false
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
else
return false;
}
};
input: [1,2,3,null,5] output: [“1->2->5”,”1->3”]
leetcode的tree这块测试，尤其注意点，输入的可以不用管，就算考虑的可以把”[“去掉。尤其注意output的格式:
不用管”[”,”]”这个符号的。
// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Paths.
class Solution {
public:
void binaryTreePaths(vector<string>& result, TreeNode *root, string t){
if (!root->left && !root->right) {
result.push_back(t);
return;
}
if (root->left) binaryTreePaths(result, root->left, t + "->" + to_string(root->left->val));
if (root->right) binaryTreePaths(result, root->right, t + "->" + to_string(root->right->val));
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
if (root)
binaryTreePaths(result, root, to_string(root->val));
return result;
}
};
这里有一个tip值得关注，就是 to_string,这个std::to_string可以将任何类型的参数转化为string类型。在c++中，string可以使用”+”号，这无疑对于解决一些zifu相关的算法题目提供了便利。
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res; // 返回值
stack<TreeNode*> s; // 节点的栈
stack<string> path_stack; // 路径的栈
if(!root) return res;
s.push(root);
path_stack.push(to_string(root->val)); // Initiliza both stack to run it.
while(!s.empty()){ // this is a model for stack ops
TreeNode* cur_node = s.top(); s.pop();
string tmp_path = path_stack.top(); path_stack.pop();
if (!cur_node->left && !cur_node->right){
res.push_back(tmp_path); // if the cur_node is left node, then push stack to res
continue; // key: if true, the next program will not run
}
if (cur_node->left){
s.push(cur_node->left);
path_stack.push(tmp_path + "->" + to_string(cur_node->left->val));
}
if (cur_node->right){
s.push(cur_node->right);
path_stack.push(tmp_path + "->" + to_string(cur_node->right->val));
}
}
return res;
}
可以说，上面是我第一次接触两个栈的使用，有意思啊。
Ctrl+Shift+E 垂直分割窗口
Ctrl+Shift+O 水平分割窗口
F11 全屏
Ctrl+Shift+C 复制
Ctrl+Shift+V 粘贴
Ctrl+Shift+N 或者 Ctrl+Tab 在分割的各窗口之间切换，或者alt加方向键
Ctrl+Shift+X 将分割的某一个窗口放大至全屏使用
Ctrl+Shift+Z 从放大至全屏的某一窗口回到多窗格界面
Ctrl+Shift+W 关闭当前窗口
创建的时候就很简单了，有
kthread_run();
// 或者
kthread_create();
其实呢，这块就是自己知道的太少，来看看我的低级错误。
19.c
int wait_event_interruptible(wait_queue_head_t q, CONDITION);
void wake_up_all(wait_queue_head_t *q);
The whole point of a scheduler is to avoid polling in cases like this. What happens is precisely described in what you quoted : The condition is only rechecked on wake_up, ie for example if a given task is waiting for data to be produced :
consumer check if data is available if not (ie condition false) it goes to sleep and is added to a wait queue retry when waked up
While on the producer side Once data is produced, set some flag, or add something to a list so that the condition evaluated by the consumer becomes true call wake_up or wake_up all on a waitqueue
Now , I suggest you try to use them, and come back with another question AND code you tried if it does not work the way you want.
这篇文章也是很好的here
kthread_run 这篇文章值得仔细阅读 kthread_run()负责内核线程的创建，参数包括入口函数threadfn，参数data，线程名称namefmt。可以看到线程的名字可以是类似sprintf方式组成的字符串。如果实际看到kthread.h文件，就会发现kthread_run实际是一个宏定义，它由kthread_create()和wake_up_process()两部分组成，这样的好处是用kthread_run()创建的线程可以直接运行，使用方便。
我的错误就是在使用kthread_run又运行了一个wake_up_process的语句。
#define kthread_run(threadfn, data, namefmt, ...) \
({ \
struct task_struct *__k \
= kthread_create(threadfn, data, namefmt, ## __VA_ARGS__); \
if (!IS_ERR(__k)) \
wake_up_process(__k); \
__k; \
})
kthread_should_stop()返回should_stop标志。它用于创建的线程检查结束标志，并决定是否退出。线程完全可以在完成自己的工作后主动结束，不需等待should_stop标志。
/**
* kthread_should_stop - should this kthread return now?
*
* When someone calls kthread_stop() on your kthread, it will be woken
* and this will return true. You should then return, and your return
* value will be passed through to kthread_stop().
ed_should_stop - should this kthread return now?
*
* When someone calls kthread_stop() on your kthread, it will be woken
* and this will return true. You should then return, and your return
* value will be passed through to kthread_stop().
*/
bool kthread_should_stop(void)
{
return test_bit(KTHREAD_SHOULD_STOP, &to_kthread(current)->flags);
}
EXPORT_SYMBOL(kthread_should_stop);
bool kthread_should_stop(void)
{
return test_bit(KTHREAD_SHOULD_STOP, &to_kthread(current)->flags);
}
EXPORT_SYMBOL(kthread_should_stop);
/**
* kthread_stop - stop a thread created by kthread_create().
* @k: thread created by kthread_create().
*
* Sets kthread_should_stop() for @k to return true, wakes it, and
* waits for it to exit. This can also be called after kthread_create()
* instead of calling wake_up_process(): the thread will exit without
* calling threadfn().
*
* If threadfn() may call do_exit() itself, the caller must ensure
* task_struct can't go away.
*
* Returns the result of threadfn(), or %-EINTR if wake_up_process()
* was never called.
*/
int kthread_stop(struct task_struct *k)
{
struct kthread *kthread;
int ret;
trace_sched_kthread_stop(k);
get_task_struct(k);
kthread = to_kthread(k);
set_bit(KTHREAD_SHOULD_STOP, &kthread->flags);
kthread_unpark(k);
wake_up_process(k); // 首先唤醒这个进程
wait_for_completion(&kthread->exited); // 等待完成
ret = k->exit_code; //期待这个进程退出
put_task_struct(k); // 更改状态
trace_sched_kthread_stop_ret(ret);
return ret;
}
由这个api stop由kthread_create()产生的kthread,这个是可以直接调用的.线程一旦启动起来后，会一直运行，除非该线程主动调用do_exit函数，或者其他的进程调用kthread_stop函数，结束线程的运行。
/**
* wait_event_interruptible - sleep until a condition gets true
* @wq_head: the waitqueue to wait on //首先把这个线程放入等待队列
* @condition: a C expression for the event to wait for //激活的满足条件
*
* The process is put to sleep (TASK_INTERRUPTIBLE) until the
* @condition evaluates to true or a signal is received.//这里这个信号是如何获取的呢?
* The @condition is checked each time the waitqueue @wq_head is woken up.
*
* wake_up() has to be called after changing any variable that could
* change the result of the wait condition.
*
* The function will return -ERESTARTSYS if it was interrupted by a
* signal and 0 if @condition evaluated to true.
*/
#define wait_event_interruptible(wq_head, condition) \
({ \
int __ret = 0; \
might_sleep(); \
if (!(condition)) \
__ret = __wait_event_interruptible(wq_head, condition); \
__ret; \
})
/*下面的宏在上面*/
#define __wait_event_interruptible(wq_head, condition) \
___wait_event(wq_head, condition, TASK_INTERRUPTIBLE, 0, 0, \
schedule())
wait_event_interruptible函数最终将当前队列中的进程设置为TASK_INTERRUPTIBLE状态，然后调用schedule()函数 这个函数会将TASK_INTERRUPTIBLE状态的进程从runqueue队列中删除，结果就是不会再被调度了，那么，如何被重新调度呢？ 当然使用wait_up.这里先猜测下，wake_up函数与上面的函数应该一致，只是应该换成TASK_RUNNING状态。
接下来就是揭晓答案的时刻。
#define wake_up(x) __wake_up(x, TASK_NORMAL, 1, NULL)
接着往下找:
/**
* __wake_up - wake up threads blocked on a waitqueue.
* @wq_head: the waitqueue
* @mode: which threads
* @nr_exclusive: how many wake-one or wake-many threads to wake up
* @key: is directly passed to the wakeup function
*
* If this function wakes up a task, it executes a full memory barrier before
* accessing the task state.
*/
void __wake_up(struct wait_queue_head *wq_head, unsigned int mode,
int nr_exclusive, void *key)
{
__wake_up_common_lock(wq_head, mode, nr_exclusive, 0, key);
}
EXPORT_SYMBOL(__wake_up);
/*
* Same as __wake_up but called with the spinlock in wait_queue_head_t held.
*/
void __wake_up_locked(struct wait_queue_head *wq_head, unsigned int mode, int nr)
{
__wake_up_common(wq_head, mode, nr, 0, NULL, NULL);
}
EXPORT_SYMBOL_GPL(__wake_up_locked);
/*
* The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
* wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
* number) then we wake all the non-exclusive tasks and one exclusive task.
*
* There are circumstances in which we can try to wake a task which has already
* started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
* zero in this (rare) case, and we handle it by continuing to scan the queue.
*/
static int __wake_up_common(struct wait_queue_head *wq_head, unsigned int mode,
int nr_exclusive, int wake_flags, void *key,
wait_queue_entry_t *bookmark)
{
wait_queue_entry_t *curr, *next;
int cnt = 0;
lockdep_assert_held(&wq_head->lock);
if (bookmark && (bookmark->flags & WQ_FLAG_BOOKMARK)) {
curr = list_next_entry(bookmark, entry);
list_del(&bookmark->entry);
bookmark->flags = 0;
} else
curr = list_first_entry(&wq_head->head, wait_queue_entry_t, entry);
if (&curr->entry == &wq_head->head)
return nr_exclusive;
list_for_each_entry_safe_from(curr, next, &wq_head->head, entry) {
unsigned flags = curr->flags;
int ret;
if (flags & WQ_FLAG_BOOKMARK)
continue;
ret = curr->func(curr, mode, wake_flags, key);
if (ret < 0)
break;
if (ret && (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
break;
if (bookmark && (++cnt > WAITQUEUE_WALK_BREAK_CNT) &&
(&next->entry != &wq_head->head)) {
bookmark->flags = WQ_FLAG_BOOKMARK;
list_add_tail(&bookmark->entry, &next->entry);
break;
}
}
return nr_exclusive;
}
具体的封装链为:
wake_up->__wake_up->__wake_up_locked -> __wake_up_common->
当然，最后一个函数有些复杂.
好一个TASK_NORMAL这究竟是个什么东西？
/*
* Task state bitmask. NOTE! These bits are also
* encoded in fs/proc/array.c: get_task_state().
*
* We have two separate sets of flags: task->state
* is about runnability, while task->exit_state are
* about the task exiting. Confusing, but this way
* modifying one set can't modify the other one by
* mistake.
*/
/* Used in tsk->state: */
#define TASK_RUNNING 0x0000
#define TASK_INTERRUPTIBLE 0x0001
#define TASK_UNINTERRUPTIBLE 0x0002
#define __TASK_STOPPED 0x0004
#define __TASK_TRACED 0x0008
/* Used in tsk->exit_state: */
#define EXIT_DEAD 0x0010
#define EXIT_ZOMBIE 0x0020
#define EXIT_TRACE (EXIT_ZOMBIE | EXIT_DEAD)
/* Used in tsk->state again: */
#define TASK_PARKED 0x0040
#define TASK_DEAD 0x0080
#define TASK_WAKEKILL 0x0100
#define TASK_WAKING 0x0200
#define TASK_NOLOAD 0x0400
#define TASK_NEW 0x0800
#define TASK_STATE_MAX 0x1000
/* Convenience macros for the sake of set_current_state: */
#define TASK_KILLABLE (TASK_WAKEKILL | TASK_UNINTERRUPTIBLE)
#define TASK_STOPPED (TASK_WAKEKILL | __TASK_STOPPED)
#define TASK_TRACED (TASK_WAKEKILL | __TASK_TRACED)
#define TASK_IDLE (TASK_UNINTERRUPTIBLE | TASK_NOLOAD)
/* Convenience macros for the sake of wake_up(): */
#define TASK_NORMAL (TASK_INTERRUPTIBLE | TASK_UNINTERRUPTIBLE)
/* get_task_state(): */
#define TASK_REPORT (TASK_RUNNING | TASK_INTERRUPTIBLE | \
TASK_UNINTERRUPTIBLE | __TASK_STOPPED | \
__TASK_TRACED | EXIT_DEAD | EXIT_ZOMBIE | \
TASK_PARKED)
重点是TASK_NORMAL这个宏可以唤醒可中断和不可中断的TASK
make C=2 CF=-D__CHECK_ENDIAN__
有关sparse发现的问题，我自己的patch在下面，但是，目前来说没有理解其中的原理 只能先记录下来，后面再总结。
在上面的补丁中，其中就是一个有关rcu的bug. 现在记录一个
li 其中的一个问题如何从KASAN的log中找到相关的代码线索？
嘿嘿，这是有关位操作的黑科技 资源：
1. 下面这段代码是有问题的， 命令：
sudo make C=2 M=drivers/net/
相关的代码：3241行fromcode
static inline u32 bond_eth_hash(struct sk_buff *skb)
{
struct ethhdr *ep, hdr_tmp;
ep = skb_header_pointer(skb, 0, sizeof(hdr_tmp), &hdr_tmp);
if (ep)
return ep->h_dest[5] ^ ep->h_source[5] ^ ep->h_proto;
return 0;
}
其中，ethhdr的定义在161
#if __UAPI_DEF_ETHHDR
struct ethhdr {
unsigned char h_dest[ETH_ALEN]; /* destination eth addr */
unsigned char h_source[ETH_ALEN]; /* source ether addr */
__be16 h_proto; /* packet type ID field */
} __attribute__((packed));
#endif
看出问题来了吗？
很简单，这是c语言的或者计算机世界中最基本的知识了，只是自己疏于整理(另一句话就是基础太差劲) 正好，自己在写这个短小的程序时碰到了，故借此机会先记录下内核中的一些基础知识。
在c语言中，u64的含义就是unsigned 64 bits,与此相似的就是，u32(unsigned 32 bits).目前为止，我使用最多的数据类型可能就是整型(int)、长整型(long int==>long long int)、单精度浮点型(float)、双精度浮点型(double).他们都有一个共同的特点就是–带符号。学过计算机组成原理的同学一定接触过有符号和无符号的区别，暂且不表，这里就是简简单单的列举一下u64的用法。unsigned 就是无符号的含义。
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main() {
unsigned long long int message;
scanf("%llx", &message); //==> 0x1234567890abcdef
printf("The size of message is %d bytes, %llx\n", sizeof(message), message);
return 0;
}
注意上面的message定义为long long且不带符号，scanf()的格式控制符是一个组合：ll对应long long，x对应十六进制。所以你在键入的时候，在数据的前面添加上0x。在我的机器上，long long int 是8 bytes,那么也就是8 * 8 = 64 bits数据长度。同时，一个字符的大小是4bits，所以message可以存储64/4=16个字符。在我的注释中，正好是16位十六进制数字，如果你多以为，则message就溢出了。
在我有限的c语言知识中，还没有碰到使用u64数据类型的好处，或者说必须使用的场景。好，下面就简单说一下他的一个用法。
考虑到一个由16进制组成的数据：0x1234567890abcdef或者0xe233f61cc9c7，那么，怎么才可以将这个16进制的数据存放到字符数组中呢？
答案就在下面：
len = sprintf(id, "%llx\n", task->id);
其中，task->id的数据类型是u64,id的数据类型由char id[18]定义，这样就可以了