linux内核数据结构之链表
1、前言
最近写代码需用到链表结构，正好公共库有关于链表的。第一眼看时，觉得有点新鲜，和我之前见到的链表结构不一样，只有前驱和后继指针，而没有数据域。后来看代码注释发现该代码来自linux内核，在linux 源代码下include/Lish.h下。这个链表具备通用性，使用非常方便。只需要在结构定义一个链表结构就可以使用。
2、链表介绍
链表是非常基本的数据结构，根据链个数分为单链表、双链表，根据是否循环分为单向链表和循环链表。通常定义定义链表结构如下：
typedef struct node
{
ElemType data; //数据域
struct node *next; //指针域
}node, *list;
链表中包含数据域和指针域。链表通常包含一个头结点，不存放数据，方便链表操作。单向循环链表结构如下图所示：
双向循环链表结构如下图所示：
这样带数据域的链表降低了链表的通用性，不容易扩展。linux内核定义的链表结构不带数据域，只需要两个指针完成链表的操作。将链表节点加入数据结构，具备非常高的扩展性，通用性。链表结构定义如下所示：
struct list_head {
struct list_head *next, *prev;
};
链表结构如下所示：
需要用链表结构时，只需要在结构体中定义一个链表类型的数据即可。例如定义一个app_info链表，
1 typedef struct application_info
3uint32_t app_id;
4uint32_t up_flow;
5uint32_t down_flow;
6struct list_head app_info_head; //链表节点
7 }app_info;
定义一个app_info链表，app_info app_info_list;通过app_info_head进行链表操作。根据C语言指针操作，通过container_of和offsetof，可以根据app_info_head的地址找出app_info的起始地址，即一个完整ap_info结构的起始地址。可以参考：https://www.doczj.com/doc/704951501.html,/Anker/p/3472271.html。
3、linux内核链表实现
内核实现的是双向循环链表，提供了链表操作的基本功能。
（1）初始化链表头结点
#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)
{
list->next = list;
list->prev = list;
}
LIST_HEAD宏创建一个链表头结点，并用LIST_HEAD_INIT宏对头结点进行赋值，使得头结点的前驱和后继指向自己。
INIT_LIST_HEAD函数对链表进行初始化，使得前驱和后继指针指针指向头结点。
（2）插入节点
1static inline void __list_add(struct list_head *new,
2struct list_head *prev,
3struct list_head *next)
4 {
5next->prev = new;
6new->next = next;
7new->prev = prev;
8prev->next = new;
9 }
10
11static inline void list_add(struct list_head *new, struct list_head *head)
12 {
13__list_add(new, head, head->next);
14 }
15
16static inline void list_add_tail(struct list_head *new, struct list_head *head)
17 {
18__list_add(new, head->prev, head);
插入节点分为从链表头部插入list_add和链表尾部插入list_add_tail，通过调用__list_add函数进行实现，head->next指向之一个节点，head->prev指向尾部节点。
（3）删除节点
1static inline void __list_del(struct list_head * prev, struct list_head * next)
2 {
3next->prev = prev;
4prev->next = next;
5 }
6
7static inline void list_del(struct list_head *entry)
8 {
9__list_del(entry->prev, entry->next);
10entry->next = LIST_POISON1;
11entry->prev = LIST_POISON2;
12 }
从链表中删除一个节点，需要改变该节点前驱节点的后继结点和后继结点的前驱节点。最后设置该节点的前驱节点和后继结点指向LIST_POSITION1和LIST_POSITION2两个特殊值，这样设置是为了保证不在链表中的节点项不可访问，对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
（4）移动节点
1/**
2* list_move - delete from one list and add as another's head
3* @list: the entry to move
4* @head: the head that will precede our entry
5*/
6static inline void list_move(struct list_head *list, struct list_head *head)
7 {
8__list_del(list->prev, list->next);
9list_add(list, head);
10 }
11
12/**
13* list_move_tail - delete from one list and add as another's tail
14* @list: the entry to move
15* @head: the head that will follow our entry
16*/
17static inline void list_move_tail(struct list_head *list,
18struct list_head *head)
20__list_del(list->prev, list->next);
21list_add_tail(list, head);
22 }
move将一个节点移动到头部或者尾部。
（5）判断链表
1/**
2* list_is_last - tests whether @list is the last entry in list @head
3* @list: the entry to test
4* @head: the head of the list
5*/
6static inline int list_is_last(const struct list_head *list,
7const struct list_head *head)
8 {
9return list->next == head;
10 }
11
12/**
13* list_empty - tests whether a list is empty
14* @head: the list to test.
15*/
16static inline int list_empty(const struct list_head *head)
17 {
18return head->next == head;
19 }
list_is_last函数判断节点是否为末尾节点，list_empty判断链表是否为空。（6）遍历链表
1/**
2* list_entry - get the struct for this entry
3* @ptr: the &struct list_head pointer.
4* @type: the type of the struct this is embedded in.
5* @member: the name of the list_struct within the struct.
6*/
7#define list_entry(ptr, type, member) \
8container_of(ptr, type, member)
9
10/**
11* list_first_entry - get the first element from a list
12* @ptr: the list head to take the element from.
13* @type: the type of the struct this is embedded in.
14* @member: the name of the list_struct within the struct.
15*
16* Note, that list is expected to be not empty.
17*/
18#define list_first_entry(ptr, type, member) \
19list_entry((ptr)->next, type, member)
22* list_for_each - iterate over a list
23* @pos: the &struct list_head to use as a loop cursor.
24* @head: the head for your list.
25*/
26#define list_for_each(pos, head) \
27for (pos = (head)->next; prefetch(pos->next), pos != (head); \
28pos = pos->next)
宏list_entity获取链表的结构，包括数据域。list_first_entry获取链表第一个节点，包括数据源。list_for_each宏对链表节点进行遍历。
4、测试例子
编写一个简单使用链表的程序，从而掌握链表的使用。
自定义个类似的list结构如下所示：mylist.h
1 # define POISON_POINTER_DELTA 0
2
3#define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
4#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
5
6//计算member在type中的位置
7#define offsetof(type, member) (size_t)(&((type*)0)->member)
8//根据member的地址获取type的起始地址
9#define container_of(ptr, type, member) ({ \
10const typeof(((type *)0)->member)*__mptr = (ptr); \
11(type *)((char *)__mptr - offsetof(type, member)); })
12
13//链表结构
14struct list_head
15 {
16struct list_head *prev;
17struct list_head *next;
18 };
19
20static inline void init_list_head(struct list_head *list)
21 {
22list->prev = list;
23list->next = list;
24 }
25
26static inline void __list_add(struct list_head *new,
27struct list_head *prev, struct list_head *next)
28 {
29prev->next = new;
30new->prev = prev;
31new->next = next;
32next->prev = new;
35//从头部添加
36static inline void list_add(struct list_head *new , struct list_head *head)
37 {
38__list_add(new, head, head->next);
39 }
40//从尾部添加
41static inline void list_add_tail(struct list_head *new, struct list_head *head) 42 {
43__list_add(new, head->prev, head);
44 }
45
46static inline void __list_del(struct list_head *prev, struct list_head *next) 47 {
48prev->next = next;
49next->prev = prev;
50 }
51
52static inline void list_del(struct list_head *entry)
53 {
54__list_del(entry->prev, entry->next);
55entry->next = LIST_POISON1;
56entry->prev = LIST_POISON2;
57 }
58
59static inline void list_move(struct list_head *list, struct list_head *head) 60 {
61__list_del(list->prev, list->next);
62list_add(list, head);
63 }
64
65static inline void list_move_tail(struct list_head *list,
66struct list_head *head)
67 {
68__list_del(list->prev, list->next);
69list_add_tail(list, head);
70 }
71#define list_entry(ptr, type, member) \
72container_of(ptr, type, member)
73
74#define list_first_entry(ptr, type, member) \
75list_entry((ptr)->next, type, member)
76
77#define list_for_each(pos, head) \
78for (pos = (head)->next; pos != (head); pos = pos->next)
mylist.c如下所示：
1/**@brief 练习使用linux内核链表，功能包括：
2* 定义链表结构，创建链表、插入节点、删除节点、移动节点、遍历节点3*
4*@auther Anker @date 2013-12-15
5**/
6 #include
7 #include
8 #include
9 #include
10 #include "mylist.h"
11//定义app_info链表结构
12 typedef struct application_info
13 {
14uint32_t app_id;
15uint32_t up_flow;
16uint32_t down_flow;
17struct list_head app_info_node;//链表节点
18 }app_info;
19
20
21 app_info* get_app_info(uint32_t app_id, uint32_t up_flow, uint32_t down_flow)
22 {
23app_info *app = (app_info*)malloc(sizeof(app_info));
24if (app == NULL)
25{
26fprintf(stderr, "Failed to malloc memory, errno:%u, reason:%s\n",
27errno, strerror(errno));
28return NULL;
29}
30app->app_id = app_id;
31app->up_flow = up_flow;
32app->down_flow = down_flow;
33return app;
34 }
35static void for_each_app(const struct list_head *head)
36 {
37struct list_head *pos;
38app_info *app;
39//遍历链表
40list_for_each(pos, head)
41{
42app = list_entry(pos, app_info, app_info_node);
43printf("ap_id: %u\tup_flow: %u\tdown_flow: %u\n",
44app->app_id, app->up_flow, app->down_flow);
45
46}
47 }
48
49void destroy_app_list(struct list_head *head)
50 {
51struct list_head *pos = head->next;
52struct list_head *tmp = NULL;
53while (pos != head)
54{
55tmp = pos->next;
56list_del(pos);
57pos = tmp;
58}
59 }
60
61
62int main()
63 {
64//创建一个app_info
65app_info * app_info_list = (app_info*)malloc(sizeof(app_info)); 66app_info *app;
67if (app_info_list == NULL)
68{
69fprintf(stderr, "Failed to malloc memory, errno:%u, reason:%s\n", 70errno, strerror(errno));
71return -1;
72}
73//初始化链表头部
74struct list_head *head = &app_info_list->app_info_node;
75init_list_head(head);
76//插入三个app_info
77app = get_app_info(1001, 100, 200);
78list_add_tail(&app->app_info_node, head);
79app = get_app_info(1002, 80, 100);
80list_add_tail(&app->app_info_node, head);
81app = get_app_info(1003, 90, 120);
82list_add_tail(&app->app_info_node, head);
83printf("After insert three app_info: \n");
84for_each_app(head);
85//将第一个节点移到末尾
86printf("Move first node to tail:\n");
87list_move_tail(head->next, head);
88for_each_app(head);
89//删除最后一个节点
90printf("Delete the last node:\n");
91list_del(head->prev);
92for_each_app(head);
93destroy_app_list(head);
94free(app_info_list);
95return0;
96 }
测试结果如下所示：
参考网址：
https://https://www.doczj.com/doc/704951501.html,/developerworks/cn/linux/kernel/l-chain/
offsetof与container_of宏[总结]
1、前言
今天在看代码时，遇到offsetof和container_of两个宏，觉得很有意思，功能很强大。offsetof是用来判断结构体中成员的偏移位置，container_of宏用来根据成员的地址来获取结构体的地址。两个宏设计的很巧妙，值得学习。linux内核中有着两个宏的定义，并在链表结构中得到应用。不得不提一下linux内核中的链表，设计的如此之妙，只需要两个指针就搞定了。后续认真研究一下这个链表结构。
2、offsetof宏
使用offsetof宏需要包含stddef.h头文件，实例可以参考：
https://www.doczj.com/doc/704951501.html,/reference/cstddef/offsetof/。
offsetof宏的定义如下：
#define offsetof(type, member) (size_t)&(((type*)0)->member)
巧妙之处在于将地址0强制转换为type类型的指针，从而定位到member在结构体中偏移位置。编译器认为0是一个有效的地址，从而认为0是type指针的起始地址。
3、container_of宏
使用container_of宏需要包含linux/kernel.h头文件，container_of宏的定义如下所示：
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
container_of宏分为两部分，
第一部分：const typeof( ((type *)0)->member ) *__mptr = (ptr);
通过typeof定义一个member指针类型的指针变量__mptr，（即__mptr是指向member类型的指针），并将__mptr赋值为ptr。
第二部分： (type *)( (char *)__mptr - offsetof(type,member) )，通过offsetof宏计算出member在type中的偏移，然后用member的实际地址__mptr减去偏移，得到type的起始地址，即指向type类型的指针。
第一部分的目的是为了将统一转换为member类型指针。
4、测试程序
1 #include
2 #include
3
4#define NAME_STR_LEN 32
5
6#define offsetof(type, member) (size_t)&(((type*)0)->member)
7
8#define container_of(ptr, type, member) ({ \
9const typeof( ((type *)0)->member ) *__mptr = (ptr); \
10(type *)( (char *)__mptr - offsetof(type,member) );})
11
12 typedef struct student_info
13 {
14int id;
15char name[NAME_STR_LEN];
16int age;
17 }student_info;
18
19
20int main()
21 {
22size_t off_set = 0;
23off_set = offsetof(student_info, id);
24printf("id offset: %u\n",off_set);
25off_set = offsetof(student_info, name);
26printf("name offset: %u\n",off_set);
27off_set = offsetof(student_info, age);
28printf("age offset: %u\n",off_set);
29student_info *stu = (student_info *)malloc(sizeof(student_info)); 30stu->age = 10;
31student_info *ptr = container_of(&(stu->age), student_info, age); 32printf("age:%d\n", ptr->age);
33printf("stu address:%p\n", stu);
34printf("ptr address:%p\n", ptr);
35return0;
36 }
测试结果：
5、参考网址
任务： 编写一个能向表尾插入结点，并输出链表中所有数据元素的小程序
#ifndef _LINKLIST #define _LINKLIST #include
} void printList_link(PLIST head ) { /*在此处完成任务，输出head为表头的单链表数据元素*/ //begin PLIST p =new NODE; p=head->next; while(p){ printf("%d ",p->data); p=p->next; } //end } void insertDataTail(PLIST head , int insData ) { /*在此处完成任务，在head为表头的单链表表尾插入数据元素insData*/ //begin PLIST p; p=head->next; while(p->next!=NULL){ p=p->next; } PLIST q = new NODE; //初始化结点 p->next=q; q->data=insData; q->next=NULL; //end } #endif
Linux内核通用链表
数据结构的概念： 数据的逻辑结构+ 数据的存储结构+ 数据的操作； 数据的数值：=====》数据===》数值型数据整形浮点数ASCII 非数值型数据图片声音视频字符 =====》数据元素=====》基本项组成（字段，域，属性）的记录。 数据的结构： 逻辑结构 ----》线性结构（线性表，栈，队列） ----》顺序结构 ----》链式结构 ----》非线性结构(树，二叉树，图) ----》顺序结构 ----》链式结构 存储结构 -----》顺序存储 -----》链式存储 -----》索引存储 -----》哈希存储==散列存储 数据的操作： 增 删 改 查 DS ====》数据结构===》DS = (D,R); 数据结构中算法： 1、定义：有穷规则的有序集合。 2、特性： 有穷性 确定性
输入 输出 3、算法效率的衡量 时间复杂度计算===》算法中可执行依据的频度之和，记为：T(n)。 是时间的一种估计值不是准确值。 计算结果的分析：1 将最终结果的多项式中常数项去掉 2 只保留所有多项式中最高阶的项 3 最后的最高阶项要去掉其常数项 时间复杂度的量级关系： 常量阶====》对数阶===》线性阶===》线性对数阶====》平方阶===》立方阶===》指数阶 以上关系可以根据曲线图来判断算法对时间复杂度的要求 空间复杂度计算====》算法执行过程中所占用的存储空间的量级，记为：D（n）。 计算方法是在运行过程中申请的动态内存的量级计算。 ///////////////////////////////////////////////////////////////////////////////////////////////// 线性表 顺序存储====》顺序表（数组） 链式存储====》单链表 特征：对于非空表，a0是表头没有前驱。 an-1 是表尾没有后继 ai的每个元素都有一个直接前驱和直接后继 基本操作：创建表=====》增加元素====》删除元素====》改变元素值====》查询元素 1、顺序表的操作 1.1 创建顺序表=====》定义个指定类型的数组====》int a[100] ={0};
Linux内核的等待队列 Linux内核的等待队列是以双循环链表为基础数据结构，与进程调度机制紧密结合，能够用于实现核心的异步事件通知机制。在Linux2.4.21中，等待队列在源代码树include/linux/wait.h中，这是一个通过list_head连接的典型双循环链表，如下图所示。 在这个链表中，有两种数据结构：等待队列头（wait_queue_head_t）和等待队列项（wait_queue_t）。等待队列头和等待队列项中都包含一个list_head类型的域作为"连接件"。由于我们只需要对队列进行添加和删除操作，并不会修改其中的对象（等待队列项），因此，我们只需要提供一把保护整个基础设施和所有对象的锁，这把锁保存在等待队列头中，为wq_lock_t类型。在实现中，可以支持读写锁（rwlock）或自旋锁（spinlock）两种类型，通过一个宏定义来切换。如果使用读写锁，将wq_lock_t定义为rwlock_t类型；如果是自旋锁，将wq_lock_t 定义为spinlock_t类型。无论哪种情况，分别相应设置wq_read_lock、 wq_read_unlock、wq_read_lock_irqsave、wq_read_unlock_irqrestore、wq_write_lock_irq、wq_write_unlock、wq_write_lock_irqsave和 wq_write_unlock_irqrestore等宏。 等待队列头 struct __wait_queue_head { wq_lock_t lock; struct list_head task_list; }; typedef struct __wait_queue_head wait_queue_head_t; 前面已经说过，等待队列的主体是进程，这反映在每个等待队列项中，是一个任务结构指针（struct task_struct * task）。flags为该进程的等待标志，当前只支持互斥。 等待队列项 struct __wait_queue { unsigned int flags; #define WQ_FLAG_EXCLUSIVE 0x01 struct task_struct * task; struct list_head task_list;
《数据结构课程设计》报告 题目：单链表操作 专业：计算机科学与技术 班级： 单链表操作 针对带头结点的单循环链表，编写实现以下操作的算法函数。
实现要求： ⑴单链表建立函数create：先输入数据到一维数组A[M]中，然后根据一维 数组A[M]建立一个单循环链表，使链表中个元素的次序与A[M]中各元素的次序相同，要求该函数的时间复杂度为O(m)； ⑵定位查找函数Locate：在所建立的单循环链表中查找并返回值为key的 第1个元素的结点指针；若找不到，则返回NULL； ⑶求出该链表中值最大和次大的元素值，要求该算法的时间复杂度为O(m)， 最大和次大的元素值通过指针变量带回，函数不需要返回值； ⑷将链表中所有值比key(值key通过形参传入)小的结点作为值为key的结 点前驱，所有值比key大的结点作为值为key的结点后继，并尽量保持原有结点之间的顺序，要求该算法的时间复杂度为O(m); ⑸设计一个菜单，具有上述处理要求和退出系统功能。 ⒈本人完成的工作： 一、定义结构体：LNode 二、编写以下函数： （1）建立单循环链表 （2）建立定位查找函数 （3）求出链表中最大和次大值 （4）将链表中的值和输入的Key比较，小的作为key前驱结点，大的作为key 的后继结点 三、设计具有上述处理要求和退出系统菜单 ⒉所采用的数据结构：单链表 数据结构的定义： typedef struct Node //定义结点的结构体 { DataType data; //数据域 struct Node *next; //指针域
}LNode; //结点的类型 ⒊所设计的函数 （1）Create(void) LNode *Create(void) //建立单循环链表，链表头结点head作为返回值{ int i,j,n,A[M]; //建立数组A【M】 LNode *head,*p,*move; head=(LNode*)malloc(sizeof(LNode)); //创建空单循环链表head->next=head; move=head; printf("请输入数组元素的个数："); //输入数组 scanf("%d",&n); printf("请输入数组："); for(i=0;i
目录 1 选题背景 (2) 2 方案与论证 (3) 2.1 链表的概念和作用 (3) 2.3 算法的设计思想 (4) 2.4 相关图例 (5) 2.4.1 单链表的结点结构 (5) 2.4.2 算法流程图 (5) 3 实验结果 (6) 3.1 链表的建立 (6) 3.2 单链表的插入 (6) 3.3 单链表的输出 (7) 3.4 查找元素 (7) 3.5 单链表的删除 (8) 3.6 显示链表中的元素个数（计数） (9) 4 结果分析 (10) 4.1 单链表的结构 (10) 4.2 单链表的操作特点 (10) 4.2.1 顺链操作技术 (10) 4.2.2 指针保留技术 (10) 4.3 链表处理中的相关技术 (10) 5 设计体会及今后的改进意见 (11) 参考文献 (12) 附录代码： (13)
1 选题背景 陈火旺院士把计算机60多年的发展成就概括为五个“一”：开辟一个新时代----信息时代，形成一个新产业----信息产业，产生一个新科学----计算机科学与技术，开创一种新的科研方法----计算方法，开辟一种新文化----计算机文化，这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。 数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出，“在工业革命中其核心作用的是能量，而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构（数据结构）是计算机科学研究的基本课题，数据结构又是算法研究的基础。
2 方案与论证 2.1 链表的概念和作用 链表是一种链式存储结构，链表属于线性表，采用链式存储结构，也是常用的动态存储方法。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作线性链表（单链表） 单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 单链表 1、链接存储方法 链接方式存储的线性表简称为链表（Linked List）。 链表的具体存储表示为： ① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)） 注意： 链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。 2、链表的结点结构 ┌───┬───┐ │data │next │ └───┴───┘ data域--存放结点值的数据域 next域--存放结点的直接后继的地址（位置）的指针域（链域） 注意： ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 ②每个结点只有一个链域的链表称为单链表（Single Linked List）。
吉林工商学院 Linux红帽认证模拟（2015年6月版） 说明：均为多选题，每题一分，共一百分。可以翻书或在Linux实验环境中验证。 竞赛时间100分钟。 一、执行 su 命令后，$PATH变量被重置，一般可以通过修改/etc/login.defs中的_______ 值来改变 1 PATH 2 ENV_PATH 3 ENV_SUPATH 4 SU 二、在/etc/fstab文件中，我们可以看到以下信息 : 1 文件系统名 2 文件系统类型 3 文件系统大小 4 文件系统在系统中被fsck检查的顺序 三、为了能够使用 ls 程序列出目录的内容，并能够使用 cd 进入该目录，操作者需要有 _____ 该目录的权限 1 读 2 写 3 执行 4 递归 四、常用的输入输出重定向符号有： 1 > 2 < 3 >> 4 << 五、Linux系统中的设备的类型包括： 1 块设备 2 字符设备
精选文库 4 缓冲设备 六、Linux系统安全管理的内容包括： 1 普通用户的系统安全 2 文件系统的安全 3 进程安全 4 文件内容安全 七、在/etc/passwd文件中保存的其它特殊帐户缺省情况下包括： 1 syslog 2 ftp 3 mail 4 lp 八、bash环境中，常用的逻辑运算符有： 1 -a 2 -o 3 ! 4 != 九、为运行一个写好的shell程序，我们可以使用下列方法： 1 改变程序的属性 2 启动shell后，在外壳下运行 3 加入初使行#！/bin/sh 4 使用命令替换方式 十、使用chmod命令修改文件权限时，可以使用的有关用户的选项参数有： 1 g 2 u 3 o 4 a 十一、bash环境中，常用的字符串运算符有： 1 = 2 ！=
如何获取Linux内核源代码 下载Linux内核当然要去官方网站了，网站提供了两种文件下载，一种是完整的Linux 内核，另一种是内核增量补丁，它们都是tar归档压缩包。除非你有特别的原因需要使用旧版本的Linux内核，否则你应该总是升级到最新版本。 使用Git 由Linus领头的内核开发队伍从几年前就开始使用Git版本控制系统管理Linux内核了（参考阅读：什么是Git？），而Git项目本身也是由Linus创建的，它和传统的CVS不一样，Git是分布式的，因此它的用法和工作流程很多开发人员可能会感到很陌生，但我强烈建议使用Git下载和管理Linux内核源代码。 你可以使用下面的Git命令获取Linus内核代码树的最新“推送”版本： $ git clone git://https://www.doczj.com/doc/704951501.html,/pub/scm/linux/kernel/git/torvalds/linux-2.6.git 然后使用下面的命令将你的代码树与Linus的代码树最新状态同步： $ git pull 安装内核源代码 内核包有GNU zip（gzip）和bzip2格式。Bzip2是默认和首选格式，因为它的压缩比通常比gzip更好，bzip2格式的Linux内核包一般采用linux-x.y.z.tar.bz2形式的文件名，这里的x.y.z是内核源代码的具体版本号，下载到源代码包后，解压和抽取就很简单了，如果你下载的是bzip2包，运行： $ tar xvjf linux-x.y.z.tar.bz2 如果你下载的是gzip包，则运行： $ tar xvzf linux-x.y.z.tar.gz 无论执行上面哪一个命令，最后都会将源代码解压和抽取到linux-x.y.z目录下，如果你使用Git下载和管理内核源代码，你不需要下载tar包，只需要运行git clone命令，它就会自动下载和解压。 内核源代码通常都会安装到/usr/src/linux下，但在开发的时候最好不要使用这个源代码树，因为针对你的C库编译的内核版本通常也链接到这里的。 应用补丁
实验名称：实验一单链表的基本操作 实验目的 熟练掌握线性表两类存储结构的描述方法。 实验内容 从键盘读入若干个整数，建一个整数单链表，并完成下列操作： （1）打印该链表； （2）在链表中插入一个结点，结点的数据域从键盘读入，打印该链表； （3）在链表中删除一个结点，被删结点的位置从键盘读入，打印该链表； （4）在链表中做查找：从键盘读入要查找的整数，将该整数在链表中的位置打印出来，若要查找的整数不在链表中，返回一个信息。 算法设计分析 （一）数据结构的定义 单链表存储结构定义为： struct Node; typedef struct Node * pnode; struct Node { int info; pnode link; }; typedef struct Node * LinkList; （二）总体设计 程序由主函数、创建单链表函数、链表长度函数、链表打印函数、插入正整数函数、删除函数、查询函数组成。其功能描述如下： （1）主函数：调用各个函数以实现相应功能 int main(void) //主函数 { printf("单链表的基本操作实验：\n"); struct list *pnode; pnode = creat(); //创建 print(pnode); //输出 insert(pnode); //插入 print(pnode); //输出 _delete(pnode); //删除 print(pnode); //输出 _located(pnode); //查找 print(pnode); //输出 return 0 ; } （三）各函数的详细设计： Function1: struct list *creat()//创建链表；
对于每一个配置选项，用户可以回答"y"、"m"或"n"。其中"y"表示将相应特性的支持或设备驱动程序编译进内核；"m"表示将相应特性的支持或设备驱动程序编译成可加载模块，在需要时，可由系统或用户自行加入到内核中去；"n"表示内核不提供相应特性或驱动程序的支持。只有<>才能选择M 1. General setup（通用选项） [*]Prompt for development and/or incomplete code/drivers，设置界面中显示还在开发或者还没有完成的代码与驱动，最好选上，许多设备都需要它才能配置。 [ ]Cross-compiler tool prefix，交叉编译工具前缀，如果你要使用交叉编译工具的话输入相关前缀。默认不使用。嵌入式linux更不需要。 [ ]Local version - append to kernel release，自定义版本，也就是uname -r可以看到的版本，可以自行修改，没多大意义。 [ ]Automatically append version information to the version string，自动生成版本信息。这个选项会自动探测你的内核并且生成相应的版本，使之不会和原先的重复。这需要Perl的支持。由于在编译的命令make-kpkg 中我们会加入- –append-to-version 选项来生成自定义版本，所以这里选N。 Kernel compression mode (LZMA)，选择压缩方式。 [ ]Support for paging of anonymous memory (swap)，交换分区支持，也就是虚拟内存支持，嵌入式不需要。 [*]System V IPC，为进程提供通信机制，这将使系统中各进程间有交换信息与保持同步的能力。有些程序只有在选Y的情况下才能运行，所以不用考虑，这里一定要选。 [*]POSIX Message Queues，这是POSIX的消息队列，它同样是一种IPC(进程间通讯)。建议你最好将它选上。 [*]BSD Process Accounting，允许进程访问内核，将账户信息写入文件中，主要包括进程的创建时间/创建者/内存占用等信息。可以选上，无所谓。 [*]BSD Process Accounting version 3 file format，选用的话统计信息将会以新的格式（V3）写入，注意这个格式和以前的v0/v1/v2 格式不兼容，选不选无所谓。 [ ]Export task/process statistics through netlink (EXPERIMENTAL)，通过通用的网络输出工作/进程的相应数据，和BSD不同的是，这些数据在进程运行的时候就可以通过相关命令访问。和BSD类似，数据将在进程结束时送入用户空间。如果不清楚，选N（实验阶段功能，下同）。 [ ]Auditing support，审计功能，某些内核模块需要它（SELINUX），如果不知道，不用选。 [ ]RCU Subsystem，一个高性能的锁机制RCU 子系统，不懂不了解，按默认就行。 [ ]Kernel .config support，将.config配置信息保存在内核中，选上它及它的子项使得其它用户能从/proc/ config.gz中得到内核的配置,选上，重新配置内核时可以利用已有配置Enable access to .config through /proc/config.gz，上一项的子项，可以通过/proc/ config.gz访问.config配置，上一个选的话，建议选上。 (16)Kernel log buffer size (16 => 64KB, 17 => 128KB) ，内核日志缓存的大小，使用默认值即可。12 => 4 KB，13 => 8 KB，14 => 16 KB单处理器，15 => 32 KB多处理器，16 => 64 KB，17 => 128 KB。 [ ]Control Group support（有子项），使用默认即可，不清楚可以不选。 Example debug cgroup subsystem，cgroup子系统调试例子 Namespace cgroup subsystem，cgroup子系统命名空间 Device controller for cgroups，cgroups设备控制器
#include
if(!p||j>i-1) return; lnode *s=new lnode; s->data=e; s->next=p->next; p->next=s; }//插入 void deletelist(lnode *&head,int i,int &e){ lnode *p=head; int j=0; while(p->next&&j
单链表 1 题目编写一个程序，实现链表的各种基本运算，包括：链表操作：初始化链表、输出链表、输出链表长度和释放链表链表元素操作：插入元素、删除元素、输出元素（注意元素的位置） 2 目标熟悉单链表的定义及其基本操作的实现 3 设计思想 链表由多个结点通过next 指针连接成一个完整的数据结构，每个几点包括一个数据域和一个指向下一个结点的next 指针。通过对指针的改写与结点的增减，我们可以实现单链表的插入、删除、输入、输出、求长等操作。 4 算法描述 （1 ）初始化链表：输入元素个数n ，分配n 个结点空间，输入元素值，按元素顺序初始化next 指针，使之连接成串，尾指针赋值NULL 。 （2 ）输出链表：从表头开始沿next 指针遍历各结点，每次访问结点输出结点数据值，直至next 为空。 （3 ）输出链表长度：从表头开始沿next 指针遍历各结点，每次访问结点计数器加一，直至next 为空，返回计数器值。 （4 ）释放链表：沿next 指针从前向后依次释放结点，直至next 指空。 （5 ）插入元素：指针沿next 指向移动指定位，新分配一个空间并存入数据，其next 赋值为当前指针指向结点的next ，修改当前指针指向结点的next 指向新加结点。 （6 ）删除元素：指针沿next 指向移动指定位，修改待删结点的前一结点的next 指针指向待删结点的下一结点，保存数值，释放删除结点。 （7 ）输出元素：指针沿next 指向移动指定位，指针指向结点数据区，读出数值返回。 5 程序结构图 6源程序 #i nclude
#i nclude
Linux-2.6.18移植 有了我们的交叉编译环境和我们先前学的内核基础知识，下面我们就开始我们的内核移植了，我们所用的是博创的 S3C2410 。 关于 linux-2.6.18.tar.bz2 的下载网站先前我们说过，我们要先到该官方网站上去下载一个全新的内核。 [root@Binnary ~ ]# tar –jxvf linux-2.6.18.tar.bz2 [root@Binnary ~ ]# make mrproper 如果你是新下载的内核，那这一步就不用了。但如果你用的是别人移植好的内核，那最好在编译内核之前先清除一下中间文件，因为你们用来编译内核的交叉编译工具可能不同。 第一步：修改Makefile文件 将 改为 第二步：修改分区设置信息 我们要先在BootLoader中查看相应的分区信息 vivi>help 然后修改内核源码中的分区信息。分区信息文件在 a rch/arm/mach-s3c2410/common-smdk.c 将其中的
改为如下内容：
第三步：内核通过 BootLoader把数据写入NAND Flash，而vivi的ECC效验算法和内核的不同，内核的效验码是由NAND Flash控制器产生的，所以在此必须禁用NAND Flash ECC。所以我们就要修改 drivers/mtd/nand/s3c2410.c 这个文件。将 中的 chip->ecc.mode = NAND_ECC_SOFT ，改为如下 chip->ecc.mode = NAND_ECC_NONE。
只此一处。 第四步：下面是devfs的问题，因为2.6.12内核以后取消了devfs的配置选项，缺少了它内核会找不到mtdblock设备。所以我们需要修改 fs/Kconfig 文件，或者是从2.6.12的fs/Kconfig中拷贝下面几项到2.6.18的fs/Kconfig中去，我们采用修改的方法来完成。 修改 fs/Kconfig支持devfs 。 在Pseudo filesystems 主菜单的最后添加我们所要的内容。 第五步：文件系统的支持 Yaffs 文件系统 YAFFS文件系统简介 YAFFS，Yet Another Flash File System，是一种类似于JFFS/JFFS2的专门为Flash设计 的嵌入式文件系统。与JFFS相比，它减少了一些功能，因此速度更快、占用内存更少。 YAFFS和JFFS都提供了写均衡，垃圾收集等底层操作。它们的不同之处在于： （1）、JFFS是一种日志文件系统，通过日志机制保证文件系统的稳定性。YAFFS仅仅 借鉴了日志系统的思想，不提供日志机能，所以稳定性不如JAFFS，但是资源占用少。 （2）、JFFS中使用多级链表管理需要回收的脏块，并且使用系统生成伪随机变量决定 要回收的块，通过这种方法能提供较好的写均衡，在YAFFS中是从头到尾对块搜索， 所以在垃圾收集上JFFS的速度慢，但是能延长NAND的寿命。 （3）、JFFS支持文件压缩，适合存储容量较小的系统；YAFFS不支持压缩，更适合存 储容量大的系统。 YAFFS还带有NAND芯片驱动，并为嵌入式系统提供了直接访问文件系统的API，用 户可以不使用Linux中的MTD和VFS，直接对文件进行操作。NAND Flash大多采用 MTD+YAFFS的模式。MTD（ Memory Technology Devices，内存技术设备）是对Flash 操作的接口，提供了一系列的标准函数，将硬件驱动设计和系统程序设计分开。 Yaffs 文件系统内核没有集成，可以对其主页下载： https://www.doczj.com/doc/704951501.html,/cgi-bin/viewcvs.cgi/#dirlist
序言 由于开发环境需要在linux-2.6内核上进行，于是准备对我的虚拟机上的Linux系统升级。没想到这一弄就花了两天时间( 反复装系统，辛苦啊~~)，总算把Linux系统从2.4.20-8内核成功升级到了2.6.18内核。 网上虽然有很多介绍Linux内核升级的文章，不过要么过时，下载链接失效；要么表达不清，不知所云；更可气的是很多 文章在转载过程中命令行都有错误。刚开始我就是在这些“攻略”的指点下来升级的，以致于浪费了很多时间。 现在，费尽周折，升级成功，心情很爽，趁性也来写个“升级攻略”吧！于是特意又在虚拟机上重新安装一个Linux系统 ，再来一次完美的升级，边升级边记录这些步骤，写成一篇Linux内核升级记实录(可不是回忆录啊！)，和大家一起分享 ~~！ 一、准备工作 首先说明，下面带#号的行都是要输入的命令行，且本文提到的所有命令行都在终端里输入。 启动Linux系统，并用根用户登录，进入终端模式下。 1、查看Linux内核版本 # uname -a 如果屏幕显示的是2.6.x，说明你的已经是2.6的内核，也用不着看下文了，该干什么干什么去吧！~~~如果显示的是 2.4.x，那恭喜你，闯关通过，赶快进行下一步。 2、下载2.6内核源码 下载地址：https://www.doczj.com/doc/704951501.html,/pub/linux/kernel/v2.6/linux-2.6.18.tar.bz2 3、下载内核升级工具 (1)下载module-init-tools-3.2.tar.bz2 https://www.doczj.com/doc/704951501.html,/pub/linux/utils/kernel/module-init-tools/module-init-tools-3.2.tar.bz2 (2)下载mkinitrd-4.1.18-2.i386.rpm https://www.doczj.com/doc/704951501.html,/fedora/linux/3/i386/RPMS.core/mkinitrd-4.1.18-2.i386.rpm (3)下载lvm2-2.00.25-1.01.i386.rpm https://www.doczj.com/doc/704951501.html,/fedora/linux/3/i386/RPMS.core/lvm2-2.00.25-1.01.i386.rpm (4)下载device-mapper-1.00.19-2.i386.rpm https://www.doczj.com/doc/704951501.html,/fedora/linux/3/i386/RPMS.core/device-mapper-1.00.19-2.i386.rpm (2.6.18内核和这4个升级工具我都有备份，如果以上下载地址失效，请到https://www.doczj.com/doc/704951501.html,/guestbook留下你的邮箱，我给你发过去)
#include
} LinkList InitList(void) { int i=1; char ch;//判断是否还输入 LinkList head=0,r,t;//r指向新创建的结点,t指向r的前一个结点 head=(struct nodes *)malloc(sizeof(struct nodes)); if(!head) { printf("存储空间分配失败\n"); return 0; } head->front=head; head->next=head; head->data='a'; t=r=head; while(1) { r=(struct nodes *)malloc(sizeof(struct nodes)); if(!r) { printf("存储空间分配失败\n"); return 0; }
文件系统相关数据结构及相互间的关系 一．详细关系： 1.进程要访问文件，就要首先与文件系统中要访问的文件建立连接，在进程数据结构task_struct中，有两个指针fs和files，一个指向fs_struct数据结构，是关于文件系统的信息；另一个指向files_struct数据结构，是关于已打开文件的信息。 2.fs_struct数据结构中有dentry结构指针,dentry结构中有inode结构指针。Dentry结构所代表的是逻辑意义上的文件，记录的是其逻辑上的属性，而inode 结构所代表的是物理意义上的文件，记录的是物理上的属性。它们之间的关系是多对一的关系。Inode结构中定义union数据结构用于大致反应Linux内核目前所支持的各种文件系统。 2.1.dentry结构中有一个d_inode指针指向相应的inode结构，dentry结构代表的是逻辑意义上的文件，描述文件的逻辑属性，因此目录项在磁盘上并没有对应的映像；而inode结构代表的是物理意义上的文件，记录其物理属性，对与一个具体的文件系统，inode结构在磁盘上有对应的映像。由此可见，一个索引节点对象可能对应多个目录项对象。一个有效的dentry结构必定对应一个inode 结构，这是因为一个目录项要么代表一个文件，要么代表一个目录，而目录实际上也是文件。所以只要dentry结构是有效的，则其指针d_inode必定指向一个inode结构。反之则不成立，因为一个inode可以对应多个dentry结构，即一个文件可以有不止一个文件名或路径名。因为一个已经建立的文件可以被链接到其他文件名。所以inode结构中有一个i_dentry，凡是代表着同一个文件的所有目录项都通过其dentry结构体中的d_alias域挂入相应的inode结构体中的
【IT168 评论】从2008年1月底至今，Linux Kernel系统内核已经先后升级了十次，版本号也从2.6.24上升到2.6.33，并且下个版本2.6.34也已进入开发阶段。今天我们就看看过去两年内这十个版本在性能上有何差异。 测试平台是一套工作站系统，硬件配置包括AMD Opteron 2384 2.7GHz四核心处理器(“上海”)、泰安Thunder n3600B S2927主板(NVIDIA nForce 3600PRO 芯片组)、4GB DDR2 ECC Reg内存、希捷ST3300622AS 300GB硬盘、ATI FirePro V8700显卡，软件上采用Ubuntu 8.04.4 LTS 64位操作系统，组件有GNOME 2.22.3、https://www.doczj.com/doc/704951501.html, Server 1.4.0.90、GCC 4.2.4、EXT3。 Linux Kernel 2.6.24-2.6.33的每个版本都从Ubuntu PPA源上获取，而且均为64位版本。除了替换内核之外，系统其他设置均保持默认。 Apache Benchmark(静态网页服务)：2.6.33成绩大幅提升，但事实最早的2.6.24版反而才是好的，之后八个版本都差得很多，最新版终于基本正常了。
PostgreSQL pgbench(每秒钟TPC-B交易数)：2.6.30的成绩比上个版本骤然提升了多达770%，但之后2.6.32迅速下滑，最新的2.6.33却又完全不如2.6.30之前的六个版本了。
7-Zip Compression(文件压缩速度)：不同版本有所波动，最新的2.6.33成了赢家，这才是我们最希望看到的。 LZMA Compression(256MB文件压缩)：十个版本几乎没什么区别。