来自 编程应用 2019-10-04 19:47 的文章
当前位置: 六合联盟网 > 编程应用 > 正文

Librdkafka的根基数据结构,Linux内核学习笔记

  • Librdkafka用纯C写成,小编在C API基础上作了C++的简易包装;
  • 提起C, 自然之中离不开大量的指针操作, 内部存款和储蓄器操作, 引用计数等等, 小编一一为大家作了落到实处;
  • 基本功数据结构里面也谈到了大多,比方 链表, 各类队列, 二叉树等等, 接下来大家会挨个介绍.

  Linux系统中,进度之间有一个明确的延续关系,全体进程都以 PID 为1的 init 进度的后生。内核在系统运行的末尾阶段运营 init 进度。该进程读取系统的起始化脚本(initscript)并施行其余的连锁程序,最终完毕系统运营的满贯经过。

Queue
  • 所在文书: src/queue.h和src/rdsysqueue.h
  • queue.h是个很古老的落到实处了, 作者这里用的是NetBsd里的落到实处, 还应该有其余不少版本, 达成都大致, 里面指针的运用真是值得我们好好学习;
  • 网络有关那么些的任课有大多, 大家这里只是轻易过一下用得最多的Tail queue;
  • 头指针定义 #define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,):
#define _TAILQ_HEAD(name, type, qual) struct name {  qual type *tqh_first; /* first element */  qual type *qual *tqh_last; /* addr of last next element */ }

三个因素:tqh_first: 指向队列的第一个成员;tqh_last: 存的是队列里的最终二个因素的 next指针的变量地址, 那些二级指针太有用了,大家前边会再讲到;

  • 队列的entry: #define TAILQ_ENTRY _TAILQ_ENTRY(struct type,) 实际是用起码侵入式的秘技贯彻了贰个左近于C++的模版的编写制定, 定义中的type正是队列里成分的类型, 能够是大肆struct类型, 那几个_TAILQ_ENTRY(type, qual)投身这些struct类型的定义里,是其的二个分子, 然后逐个要素通过这么些TAILQ_ENTRY分子相互串联起来, 松耦合在联合
#define _TAILQ_ENTRY(type, qual) struct {  qual type *tqe_next; /* next element */  qual type *qual *tqe_prev; /* address of previous next element */}#define TAILQ_ENTRY _TAILQ_ENTRY(struct type,)

八个因素:tqe_next: 指向队列的下贰个成员;tqe_prev: 存的是前一个元素的 next指针的变量地址, 那么些二级指针太有用了,大家前面会再讲到;

  • 获队列的末段三个因素#define TAILQ_LAST(head, headname):
(*(((struct headname *)->tqh_last))->tqh_last))

要了然这一个实在根本一点是上边定义的TAILQ_HEADTAILQ_ENTRY在结商谈内部存款和储蓄器布局上是一模二样同样的.->tqh_last)是终极一个成分的next指针的地点, 因为TAILQ_ENTRY以此定义是不曾类型名的,我们不能一贯cast成 TAILQ_ENTRY花色, 全体就不得不cast成(struct headname *), 所有((struct headname *)->tqh_last))相当于终极一个成分的地点,(((struct headname *)->tqh_last))->tqh_last)正是终极三个成分的tqe_prev值, 这个tqe_prev本着的是它前三个要素的next的地方, 解引用后自然就指向队列最终三个成分和煦了, 有一些绕~~~

  • 获得当前成分的前二个成分 #define TAILQ_PREV(elm, headname, field)
(*(((struct headname *)->field.tqe_prev))->tqh_last))

有了上三个取末了成分的阅历,这几个驾驭起来就轻易多啊, 这里就不讲啊~~~

  • 任何部分操作, 头插,尾插, 前插,后插, 遍历, 反向遍历, 删除都比较轻巧了, 首要也都是指针操作;

  系统中种种进度必有三个父进度,相应的,每一个进程也足以由零个要么多个子进度。具备同二个父进度的具有进度被称作兄弟。进度之间的关联寄放在经过描述符 task_struct 中。每个 task_struct 都蕴涵一个对准其父进程 task_struct 的指针 parent,还会有叁个被叫作 children 的子进程链表。

rd_list_t
  • 是两个append-only的轻量级数组链表, 帮助固定大小和按需自行增进两种方法且援救sort;
  • 所在文书: src/rdlist.h 和 src/rdlist.c
  • 定义:
