Technical Interview_eryuebing的博客

牛人博客
Linux(内核剖析)
趣谈Linux操作系统 学习
内存管理
理解Linux内存管理
操作系统的设计与实现
Linux进程管理与调度
嵌入式软开笔试面试题目汇总（超全）
力扣、牛客刷题

2021.6.4
2021.6.4
1 IPC --------3天

一. 进程间通信(IPC)

我们知道进程之间都是相互独立的，任何一个进程的全局变量在另一个进程中是看不到的，如果进程之间需要交换数据就要通过内核。进程间通信(InterProcess
Communication)的本质就是让两个进程看到共同的资源。

进程间通信的目的

• 数据传输：一个进程需要将它的数据发送给另一个进程
• 资源共享：多个进程之间共享同样的资源
• 通知事件：一个进程需要向另一个进程发送消息，通知其发生了某种事情（比如进程终止父进程告诉子进程）
• 进程控制：有些进程希望完全控制另一个进程的执行，此时控制进程希望能够拦截另一个进程的所有陷入和异常，能够及时知道它的状态改变。

PIPE
Linux进程通信（一）——pipe管道 10:36
Linux管道的实现机制11:16
pipe sample 12:09
Pipe内核实现细节

IPC统一管理结构(msg, shm, sem)
【Linux】Linux进程通信与System V IPC机制
key_t键和ftok函数

shm 共享内存 （内核分配page + mmap到各进程虚拟地址空间）
进程间通信方式——共享内存
【Linux】Linux的共享内存 23:00
shm sample 13:30 (通过命令 ipcs 查看shm管理，cat /proc/pid/maps查看shm如何mmap )

shmsg: message Queue
【Linux】Linux的消息队列(内核数据结构)

shsem: semaphore set
【Linux】Linux的信号量集 system V

• waitpid()/wait()

2 内核同步

英文总结
Synchronization (computer science)

专题集锦
同步机制
Linux(内核剖析)
Linux(内核剖析):28—内核同步之（临界区、竞争条件、同步、锁、常见的内核并发、SMNP和UP配置选项、锁的争用和扩展性(锁粒度)）

spinlock
Linux内核同步（二）：自旋锁（Spinlock）
Linux(内核剖析):30—内核同步之（自旋锁(spin lock)、读-写自旋锁(spin wrlock)）

struct spinlock_t sp_lock
spin_lock_init(&sp_lock);
DEFINE_SPINLOCK(sp_lock);

struct spinlock_t      //up 时为空，smp时owner和next
{
#if SMP
           struct __raw_tickets { 
            u16 owner; 
            u16 next; 
        } tickets; 
  #endif
}

spin_lock(&sp_lock);  //up上只关闭强占preempt_disable(); smps上next++，busy testing owner==next时进入
//critical section
spin_unlock(&sp_lock);// up上preempt_enable(); smp还要count++

//有中断访问共享数据的情况，需要屏蔽中断
int flag;
spin_lock_irqsave(&sp_lock, flag); // preempt_disable();lock_irq_save();

spin_lock_irqstore(&sp_lock, flag); //lock_irq_restore(); preempt_enable();

//有bh访问共享数据的情况，需要屏蔽bh
spin_lock_bh(&sp_lock); // lock_bh_disable();preempt_disable();
spin_unlock_bh(&sp_lock); // lock_bh_enable();preempt_enable();

semaphore
应用：互斥：sema_lock(&sem,x); 若x==1等同于mutex，若有几个资源可使用则x等于几
tong
Linux(内核剖析):31—内核同步之（信号量(semaphore)、读写信号量(rw_semaphore)）
Linux内核信号量(semaphore)使用与源码分析
Linux 内核同步（五）：信号量（semaphore）

/*------init semaphore--------*/
struct semaphore sema_lock
sema_lock(&sem_lock, count); //count 表示共有几个可用资源，count=1时和mutex效果一样

/*------lock critical section(can lead to sleep of current thread)--------*/
down(&sem_lock);        //等待时对信号不响应
  //critical section;
up(&sem_lock);

/*------lock critical section(can lead to sleep of current thread)--------*/
ret = down_interruptible(&sem_lock); //该函数返回可能因为1.有可用资源ret=0；2 ctrl+c等信号异常返回ret=-EINTR
if(0 != ret); 
{
	//异常唤醒
	return ret;  //ret = -EINTR or -ETIMEOUT
}
//critical section;
up(&sem_lock);

Mutex

• 互斥量, count=1的轻量级semaphore，可能睡眠(进程中使用)
• Linux(内核剖析):32—内核同步之（互斥体(mutex)）
• Linux内核同步（六）：互斥体（mutex）

/*------init mutex lock--------*/
struct mutex mt_lock
mutex_init(&mt_lock)
DEFINE_MUTEX(mt_lock)

/*------lock critical section--------*/
mutex_lock(&mt_lock);
  //critical area
mutex_unlock(&mt_lock);

mutex_trylock(&mt_lock); //锁成功返回1
mutex_islocked(&mt_lock);

顺序锁seqlock

• 一写多读应用，写优先于读(随时写，不等读完成)，写互斥(一个写者spinlock互斥其他写者)，读者没有锁互斥或保护，读者通过反复读+判断是否有写打断来保证数据完整性（读线程忙测，cup若忙也可以将read线程switchout）
• Linux内核同步（四）：顺序锁（seqlock）

/*------init seqlock--------*/
struct seqlock_t lock;
seqlock_init(&lock);
DEFINE_SEQLOCK(lock);

/*------write thread--------*/
write_seqlock(&lock);
//write data
write_sequnlock(&lock);

/*------read thread--------*/
int count;
do{
	count = read_seqbegin(&lock);
	//read data
}while(read_seqretry(&lock, count))

Barrier
禁止compiler和cup执行时对指令顺序的改变(优化)，确保硬件要求的指令执行顺序

//保证读的先后顺序
if(enable)
rmb();
do_something(attr);

//保证写的先后顺序
attr = x;
wmb();
enable = 1;

//保证读写的先后顺序
attr = get(oldattr)+1；
mb();
enable = 1;

//smp上读写屏障
smp_rmb();
smp_wmb();
smp_mb();
smp_

内核中核心的调度函数的使用（休眠，唤醒）

P1
schedule_timeout()　－－－Ｐ１主动调度（将本进程换出，选择一个新进程执行，Ｐ１睡眠（在ｃｐｕ状态为task_uninterruptable 不接收信号or task_interruptable接收信号的等待队列中）


Ｐ３
wake_up_process(P１)　－－－将待唤醒的Ｐ１进程挂入running进程队列，ｃｐｕ在后续某时刻选中Ｐ１后即执行Ｐ１

使用以上函数的其他内核机制

Ｐ１
**struct semaphore sem_t
down(&sem_t)**
{
	...
	struct semaphore_waiter waiter;
   
    前半部分：挂起本进程：
   　　　　　
    list_add_tail(&waiter.list, &sem->wait_list);　　１将本进程挂入semaphore自己的等待队列中
    waiter.task = current;
    waiter.up = false;
   timeout = schedule_timeout(currnet);　　２block在本函数中（ｃｕｐ中换出本进城，挂入ｃｐｕ睡眠等待队列）。
  

   后半部分：从schedule_timeout函数中返回ｃｕｐ中唤醒得到执行，
	 if(waiter.up == true) return 0;
	...
}


Ｐ３
**up(&sem_t)**
{
	waiter = list_del_first(sem_list); //Ｐ３释放了一个资源，从ｓａｍａ等待队列头取一个等待该资源的进程P1(waiter.task == Ｐ１)
	waiter.up = true;　　　//置标志，使得Ｐ１在ｄｏｗｎ函数的schedule_timeout中返回后，认为获得了资源并成功返回
	wake_up_process(waiter.task);　// 将待唤醒的Ｐ１进程挂入cpu的running进程队列，ｃｐｕ在后续某时刻选中Ｐ１后即执行Ｐ１
}

wait_queue s: 内核同步机制，线程Ａ需要等待某个条件Ｃ满足再继续执行，线程Ｂ确保条件Ｃ满足然后唤醒ｗｑ中等待的线程Ａ
本质及内核实现都和semaphore非常类似，semaphore可以看做wait_queue的特例，conditiaon就是sem->count == 0.
Linux内核等待队列(wait_queue)使用与源码分析
等待队列的简单使用
LDD3 Chapter6 阻塞型ＩＯ

#include <linux/sched.h>
int condition = 0                                         //global variable
DECLARE_WAIT_QUEUE_HEAD(wq);  //global variable

struct task_struct *task1 = NULL;
struct task_struct *task2 = NULL;
struct task_struct *task3 = NULL;


void* T1(void* arg)
{
	...
	wait_event_interruptable(&wq, condition);
	condition = 0;
	
}

void* T2(void* arg)
{
	...
	sleep(1);
	wait_event_interruptable(&wq, condition); //每次加入到ｗｑ链表节点头，所以ｗｑ－＞Ｔ２－＞Ｔ１
	condition = 0;
	...
}

void* T3(void* arg)
{
	...
	condition = 1;
	wake_up_interruptable(&wq); //每一次唤醒ｗｑ中链表的第一个节点记住的进程，此处会唤醒Ｔ２。无法精确指定唤醒某一个任务。
	
	condition = 1;
	wake_up_interruptable(&wq); //，此处会唤醒Ｔ１
}

int __init initFun(void)
{
     condition = 0;
	task1 = kthread_run(T1, NULL, "T1", arg1);
	task2 = kthread_run(T2, NULL, "T1", arg1);
	task3 = kthread_run(T3, NULL, "T1", arg1);
}

void __exit exitFun(void)
{
	kthread_stop(task1);
	kthread_stop(task2);
	kthread_stop(task3);
}

module_init(initFun);
module_exit(exitFun);

Select Poll
poll/select机制的用户层驱动层使用总结
Linux驱动基本理论之——poll机制图解
Linux select的实现原理到底是怎样的？

Pthread

• Linux多线程编程—线程间同步（互斥锁、条件变量、信号量和读写锁）
• 一步一步学linux操作系统: 08 多线程与互斥锁、条件变量
• 线程属性pthread_attr_t简介

pthread_mutex

• 仅实现互斥
• pthread包的mutex实现分析
• glibc nptl库pthread_mutex_lock和pthread_mutex_unlock浅析

pthread_mutex_t mt_lock;
pthread_mutex_init(&mt_lock, NULL);

pthread_mutex_lock(&mt_lock);
   f(sharedata);
pthread_mutex_unlock(&mt_lock);

pthread_mutex_destroy(&mt_lock);

sem (pthread semaphore）

• 互斥: sem_init(&sem, pshare, 1); //pshare=0 是线程间sema, phshare !=0是进城间sema
• 同步: sem_init(&sem, pshare, 0); //

//互斥
sem_t sem;
sem_init(&sem, count); //count = 1 互斥; count = 0同步

sem_wait(&sem);
  f(sharedata);
sem_post(&sem); 

//一对一同步
sem_t sem_rd;
sem_t sem_wr;
sem_init(&sem_wr, 1);
sem_init(&sem_rd, 0);

pthread_create(tid_wr, NULL, writer, arg);
pthread_create(tid_rd, NULL, reader, arg);
pthread_join(tid_wr);
pthread_join(tid_rd);

sem_destroy(&sem_rd);
sem_destroy(&sem_wr);

//thread writer
 sem_wait(&sem_wr);
    write data;
 sem_post(&sem_rd);
 
//thread reader
sem_wait(&sem_rd);
  write_data;
 sem_post(&sem_wr);

pthread_cond_t 条件变量

• 1写多读的同步，写之间互斥，读互相争抢&循环检测(要判断写是否完成)
• 要配合pthread_mutex_t使用
• 深入解析条件变量(condition variables)

int canRd;     //条件
pthread_cond_t cond;
pthread_cond_init(&cond);
pthread_mutex_t mutex;
pthread_mutex_init(&mutex);

pthread_create(tid_wr, NULL, writer, arg);
pthread_create(tid_rd1, NULL, reader, arg);
pthread_create(tid_rd2, NULL, reader, arg);
pthread_join(tid_wr);
pthread_join(tid_rd1);
pthread_join(tid_rd2);

pthread_cond_destroy(&cond);

//thread writer
pthread_mutex_lock(&mutex);
write data;
canRd = true;
pthread_cond_brodcast(&cond); //唤醒所有等待的读者
or pthread_cond_signal(&cond); //按序唤醒第一个等待的读者
pthread_mutex_unlock(&mutex);

//thread reader
pthread_mutex_lock(&mutex);
while( canRd != true)
{
	pthread_cond_wait(&cond, &mutex);
}
read data;
pthread_mutex_unlock(&mutex);

伪代码：线程间同步（pthread + pthread_mutex_t + pthread_cond_t）

#include <pthread.h>

struct msg
{
	void* content;
	struct msg* next;
}

struct msg *msglist;
pthread_mutex_t mymutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t mycond = PTHREAD_COND_INITIALIZER;

bool quit = false;
void* consumer(void* arg)
{
	pthread_t selftid = pthread_self();
	//pthread_detach(selftid); //if no sycronization with main thread.
	
	while(quit)     //main thread control when the consumer to withdraw
	{
	  //判断是否有新数据，需访问共享数据msg，所以必须加锁互斥访问ｍｓｇ
		pthread_mutex_lock(&mymutex);   　
		while(msglist == NULL) 　　//若果无ｍｓｇ，则进入睡眠等待，但睡眠前必须解锁（pthread_cond_wait）。
		{
			if(quit)
			{
				pthread_mutex_unlock(&mymutex);
				pthread_exit();
				return;
			}
			/*
		  1 pthread_cond_wait执行步骤：put current thread to cond wait queue->mutex_unlock->current thread swith out(in waiting queue to be waken up)->(once signal from producer thread) mutex_lock
		  2 有２种情况会被唤醒（写线程ｃｏｎｄ＿ｓｉｇｎａｌ）：
		  　　　ａ有新数据（ｍｓｇ！＝　ｎｕｌｌ，对应处理：判断是否有新数据，若无，则继续ｃｏｎｄ＿ｗａｉｔ（解锁后睡眠，等待下一次唤醒）
		  　　　ｂ　ｑｕｉｔ＝＝ｔｒｕｅ　对应处理：解锁，线程退出
		  */
			pthread_cond_wait(&mycond, &mymutex); 
		}
		//read msglist
		pthread_mutex_unlock(&mymutex);
	}
	pthread_exit();
}

void* producer(void* arg)
{
	pthread_t selftid = pthread_self();
	//pthread_detach(selftid);
	
	while(!endoffile())
	{
		pthread_mutex_lock(&mymutex);
		//write msglist
		pthread_cond_signal(&mycond);  //unlock 之前唤醒所有读线程
	　pthread_mutex_unlock(&mymutex);
		
	}	
	
	//write ends, and notify all readers to withdraw. 
	pthread_mutex_lock(&mymutex);
	quit = true;
	pthread_cond_broadcast(&mycond, &mymutex);  //必须唤醒所有读线程，否则因为写线程退出了写循环而没有新数据了，也就不会cond_signal任何读线程了，而读线程都会睡眠在cond_wait上无法退出，所以此处必须有一个额外的cond_signal唤醒所有的读线程
	pthread_mutex_unlock(&mymutex);
	
	pthread_exit();
}

//main thread
int main()
{
	pthread_t readPid1 = -1, readPid1 = -1, writePid;
	//pthread_mutex_init(&mymutex, NULL); 静态分配的ｍｕｔｅｘ在编译阶段初始化为解锁状态
	//pthread_cond_init(&mycond, NULL);
	
	ret = pthread_create(&readPid1, NULL, consumer, void*arg);
	if(0 != ret) goto err;
	ret = pthread_create(&readPid2, NULL, consumer, void*arg);
	if(0 != ret) goto err;
	ret = pthread_create(&writePid, NULL, producer, void*arg);
	if(0 != ret) goto err;
	
	void* retval;
	pthread_join(readPid1, &retval);
	pthread_join(readPid2, &retval);
	pthread_join(writePid, &retval);
	
	//pthread_mutex_destroy(&mymutex); // only for dynamic allocted mutex pthread_mutex_init(&mymutex, NULL);
	//pthread_cond_destroy(&mycond);
	
	pthread_exit();
	return 0;
}

伪代码：线程间互斥（pthread + pthread_mutex_t + pthread_cond_t）

#include <pthread.h>
#include <semaphor.h>

struct Printer{
}

#define MAX_PRINT_TASK_NUM
#define PRINTER_NUM
struct Printer prints[PRINTER_NUM];
sem_t mysem;

int main()
{
	sem_init(&mysem, 0, PRINTER_NUM);
	pthread_t pid[MAX_PRINT_TASK_NUM];
	cint cnt = 0;
	
	while(q != gechar() && cnt < MAX_PRINT_TASK_NUM)
	{
		printf("please press any key to submit a print task\n");
		scanf("")
		pthread_create(&pid[cnt], NULL, exect_print_func, (void*)file );
	}
	
	
	sem_destroy(&mysem);
	
}

2 TCP/IP，socket， rtsp/rtp -----------3天
Linux网络编程

TCP/IP

• 太厉害了，终于有人能把TCP/IP 协议讲的明明白白了

socket编程

• Linux的SOCKET编程详解
  深入理解socket中的recv函数和send函数
  todo: inet_pton() inet_ntop()实现

#include <sys/socket.h>
#define SERVER_PORT 554
#define SERVER_MAX_CONNC 100
#define BUFF_SIZE 1024
main()
{
	int sockfd = socket(AF_INET, SOCK_STREAM, IPPORTO_TCP);
	if(-1 == sockfd) error;
	
	struct sockaddr_in svaddr;
	svaddr.sin_family = AF_INET;
	svaddr.sin_addr.s_addr = htonl(INADDR_ANY);
	svaddr.sin_port = htons(SEVER_PORT);
	if(-1 == bind(sockfd, (struct sockaddr*)svaddr, sizeof(svaddr))
	 error;
	
	if( -1 == listen(sockfd, SERVER_MAX_CONNC))
	 error;
	
	pthread_t pid[SERVER_MAX_CONNC];
	struct sockaddr_in cliaddr[SERVER_MAX_CONNC];
	int clisock[SERVER_MAX_CONNC];
	int cliaddrlen = 0;
	int clinum = 0;
	while(1)
	{
		clisock[clinum] = accept(sockfd, (struct sockaddr*)&cliaddr[clinum],&cliaddrlen);
		if(-1 == clisock[clinum])
		{
			error;
			continue;
		}
		
		if(0 == pthread_create(&(pid[clinum]), NULL, SeverNetService, &(clisock[clinum])))
		{
			error;
		}
		pthread_detach(pid[clinum]);
		clinum++;
	}
	close(sockfd);
}
void* SeverNetService(void* arg)
{
	int recvlen = 0, sendlen = 0;
	char recvbuff[BUFF_SIZE], sendbuff[BUFF_SIZE];
		
	clisock = *((int*)arg);
	
	while(1)
	{
		//失败时，返回值小于0；超时或对端主动关闭，返回值等于0；成功时，返回值是返回接收数据的长度
		recvlen = recv(clisock, recvbuff, BUFF_SIZE, 0);
		if(recvlen <= 0)
		{
			goto error;
		}
		recvbuff[recvlen] = 0;
		//to deal with received data
		
		//to prepare  send data
		//失败时，返回值小于0；超时或对端主动关闭，返回值等于0；成功时，返回值是返回发送数据的长度
		sendlen = send(clisock, sendbuff, strlen(sendbuff), 0);
		if(sendlen <= 0)
		{
			goto error;
		}
	}
	error:
		close(clisock);
		pthread_exit(0);
}

大小端：endian 表示数的结尾即存储该数的低地址，ｃｐｕ存储和读取内存都是从低地址－－》高地址
如int a = 0x12345678 在大端和小端的机器的内存中存储如下：
　　　　 0x8000 0001 0x8000 0002 0x8000 0003 0x8000 0004
big endian: 12 34 56 78
little endian: 78 56 34 12
　　　　　　　　　　　
big endian: 　最重要（大）的部分存在 endian（低地址）　 == 网络字节序
little endian:　最不重要（小）的部分存在 endian（低地址）
　　　　　　　　　　　　　　　　　　　
大小端转换：
（( a&0x000000ff）<< 24 ) | ( ( a&0x0000ff00 ) << 8 ) | ( ( a&0x00ff0000 ) >> 8 ) | ( ( a&0xff000000 ) >> 24 )

// check cup is little or big endian
int main()
{
	union {
	 int i;
	 char c;
	}temp;
	
	temp.i = 0x12345678;
	if(temp.c == 0x78)
	{
		printf("little endian\n");
	}
	else
	{
		printf("big endian\n");
	}
	return 0
}

//convert little to big endian
int LE2BE(int val)
{
	return ( ((val&0xff)<<24) | ((val&0xff00)<<8) | ((val&0xff0000)>>8) | ((val&0xff000000)>>24) )
}

HTTP

• 一篇文章带你详解 HTTP 协议（网络协议篇一）

RTSP、RTP、RTCP

• RTSP over UDP与RTSP over TCP取流对比
  RTSP消息格式
  网络摄像头Rtsp直播方案（一）－　socket code
  网络摄像头Rtsp直播方案（二）－　rtsp code
  网络摄像头Rtsp直播方案（三）－　rtp code

消息解析sscanf()

1 OPTION:

Client(192.168.1.1) -->Server(10.10.10.1)

Request: OPTIONS rtsp://10.10.10.1:554/h264/ch1/sub/av_stream RTSP/1.0\r\n
Cseq: 2\r\n
User-Agent: LibVLC/2.2.4\r\n
\r\n

Response: RTSP/1.0 200 OK\r\n
Cseq: 2\r\n
Public: OPTIONS, DESCRIBE, SETUP, PLAY, TEARDOWN, GET_PAMAMETER SET_PAMAMETER\r\n
Date: Fri, SEP 10 2021 10:03:30 GMT\r\n
\r\n

2 DESCRIBE
Request: DESCRIBE rtsp://10.10.10.1:554/h264/ch1/sub/av_stream RTSP/1.0\r\n
Cseq: 3\r\n
User-Agent: LibVLC/2.2.4\r\n
Accept: application/sdp\r\n
\r\n

3 boot移植 --------3天
4 mmap ---------2天
认真分析mmap：是什么 为什么 怎么用
mmap内存映射

mmap本身其实是一个很简单的操作，在进程的页表中添加一个页表项，该页表项是物理内存的地址。调用mmap的时候，内核会在改进程的虚拟空间的映射区域查找一块满足需求的空间用于映射该文件，然后生成该虚拟地址的页表项，该页表项此时的有效位(标志是否已经在物理内存中)为0，页表项的内容是文件的磁盘地址，此时mmap的任务已经完成。

当mmap建立完页表的映射后，就可以操作改块内存了，进行的所有改动都会自动写会磁盘文件。第一次访问该块内存的时候，因为页表项的有效位还是0，就会发生缺页中断，然后CPU会使用该页表项的内容也就是磁盘的文件地址，该将地址指向的内容加载到物理内存，并需改页表项的内容为该物理地址，有效位置为1.

todo：仿写 mmap实现映射mem字符驱动的内存
Linux驱动mmap内存映射详解及例子实现
一步一步学linux操作系统: 22 内存管理_用户态内存映射
/proc/$pid/maps文件格式解析

一步一步学linux操作系统: 26 文件系统_虚拟文件系统、挂载文件系统与打开文件

5 fs
一口气搞懂「文件系统」，就靠这 25 张图了
从内核文件系统看文件读写过程
Linux 字符设备驱动开发基础（六）—— VFS 虚拟文件系统解析
6 char device driver mode
一步一步学linux操作系统: 28 输入与输出系统_输入与输出设备的管理
一步一步学linux操作系统: 29 输入与输出系统_ 字符设备一_打开、读写与IOCTL 控制
Linux 字符设备驱动开发
Linux 字符设备驱动结构（一）—— cdev 结构体、设备号相关知识解析
Linux 字符设备驱动结构（三）—— file、inode结构体及chardevs数组等相关知识解析
mknod创建设备文件
一步一步学linux操作系统: 26 文件系统_虚拟文件系统、挂载文件系统与打开文件
嵌入式Linux根文件系统和挂载 — to read

Linux 文件系统与设备文件系统 （二）—— sysfs 文件系统与Linux设备模型

5 多媒体：H264 / VO/ FB/ ---------3天

H264
入门理解H264编码
h264理论
H264句法语法详解专题

• slice header、 MB组成(motion vector) slice的ABC三种类型
  DaveBobo的多媒体编程

6 面试问题
star原则

一 编程题

1 Linked list题

1.2 leetcode
参考
如何判断单链表里面是否有环？
如何判断单链表是否有环、环的入口、环的长度和总长

反转单链表 1
反转部分单链表 1
判段Linked list是否有环 1
求Linked list中环的入口点 1
两Linked list的交点 1
合并两升序链表 1
sorted list删除后续重复节点 1
sorted list删除所有重复节点 1
删除距结尾的第N个节点 1
middle of linked list 1
rotate list 1
insertionSortList 插入法排序链表 1
Convert Binary Number in a Linked List to Integer 1
判断list是否回文串 1
交换成对节点swap-nodes-in-pairs 1
Partition List 1
1.3 二叉树
参考：二叉树的非递归前序、中序、后序遍历算法详解及代码实现（C语言）
preorder iterative遍历 1
inorder iterative遍历 1
postorder iterative遍历

1.4 排序
参考：快速排序算法心得
【C语言】快速排序函数qsort()
quicksort 有重复元素 1
找数组的第Ｋ大元素 — quicksort变型

1.3 string
atoi itoa strlen strcpy strcat strcmp memmove 1

atoi
1 sum超出范围的判断，两种方法。
　1.1 用 long long　计算，再判断是否超出范围
　     isInRange(int sum, int digit)
　     {
　　　　　long long temp = sum*10 + digit;
　　　　　return temp <= INT_MAX;
　　　　}
1.2 用INT_MAX反推本次sum*10+digit是否超出范围
    1/ 如果sum*10 > INT_MAX,肯定超出范围
    ２/ 如果sum == INT_MAX/10　(214748364x),但INT_MAX % 10 < digit也超出范围(2147483648,2147483649)  
　　　　isInRange(int sum, int digit)
　     {
　　　　　return (INT_MAX/10 < sum) || (INT_MAX/10 == sum && INT_MAX % 10 < digit)) 
　　　　}　　
　　注意：仅检测正数。对于负数边界值-2147483648，判断它的正数2147483648超出范围，又因为sign = -1,所以返回INT_MIN.
2 int最大最小值 <limit.h> INT_MAX(0x7fffffff = 2147483647) INT_MIN(0x80000000 = -2147483648)
3 int sign = 1 (+), -1(-). 
3 最后return sign*sum;  or  return sign == 1? sum : (~(sum) + 1);
4 主干
　　　　　while(space) p++; //空格合法：跳过前面的所有空格
　　　　　if(*p == '+' || *p == '-')　　//符合合法：取正确符号
　　　　　{
			if(*p == '-') sign = -1;
		}
　　　　　
        while(*p != '\0') // read until end of string
        {
        	//只要不是０－９就跳出 此阶段＇＇，＇＋＇　＇－＇　其他非数字字符均不合法
        	//for "w470" sum = 0; for "470-" '470 ' '470w' sum=470  
        	if(is not digit(*p)) break;  
        	digit = *p - '0';
        	if(!isInRange(sum, digit))
        	{
        		return sign == 1? INT_MAX:INT_MIN;
        	}
        	sum = sum*10 + digit;
        	p++;
        }
        return sign*sum;

reverse string 1
reverse string II 1
reverse vowels of string 1
strstr 1
最长公共前缀 1
有效的括号　－－stack 1

1.4 search
binary search

> **二分法思想**：对有规律的一组数进行某种二分，选择一半丢弃一半（ｌｏｇ２＾ｎ），不断缩小范围，最后从有限的数中选择答案
> 
> 条件：数组（根据下标可判断数的趋势），数有一定规律（有序，００ｘｘ），答案默认是在[start,end]范围内
> 
> 模板要点：
>  1 while( start + 1 < end) 
> 循环跳出时［start|end］为相邻两元素，while循环作用是缩小范围的，步骤４是选择答案 
> 
> 2 mid = start + (end -start)/2  
> 写成mid = (start + end)/2;不好，因为start + end 可能超出int范围
> 成mid = start + (end - start)>>1;不对，因为>>优先级最低，即=(start + (end - start))>>1, 
> mid = start + ((end - start)>>1) 可能超出int范围 
> 3 if(nums[mid] < target) 
>          start = mid;  
>   else if(nums[mid] == target) 
>             start = mid;   //求第一个target位置end = mid 求最后一个target位置start = mid;   
>    else end = mid;

>     4 最后根据题目要求在相邻的２个数内选择一个答案

九章二分法模板
binary search
firstBadVersion- binary search 1
sqrt(x)
Search Insert Position 1
Find one Peak Element 1
Find K Closest Elements 　BS+背向双指针 1
Find Minimum in Rotated Sorted Array 1
find-first-and-last-position BS+背向双指针 1

双指针
一类　相向双指针

• Two sum 类
  Two Sum --双指针 / hashmap 1
  add-two-numbers o(n + m)

• partition类

二类　背向双指针　
longest-palindromic-substring　o(n^2) 1

三类　同向双指针　
longest-substring-without-repeating　Ｏ（ｎ＾２） hashtable+ 同向双指针 1 ??debug

找出占一半的元素　－－特殊简单算法

1.5 hash
Design HashMap --包括list_head操作
topKFrequent　－－hashtable+quicksort

1.6 BST
binary-tree-level-order-traversal
minimum-depth-of-binary-tree
maximum-depth-of-binary-tree

1.4 编程技巧

字符串

char str1[] = "abcd";  char*p = str1; 
q = p+n: 指向第n个元素的下一个地址空间，如p+strlen(str1)指向'\0'

start end分别是数组的开始和结束元素的下标，则[start,end]间元素的个数l= end - start + 1
start是开始元素的下标　ｌ是元素个数，则结束元素的下标end = start + l -1;  

求q指针和p指针间的字符长度: q-p+1。若q指向'\0', q-p=strlen(str1);   若q指向'd',q-p+1==strlen(str1)

循环处理until string结束
while(*p)  // equals to while('\0' != *p)
{
.....
p++;
 }

 判断条件中++/-- 和在block中++/--的不同 （保险起见prefer后一种）
判断p串是否和q串的子串(内容是否相同） (假设p和q分别指向str1和str2)
A：无论*p,*q是否相等， p，q都指向下一个字符
 while(*p && *p++ = *q++)
 {}
 if(*p)  
 {
    是子串;
 } 
B：若*p,*q不相等，p，q就停留在最后一个相等的字符上
 while（*p && *p = *q）
 {
	 ++p;
	 ++q;
 }
if(*p)
{
  是子串
}
A错误，B正确，例如p=“ab” q=“ac”

二 C语言

1. static / dynamic link
   如何在linux下写静态链接库并卖给别人？
   static link _E

2. 创建静态库.a文件：ar rcs libclass.a class1.o class2.o class3.o

3. 查看静态库中包含的文件: nm -o libclass.a 或者 nm -s libclass.a

4. comple x.c时指定用到的.a库: gcc x.c libclass.a 或者 gcc x.c -lclass

5. link 时指定用到的.a库: ld x.o -lclass

6. dynamic link
   如何在linux下写动态链接库并卖给别人？

7. malloc/free实现

8. C++ 引用

9. boolean TRUE FALSE
   c中逻辑判断: 0 为假， 非0均为真（不是只有1才为真）
   c语言没有布尔类型，c99库才支持布尔型，

 #include  <stdbool.h>
   bool flag = true; flag = false;  

10. 位运算应用

  &：只有1&1=1 ，用于判断哪一位为1
   判断奇偶数:   `(n&1)? 奇数：偶数`     

 给n，表示-n：-n = ~n + 1 = ~(n - 1); 
如代码中写n = -5 效率比较低，写成n = ~5 + 1 (补码); 或n = ~ (5-1);   

n & (n-1) 清除n最右边的1
n & (-n)   取得n最右边的1

11. int 的最大、最小定义

#include <limit.h>
 INT_MAX = 2147483647=0x7fffffff
 INT_MIN = -2147483648 = 0x10000000
 INI_MAX + 1 = INI_MIN (二进制溢出)
 -1 = 0xffffffff

12. #include < > 和 #include " "

关于C语言include尖括号和双引号的对话

linux操作系统

• 一、 系统调用 Linux(内核剖析):13—系统调用的实现与解析
  一步一步学linux操作系统: 06 系统调用
  Linux内核中的fastcall和asmlinkage宏

在进程A中通过系统调用sethostname(const char *name,seze_t len)设置计算机在网络中的“主机名”.
在该情景中我们势必涉及到从用户空间向内核空间传递数据的问题，name是用户空间中的地址，它要通过系统调用设置到内核中的某个地址中。让我们看看这个 过程中的一些细节问题：系统调用的具体实现是将系统调用的参数依次存入寄存器ebx,ecx,edx,esi,edi（最多5个参数，该情景有两个 name和len），接着将系统调用号存入寄存器eax，然后通过中断指令“int 80”使进程A进入系统空间。由于进程的CPU运行级别小于等于为系统调用设置的陷阱门的准入级别3，所以可以畅通无阻的进入系统空间去执行为int 80设置的函数指针system_call()。由于system_call()属于内核空间，其运行级别DPL为0，CPU要将堆栈切换到内核堆栈，即 进程A的系统空间堆栈。我们知道内核为新建进程创建task_struct结构时，共分配了两个连续的页面，即8K的大小，并将底部约1k的大小用于 task_struct（如#define alloc_task_struct() ((struct task_struct ) __get_free_pages(GFP_KERNEL,1))）,而其余部分内存用于系统空间的堆栈空间，即当从用户空间转入系统空间时，堆栈指针 esp变成了（alloc_task_struct()+8192），这也是为什么系统空间通常用宏定义current（参看其实现）获取当前进程的 task_struct地址的原因。每次在进程从用户空间进入系统空间之初，系统堆栈就已经被依次压入用户堆栈SS、用户堆栈指针ESP、EFLAGS、 用户空间CS、EIP，接着system_call()将eax压入，再接着调用SAVE_ALL依次压入ES、DS、EAX、EBP、EDI、ESI、 EDX、ECX、EBX，然后调用sys_call_table+4%EAX，本情景为sys_sethostname()。

• 二、stack overflow_E
  a stack overflow occurs if the call stack pointer exceeds the stack bound.
  进程fork 函数/分配哪些资源/如何调度/
  线程pthread函数/分配哪些资源/
  栈帧详解

三、内核线程创建
kernel_thread() kthread_create()/kthread_run()创建内核线程的区别与使用

//包含的头文件
#include <linux/sched.h>
#include <linux/kthread.h>

//线程执行主函数
int threadFn(void *p)
{
}

第一种
kthread_run(threadFn, threadFnArg, "mythead");
注释：

第二种
struct task_struct *task1 = kthread_create(threadFn, threadFnArg, "mythead");
if(NULL != task1) wake_up_process(task1);

四 内存管理

• buddy system 管理所有物理内存？存放所有页描述符(struct page)的mem_map存放在哪里，何时init，初始化时各page的信息？

• alloc_pages()只分配High-mem?__get_free_pages(gfp_mask, order)分配LowMemory page 直接映射?

• 用户进程对应的物理内存分配在哪个区域，Zone_NOMAL or Zone_HIGH？

• 进程pgd的初始化过程

对于32位的Linux，其每一个进程都有4G的寻址空间，但当一个进程访问其虚拟内存空间中的某个地址时又是怎样实现不与其它进程的虚拟空间混淆 的呢？每个进程都有其自身的页面目录PGD，Linux将该目录的指针存放在与进程对应的内存结构task_struct.(struct mm_struct)mm->pgd中。每当一个进程被调度（schedule()）即将进入运行态时，Linux内核都要用该进程的PGD指针设 置CR3（switch_mm()）。

当创建一个新的进程时，都要为新进程创建一个新的页面目录PGD，并从内核的页面目录swapper_pg_dir中复制内核区间页面目录项至新建进程页面目录PGD的相应位置，具体过程如下：
do_fork() –> copy_mm() –> mm_init() –> pgd_alloc() –> set_pgd_fast()
–> get_pgd_slow() –> memcpy(&PGD + USER_PTRS_PER_PGD, swapper_pg_dir +
USER_PTRS_PER_PGD, (PTRS_PER_PGD - USER_PTRS_PER_PGD) * sizeof(pgd_t))
这样一来，每个进程的页面目录就分成了两部分，第一部分为“用户空间”，用来映射其整个进程空间（0x0000 0000－0xBFFF
FFFF）即3G字节的虚拟地址；第二部分为“系统空间”，用来映射（0xC000 0000－0xFFFF
FFFF）1G字节的虚拟地址。可以看出Linux系统中每个进程的页面目录的第二部分是相同的，所以从进程的角度来看，每个进程有4G字节的虚拟空间，
较低的3G字节是自己的用户空间，最高的1G字节则为与所有进程以及内核共享的系统空间。

进程的页目录PGD（属于内核数据结构）就处于内核空间中。在进程切换时，要将寄存器CR3设置成指 向新进程的页目录PGD，而该目录的起始地址在内核空间中是虚地址，但CR3所需要的是物理地址，这时候就要用__pa()进行地址转换。在 mm_context.h中就有这么一行语句：
asm volatile(“movl %0,%%cr3”: :”r” (__pa(next->pgd));
这是一行嵌入式汇编代码，其含义是将下一个进程的页目录起始地址next_pgd，通过__pa()转换成物理地址，存放在某个寄存器中，然后用mov指令将其写入CR3寄存器中。经过这行语句的处理，CR3就指向新进程next的页目录表PGD了。

• load kernel image

我们把内核的代码和数据就叫内核映像（kernel image）。当系统启动时，Linux内核映像被安装在物理地址0x00100000开始的地方，即1MB开始的区间(第1M留作它用)。然而，在正常 运行时， 整个内核映像应该在虚拟内核空间中，因此，连接程序在连接内核映像时，在所有的符号地址上加一个偏移量PAGE_OFFSET，这样，内核映像在内核空间 的起始地址就为0xC0100000。

内核虚拟地址空间布局

内核线性地址空间部分从PAGE_OFFSET（通常定义为3G）开始，为了将内核装入内存，从PAGE_OFFSET开始8M线性地址用来映射内核所在的物理内存地址（也可以说是内核所在虚拟地址是从PAGE_OFFSET开始的）；接下来是mem_map数组，mem_map的起始线性地址与体系结构相关，比如对于UMA结构，由于从PAGE_OFFSET开始16M线性地址空间对应的16M物理地址空间是DMA区，mem_map数组通常开始于PAGE_OFFSET+16M的线性地址；从PAGE_OFFSET开始到VMALLOC_START – VMALLOC_OFFSET的线性地址空间直接映射到物理内存空间（一一对应影射，物理地址<==>线性地址-PAGE_OFFSET），这段区域的大小和机器实际拥有的物理内存大小有关，这儿VMALLOC_OFFSET在X86上为8M，主要用来防止越界错误；在内存比较小的系统上，余下的线性地址空间（还要再减去空白区即VMALLOC_OFFSET）被vmalloc()函数用来把不连续的物理地址空间映射到连续的线性地址空间上，在内存比较大的系统上，vmalloc()使用从VMALLOC_START到VMALLOC_END（也即PKMAP_BASE减去2页的空白页大小PAGE_SIZE（解释VMALLOC_END））的线性地址空间，此时余下的线性地址空间（还要再减去2页的空白区即VMALLOC_OFFSET）又可以分成2部分：第一部分从PKMAP_BASE到FIXADDR_START用来由kmap()函数来建立永久映射高端内存；第二部分，从FIXADDR_START到FIXADDR_TOP，这是一个固定大小的临时映射线性地址空间，（引用：Fixed virtual addresses are needed for subsystems that need to know the virtual address at compile time such as the APIC），在X86体系结构上，FIXADDR_TOP被静态定义为0xFFFFE000,此时这个固定大小空间结束于整个线性地址空间最后4K前面，该固定大小空间大小是在编译时计算出来并存储在__FIXADDR_SIZE变量中。

正是由于vmalloc()使用区、kmap()使用区及固定大小区（kmap_atomic()使用区）的存在才使ZONE_NORMAL区大小受到限制，由于内核在运行时需要这些函数，因此在线性地址空间中至少要VMALLOC_RESERVE大小的空间。VMALLOC_RESERVE的大小与体系结构相关，在X86上，VMALLOC_RESERVE定义为128M，这就是为什么ZONE_NORMAL大小通常是16M到896M的原因。

896M之谜
内核空间0-896M直接映射，如果物理内存为256M呢？highMem开始地址为3G+256M+8M
物理内存低于896M各个区到底是怎么映射的

• pgd_alloc()实现？进程pgd实际使用的物理内存在哪里？
• 描述内核pgd的swapper_pg_dir何时init,根据什么参数init，存在哪里？

当创建一个新的进程时，都要为新进程创建一个新的页面目录PGD，并从内核的页面目录swapper_pg_dir中复制内核区间页面目录项至新建进程页面目录PGD的相应位置，具体过程如下：
do_fork() –> copy_mm() –> mm_init() –> pgd_alloc() –> set_pgd_fast() –> get_pgd_slow() –> memcpy(&PGD + USER_PTRS_PER_PGD, swapper_pg_dir + USER_PTRS_PER_PGD, (PTRS_PER_PGD - USER_PTRS_PER_PGD) * sizeof(pgd_t))
这样一来，每个进程的页面目录就分成了两部分，第一部分为“用户空间”，用来映射其整个进程空间（0x0000 0000－0xBFFF FFFF）即3G字节的虚拟地址；第二部分为“系统空间”，用来映射（0xC000 0000－0xFFFF FFFF）1G字节的虚拟地址。可以看出Linux系统中每个进程的页面目录的第二部分是相同的，所以从进程的角度来看，每个进程有4G字节的虚拟空间， 较低的3G字节是自己的用户空间，最高的1G字节则为与所有进程以及内核共享的系统空间。

• copy_from_user()的过程和实现细节？

调用copy_from_user(to,from,n），其中to指向内核空间 system_utsname.nodename，譬如0xE625A000，from指向用户空间譬如0x8010FE00。现在进程A进入了内核，在 系统空间中运行，MMU根据其PGD将虚拟地址完成到物理地址的映射，最终完成从用户空间到系统空间数据的复制。准备复制之前内核先要确定用户空间地址和 长度的合法性，至于从该用户空间地址开始的某个长度的整个区间是否已经映射并不去检查，如果区间内某个地址未映射或读写权限等问题出现时，则视为坏地址， 就产生一个页面异常，让页面异常服务程序处理。过程如 下：copy_from_user()->generic_copy_from_user()->access_ok()+__copy_user_zeroing().

BOOT
深入理解uboot 2016 - 基础篇（处理器启动流程分析）

• 系统引导时内存管理

bootmem分配器
1 使用一个位图来管理页, 以位图代替原来的空闲链表结构来表示存储空间, 位图的比特位的数目与系统中物理内存页面数目相同. 若位图中某一位是1, 则标识该页面已经被分配(已用页), 否则表示未被占有(未用页)

内核启动时获取参数方式----Uboot传递参数给内核
uboot环境变量（设置bootargs向linux内核传递正确的参数

五、build Linux平台/工具

• buildroot 认识Buildroot buildroot使用介绍
• Yocto
• OpenWRT 从零开始学习OpenWrt完美教程

其他
你知道这些标点符号用英语怎么说吗？

开发过程管理

1 Agil
2 version control cvs > svn (集中式) > Git （分布式）
clearcase
3 开发过程管理工具
jira系统：
confuence:

２１天：
１、项目介绍－ＴＤＥ
　　　　　　　ＩＰＣＡＭ
　　　　　　　Ｈｉ３５２１／Ｈｉ３５２０
　　　　　　　ｓａｇｅｍｃｏｍ

２、ｌｅｅｔｃｏｄｅ－－复习、新题
３、驱动开发技术点（伪码）－－用户态－　线程创建及同步
　　　　　　　　　　　　　　　　　　　　进程创建及通信
　　　　　　　　　　　　　　　　　　　　网络特性及ｓｏｃｋｅｔ编程
　　　　　　　　　　　　　　　　　　　　ｒｔｓｐ／ｒｔｐ
　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　内核态－同步，互斥
　　　　　　　　　　　　　　－中断＆ＢＨ（ｔａｓｋｌｅｔ，ｗｏｒｋｑｕｅｕｅ）
　　　　　　　　　　　　　　－进程、线程
　　　　　　　　　　　　　　－字符驱动
　　　　　　　　　　　　　　－内存（内核态分配函数，ｍｍａｐ，驱动内存分配）
　　　　　　　　　　　　　　－ｓｙｓｔｅｍ　ｃａｌｌ
　　　　　　　　　　　　　　－ｆｓ
　　　　　　　　　　　　　　－ｂｏｏｔ，ｋｅｒｎｅｌ生成
　　　　　　　　　　　　　　－调试技术
４、开发过程－1 Agil
－2 version control cvs > svn (集中式) > Git （分布式）
clearcase
－　3 开发过程管理工具
jira系统：
confuence: