内核数据结构

链表和红黑树

Linux 内核源码中，常用的数据结构为链表和红黑树。如链表主要解决元素可以动态创建并删除和插入，每个元素离散存放不需要占据连续的内存

链表在Linux 内核数据结构如下:

struct list_head {
    struct list_head *next, *prev;
};
struct hlist_head{
    struct hlist_node *first;
}

链表静态和动态初始化操作：

#define LIST_HEAD_INIT(name) { &(name),&(name)}
#define LIST_HEAD(name) \
    struct list_head name  = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    WRITE_ONCE(list->next,list);
    list->prev = list;
}

添加节点到链表，内核直接提供API接口：

static inline void list_add(struct list_head *new,struct list_head *head)
{
    __list_add(new,head,head->next);
}

遍历节点内核提供API接口：

#define list_for_each(pos,head)\
    for (pos = (head)->next; pos != (head); pos = pos->next)

Linux 内核源码中的红黑树主要应用在内存管理以及进程调度，将排序的元素组织到树，也正式因为红黑树具有特色（搜索，删除，插入操作都可以在O(logN)时间完成，其中N为树种的元素个数）。

Red Black Tree具备二叉树特性：

结点是红色或黑色
根结点是黑色
所有叶子都是黑色（叶子是NULL节点）
每个红色结点的两个子结点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色结点）
从任意结点到其每个叶子的所有路径都包含相同数目的黑色结点。

Linux 内核红黑树数据结构如下：

    struct rb_root {
        struct rb_node *rb_node;
    };

    struct rb_node {
        unsigned long __rb_parent_color;
        struct rb_node *rb_right;
        struct rb_node *rb_left;
    } __attribute__((aligned(sizeof(long))));

    struct rb_root {
        struct rb_node *rb_node;
    }

进程管理4大常用API详解

find_get_pid(...)函数功能：

根据进程编号获取对应的进程描述符，具体的Linux内核源码对应的函数设计如下: struct pid *find_get_pid(pid_t nr) // nr进程对应的进程编号 { struct pid *pid; rcu_read_lock(); //rcu 读锁 pid = get_pid(find_vpid(nr)); //调用get_pid 增加引用计数操作 rcu_read_unlock();// rcu 读解锁 return pid; } EXPORT_SYMBOL_GPL(find_get_pid);

pid_task(...)函数功能

获取任务的任务描述符数据信息，具体的Linux内核源码对应的函数设计如下：

struct task_struct *pid_task(struct pid *pid, enum pid_type type)
{
       struct task_struct *result = NULL;
       if(pid) {
        struct hlist_node *first;
        first = rcu_dereference_check(hlist_first_rcu(&pid->tasks[type]),
                                lockdep_tasklist_lock_is_held());
        if(first)
            result = hlist_entry(first,struct task_struct , pid_links[(type)]);
        }
        return result;
}
EXPORT_SYMBOL(pid_task);

pid_nr(...) 函数功能

获取进程的全局进程号，具体linux内核源码对应函数设计如下：

static inline pid_t pid_nr(struct pid *pid)
{
    pid_t nr = 0;
    if (pid)
        nr = pid->numbers[0].nr;
    return nr;
}
EXPORT_SYMBOL(pid_t);

__task_pid_nr_ns(...)函数功能：

获取进程编号，具体linux内核源码对应函数设计：

pid_t __task_pid_nr_ns(struct task_struct *task,enum pid_type type,struct pid_namespace *ps)
{
    pid_t nr = 0;
    rcu_read_lock();
    if(!ns)
        ns = task_active_pid_ns(current);
    if(likely(pid_alive(task)))
        nr = pid_nr_ns(rcu_dereference(*task_pid_ptr(task,type)),ns);
    rcu_read_unlock();
    return nr;
}
EXPORT_SYMBOL(__task_pid_nr_ns);

进程调度常用API函数 kthread_create_on_node(...)函数功能：指定存储节点创建新内核线程

struct task_struct *kthread_create_on_node(int (*threadfn)(void *data),void *data,int node,const char namefmt[],...)
{
    struct task_struct *task;
    va_list args;
    va_start(args,namefmt);
    task = __kthread_create_on_node(threadfn,data,node,namefmt,args);
    va_end(args);
    return task;
}
EXPORT_SYMBOL(kthread_create_on_node);

进程调度常用API函数：wake_up_process(...)函数功能：使唤醒处于睡眠状态的进程状态转为RUNNING 状态，让CPU重新调度处理

int wake_up_process(struct task_struct *p)
{
    return try_to_wake_up(p,TASK_NORMAL,0);
}
EXPORT_SYMBOL(wake_up_process) //返回 0 （相当于当前进程处于running 状态或唤醒进程已经失败），1 （相当于当前进程不处于running 状态，唤醒进程已经成功）

进程调度常用API 函数：task_nice(...)函数功能：专门用于获取进程对应nice 值。

static inline int task_nice(const struct task_struct *p)
{
    return PRIO_TO_NICE((p)->static_prio);
}

跟静态优先级关系nice=static_prio-120 调用此函数，返回整型值（int)代表当前进程的nice 值，其取值范围是-20--19，nice 的值越小代表优先级越大。

进程调度常用API函数：set_user_nice(...)函数功能：专门用于改变进程的静态优先级。

void set_user_nice(struct task_struct *p, long nice)
{
    bool queued, running;
    int old_prio, delta;
    struct rq_flags rf;
    struct rq *rq;
#如果当前task的nice值已经等于要设置的nice值，就直接退出
#从这里可以看出nice值的范围在-20~19 之间
    if (task_nice(p) == nice || nice < MIN_NICE || nice > MAX_NICE)
        return;
    /*
     * We have to be careful, if called from sys_setpriority(),
     * the task might be in the middle of scheduling on another CPU.
     */
    rq = task_rq_lock(p, &rf);
    update_rq_clock(rq);

    /*
     * The RT priorities are set via sched_setscheduler(), but we still
     * allow the 'normal' nice value to be set - but as expected
     * it wont have any effect on scheduling until the task is
     * SCHED_DEADLINE, SCHED_FIFO or SCHED_RR:
     */
#如果当前是实时进程，这里也可以看出实时进程的的调度策略可以分为deadline/fifo/rr.
#针对实时进程设置nice值其实是没有作用的，但是这里还是将nice值转成优先级后设置到p->static_prio 
    if (task_has_dl_policy(p) || task_has_rt_policy(p)) {
        p->static_prio = NICE_TO_PRIO(nice);
        goto out_unlock;
    }
    queued = task_on_rq_queued(p);
    running = task_current(rq, p);
    if (queued)
        dequeue_task(rq, p, DEQUEUE_SAVE | DEQUEUE_NOCLOCK);
    if (running)
        put_prev_task(rq, p);
#将nice值转成优先级设置到static_prio 中，#define NICE_TO_PRIO(nice) ((nice) + DEFAULT_PRIO)
#这里的DEFAULT_PRIO 值经过计算是120.
#从这里也可以看出优先级转nice值应该是减去DEFAULT_PRIO #define PRIO_TO_NICE(prio)  ((prio) - DEFAULT_PRIO)

    p->static_prio = NICE_TO_PRIO(nice);
    set_load_weight(p);
    old_prio = p->prio;
    p->prio = effective_prio(p);
    delta = p->prio - old_prio;
#如果要设置的nice的task在queue中
    if (queued) {
        enqueue_task(rq, p, ENQUEUE_RESTORE | ENQUEUE_NOCLOCK);
        /*
         * If the task increased its priority or is running and
         * lowered its priority, then reschedule its CPU:
         */
#如果增大优先级且task正在运行或者减小优先级的话，则重新调度rq。
        if (delta < 0 || (delta > 0 && task_running(rq, p)))
            resched_curr(rq);
    }
#如果要设置nice值的task正在运行，由于我们这里改变了p的优先级，则重新指定task的rq.
    if (running)
        set_curr_task(rq, p);
out_unlock:
    task_rq_unlock(rq, p, &rf);
}

进程调度常用API函数：complete_all(...)函数功能：主要用于唤醒等待队列中所有睡眠进程等功能

void complete_all(struct completion *x)
{
    unsigned long flags;
    spin_lock_irqsave(&x->wait.lock,flags);
    x->done = UINT_MAX;
    __wake_up_locked(&x->wait.TASK_NORMAL,0);
    spin_unlock_irqrestore(&x->wait.lock,flags);
}
EXPORT_SYMBOL(complete_all);

该函数实现唤醒等待队列中进程通过函数__wake_up_locked(),通过参数确定唤醒进程状态：

TASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLE。唤醒进程不是同步操作。

进程调用API函数：__wake_up_sync_key(...)功能为：专用与唤醒等待队列中处于特定状态的进程。

void __wake_up_sync(wait_queue_head_t *q,unsigned int mode,int nr_exclusive)
{
    __wake_up_sync_key(q,mode,nr_exclusive,NULL);
}
EXPORT_SYMBOL_GPL(__wake_up_sync);

此函数唤醒进程不会改变进程之前所在cpu,不会引起额外的抢占操作，并且可以同步唤醒进程。

HrQing

基于Django的网站，记录IT 开发，包括c++,java,python, 接受半导体测试服务，包括力学测试，表面分析测试，热学测试，联系方式：[email protected]。

内核数据结构

内核数据结构

链表和红黑树

链表在Linux 内核数据结构如下:

链表静态和动态初始化操作：

添加节点到链表，内核直接提供API接口：

遍历节点内核提供API接口：

Linux 内核源码中的红黑树主要应用在内存管理以及进程调度，将排序的元素组织到树，也正式因为红黑树具有特色（搜索，删除，插入操作都可以在O(logN)时间完成，其中N为树种的元素个数）。

进程管理4大常用API详解

find_get_pid(...)函数功能：

pid_task(...)函数功能

pid_nr(...) 函数功能

__task_pid_nr_ns(...)函数功能：

进程调度常用API函数 kthread_create_on_node(...)函数功能：指定存储节点创建新内核线程

进程调度常用API函数：wake_up_process(...)函数功能：使唤醒处于睡眠状态的进程状态转为RUNNING 状态，让CPU重新调度处理

进程调度常用API 函数：task_nice(...)函数功能：专门用于获取进程对应nice 值。

进程调度常用API函数：set_user_nice(...)函数功能：专门用于改变进程的静态优先级。

进程调度常用API函数：complete_all(...)函数功能：主要用于唤醒等待队列中所有睡眠进程等功能

进程调用API函数：__wake_up_sync_key(...)功能为：专用与唤醒等待队列中处于特定状态的进程。

您还没有登录，请您登录后发表评论。