typedef struct rd_list_s { int rl_size; // 目前list的容易 int rl_cnt; // 当前list里已放入的元素个数 void **rl_elems; // 存储元素的内存, 可以看成是一个void*类型的数组 void (*rl_free_cb) ; // 存储的元素的释放函数 int rl_flags; #define RD_LIST_F_ALLOCATED 0x1 /* The rd_list_t is allocated, * will be free on destroy() */ #define RD_LIST_F_SORTED 0x2 /* Set by sort(), cleared by any mutations. * When this flag is set bsearch() is used * by find(), otherwise a linear search. */ #define RD_LIST_F_FIXED_SIZE 0x4 /* Assert on grow */ #define RD_LIST_F_UNIQUE 0x8 /* Don't allow duplicates: * ONLY ENFORCED BY CALLER. */} rd_list_t;
  • 创建list: rd_list_t *rd_list_new (int initial_size, void
rd_list_t *rd_list_new (int initial_size, void   { rd_list_t *rl = malloc(sizeof; rd_list_init(rl, initial_size, free_cb); rl->rl_flags |= RD_LIST_F_ALLOCATED; return rl;}
  • 体量自增: void rd_list_grow (rd_list_t *rl, size_t size)重在是调用rd_realloc
void rd_list_grow (rd_list_t *rl, size_t size) { rd_assert(!(rl->rl_flags & RD_LIST_F_FIXED_SIZE)); // 不适用于固定大小类型的list rl->rl_size += size; if (unlikely(rl->rl_size == 0)) return; /* avoid zero allocations */ rl->rl_elems = rd_realloc(rl->rl_elems, sizeof(*rl->rl_elems) * rl->rl_size);}
  • 永远体量的list的创设: void rd_list_prealloc_elems (rd_list_t *rl, size_t elemsize, size_t size)实在连各个成分的轻重也是稳固的
oid rd_list_prealloc_elems (rd_list_t *rl, size_t elemsize, size_t size) { size_t allocsize; char *p; size_t i; rd_assert(!rl->rl_elems); /* Allocation layout: * void *ptrs[cnt]; * elems[elemsize][cnt]; */ allocsize = (sizeof * size) + (elemsize * size); //rl_elems数组本身的大小(元素类型是void*) + 所有元素的大小 rl->rl_elems = rd_malloc(allocsize); /* p points to first element's memory. */ p = &rl->rl_elems[size]; /* Pointer -> elem mapping */ for (i = 0 ; i < size ; i++, p += elemsize) rl->rl_elems[i] = p; //数组元素赋值 rl->rl_size = size; rl->rl_cnt = 0; rl->rl_flags |= RD_LIST_F_FIXED_SIZE; // 标识为固定大小的list}
  • 足够新成分 void *rd_list_add (rd_list_t *rl, void *elem):
void *rd_list_add (rd_list_t *rl, void *elem) { if (rl->rl_cnt == rl->rl_size) rd_list_grow(rl, rl->rl_size ? rl->rl_size * 2 : 16); //容量不够先自增 rl->rl_flags &= ~RD_LIST_F_SORTED; //新增后原有的排序失效 if  rl->rl_elems[rl->rl_cnt] = elem; return rl->rl_elems[rl->rl_cnt++]; //当前已有元素数 + 1}
  • 按索引移除成分:
static void rd_list_remove0 (rd_list_t *rl, int idx) { rd_assert(idx < rl->rl_cnt); if (idx + 1 < rl->rl_cnt) //如果idx指向的是最后一个元素,不用mm了, rl->rl_cnt--就好 memmove(&rl->rl_elems[idx], &rl->rl_elems[idx+1], sizeof(*rl->rl_elems) * (rl->rl_cnt - ; // 实际就是用memmove作内存移动 rl->rl_cnt--;}
  • 排序用的qsort快排
void rd_list_sort (rd_list_t *rl, int  (const void *, const void *)) { rd_list_cmp_curr = cmp; qsort(rl->rl_elems, rl->rl_cnt, sizeof(*rl->rl_elems), rd_list_cmp_trampoline); rl->rl_flags |= RD_LIST_F_SORTED;}
  • 查找:
void *rd_list_find (const rd_list_t *rl, const void *match, int  (const void *, const void *)) { int i; const void *elem; //如果排过序就用二分查找 if (rl->rl_flags & RD_LIST_F_SORTED) { void **r; rd_list_cmp_curr = cmp; r = bsearch(&match/*ptrptr to match elems*/, rl->rl_elems, rl->rl_cnt, sizeof(*rl->rl_elems), rd_list_cmp_trampoline); return r ? *r : NULL; } 没排过就编历, 是不是可以先qsort一下呢? RD_LIST_FOREACH(elem, rl, i) { if (!cmp(match, elem)) return elem; } return NULL;}

 

Librdkafka源码深入分析-Content Table

一、父进度的拜会方法

  对于当前经过,能够采纳上面代码访问其父进度,得到其进程描述符:

struct task_struct *my_parent = current -> parent;

   其中,current 是贰个宏,在 linux/asm-generic/current.h中有定义:

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef __ASM_GENERIC_CURRENT_H
#define __ASM_GENERIC_CURRENT_H

#include <linux/thread_info.h>

#define get_current() (current_thread_info()->task)
#define current get_current()

#endif /* __ASM_GENERIC_CURRENT_H */

  而 current_thread_info() 函数在 arch/arm/include/asm/thread_info.h 中有定义:

/*
 * how to get the thread information struct from C
 */
static inline struct thread_info *current_thread_info(void) __attribute_const__;

static inline struct thread_info *current_thread_info(void)
{
    return (struct thread_info *)
        (current_stack_pointer & ~(THREAD_SIZE - 1));        // 让SP堆栈指针与栈底对齐    
}    

   能够观看,current 实际上是指向当前进行进程的 task_struct 指针的。

 

二、子进程的探访方法

  能够运用以下方法访谈子进度:

struct task_struct *task;
struct list_head *list;

list_for_each(list,&current->children){
    task = list_entry(list,struct task_struct,sibling);      
}

  能够看见,这里运用的是链表相关的操作来访谈子进度。大家精晓, task_struct 是寄存在在两个双向循环链表 task_list(任务队列)中的,而三个task_struct 饱含了二个实际进度的保有音讯,由此,大家只要求找到子进度的 task_struct 即能够访谈子进度了,上边代码就是这么做的。那么,具体是如何找到子进程的长河描述符 task_struct的呢?下边临地方的代码举办详细深入分析:

  list_head: 在 linux/types.h 中定义

struct list_head{
    struct list_head *next,*prev;  
};

  显然,list_head 其实正是四个双向链表,而且平时的话,都以双向循环链表。

 

  list_for_each: 在linux/list.h 中定义

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

  那是一个宏定义。当中,pos 是指向 list_head 的指针,而 head 是双链表 list_head 中的指针,定义了从何地开始遍历那么些链表。那一个宏的功效正是对一个双向循环链表举行遍历。

 

  list_entry: 在 linux/list.h 中定义,也是贰个宏定义

/**
 * list_entry - get the struct for this entry
 * @ptr:    the &struct list_head pointer.
 * @type:    the type of the struct this is embedded in.
 * @member:    the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) 
    container_of(ptr, type, member)

  list_entry 实际上就是 container_of。

 

  container_of : 在 linux/kernel.h 中定义

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:    the pointer to the member.
 * @type:    the type of the container struct this is embedded in.
 * @member:    the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({                
    void *__mptr = (void *)(ptr);                    
    BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&    
             !__same_type(*(ptr), void),            
             "pointer type mismatch in container_of()");    
    ((type *)(__mptr - offsetof(type, member))); })

  container_of 实现了基于三个协会中的二个分子变量的指针来收获指向任何结构的指针的成效。在那之中,offsetof 也是贰个宏,它的职能是获得成员变量基于其所在结构的地址的偏移量,定义如下:

#define offsetof(TYPE,MEMBER)  ((size_t) &((TYPE *)0) -> MEMBER)        // 获得成员变量member基于其所在结构的地址的偏移量,该宏在 linux/stddef.h 中有定义

  解析一下 offsetof 宏:

1)、((TYPE *) 0) : 将 0 转变来 TYPE 类型的指针。那注解了三个针对性 0 的指针,且那么些指针是 TYPE 类型的;

2)、((TYPE *) 0) -> MEMBE昂科威: 访谈结构中的成员MEMBEKuga,贰个对准 0 的 TYPE 类型的组织;鲜明,MEMBEEscort 的地点正是偏移地址;

3)、&((TYPE *) 0) -> MEMBE奥迪Q5:取多少成员MEMBESportage的地方(不是按位与,不要看错了);

4)、((size_t) &((TYPE *) 0) -> MEMBE奥迪Q7): 强制类型转换来 size_t 类型。 

 

本文由六合联盟网发布于编程应用,转载请注明出处:Librdkafka的根基数据结构,Linux内核学习笔记

关键词: