rtl面试之循环存储结构 十月 13th, 2010
今天终于面试了Realtek，我是两场面试。第一场是下午1点开始，面试官给了一个题目，是关于环形存储结构实现的，大意如下
有一块内存，有一个线程在往其中写，有一个线程从其中往外读。写线程每当写到此buffer的末端时，应将从此buffer头重新写。然而要求写线程不得刷掉未读过的数据，读线程不得读取未写过的内存。请编程写操作函数。
当时我满脸通红，手心盗汗，竟像是第一次牵宝贝儿的手。虽然还是沉思后找到了解决方法，但是写函数时连返回类型都忘了写。虽然还是把原理和面试官讲清楚，但是连一点编程规范都没有，更不要说什么风骚品味。
原理很简单，就是将写线程对该内存首地址的相对偏移地址记录为wnum, 对应的读线程为rnum，每次写或者读的时候比较一下wnum与rnum的值就可以确定读与写的范围。
今晚在吃饭的时候很不服，晚上回来还是把这个程序写完，贴到这边，
02 #include <stdlib.h>
03
04 typedef unsigned int uint32_t;
05
06 typedef struct _loop_fifo{
07 uint32_t wnum;
08 uint32_t rnum;
09 void **data;
10 uint32_t total_num;
11 }loop_fifo_t;
12
13
14 int loop_fifo_init(loop_fifo_t *lf, uint32_t totalnum)
15 {
16 loop_fifo_t *plf = lf;
17
18 plf->wnum = 0;
19 plf->rnum = 0;
20
21 *(plf->data) = malloc(totalnum);
22
23 plf->total_num = totalnum;
24
25 return 0;
26 }
27
28 int loop_fifo_read(loop_fifo_t *lf ,void *destaddr, uint32_t tobe_rnum)
29 {
30 int flag;
31
32 loop_fifo_t *plf = lf;
33 uint32_t total_num = plf->total_num;
34
35 if(plf->wnum >= plf->rnum)
36 flag = 0;
37 else
38 flag = 1;
39
40 if(flag)
41 {
42 assert(tobe_rnum + plf->rnum - total_num < plf->wnum);
43
44 if(tobe_rnum + plf->rnum < total_num)
45 {
46 memcpy(destaddr, *(plf->data + plf->rnum), tobe_rnum);
47 plf->rnum = tobe_rnum + plf->rnum;
48 }
49 else
50 {
51 int div_num = total_num - (tobe_rnum + plf->rnum);
52 memcpy(destaddr, *(plf->data + plf->rnum), total_num - div_num);
53 memcpy(*(&destaddr + div_num), *plf->data, div_num);
54
55 plf->rnum = tobe_rnum + plf->rnum - total_num;
56 }
57
58 }
59 else
60 {
61 assert(tobe_rnum + plf->rnum < plf->wnum);
62
63 memcpy(destaddr, *(plf->data + plf->rnum), tobe_rnum);
64
65 plf->rnum += tobe_rnum;
66 }
67
68 return 0;
69 }
【扩展】
在第二场面试时，CN部的面试官提出如何使用一个描述符结构来管理此块内存。我又将该环形存储结构进行了如下扩展（这个不是当场完成的，是我后来补充的）。
rtl网卡Datasheet和linux源码阅读笔记之二 九月 9th, 2010
网卡的autonegotiation机制
本文章是关于网卡的auto negotiation机制，阐述的脉络为：
1. aneg机制解决的问题和内容 ；
2. aneg机制在用户层的程序；
3. aneg机制在MII中的控制接口；
4. aneg机制在PHY层的实现；
5. aneg机制在Linux中的源码分析；
关于更多的详细信息，可以在本文章中给出的链接中获得；
[aneg机制的解决问题与内容]
解决网路两端网卡接口速率与模式不匹配的问题，主要是协商如下几个范围
1) Half/Full – Duplex(双工 or 半双工);
2) Speed(传输速率);
[aneg机制在用户层的程序]
仅以本人的PC为例，
对于Windows下，以下图片摘记本人实验室的XP系统PC且装有intel专有的网卡驱动接口)
 |
| From blog_aneg |
在Linux下，(以下内容摘记本人的ubuntu server的ethtool程序的打印信息)
为了能显示更多的非aneg信息，以及为了能以更加直观的表示，本人还是使用了windows下的diff工具
 |
| From blog_aneg |
[aneg机制PHY与MAC的接口---MII]
以下是Realtek系列网卡的MII接口寄存器详细信息
 |
| From blog_aneg |
 |
| From blog_aneg |
在这里的MII有个bit位名称为Nway即为autonegotiation的控制位。
而speedctrl, duplexctrl即为手动控制时需要设置的。
[aneg机制实现所在的协议层]
如下图所示，(以下图片摘记Matthew Hersh 的文章) |
| From blog_aneg |
 |
| From blog_aneg |
关于medium的类型讲述，可以参阅techfest系列文章
[aneg机制在Linux源码中的实现]
rtl网卡Datasheet与linux驱动源码阅读笔记 九月 6th, 2010
在我们使用ifconfig命令查看NI的信息时。有这样一行标志量，如下红色字体显示
eth0 Link encap:以太网 硬件地址 00:27:13:69:7e:b7
inet 地址:10.6.15.139 广播:10.6.15.255 掩码:255.255.255.0
inet6 地址: fe80::227:13ff:fe69:7eb7/64Scope:Link
UP BROADCAST RUNNING MULTICAST MTU:1500 跃点数:1
接收数据包:91978 错误:0 丢弃:0 过载:0帧数:0
发送数据包:48368 错误:0 丢弃:0 过载:0载波:0
碰撞:0 发送队列长度:100
接收字节:65581015 (65.5 MB) 发送字节:11198359 (11.1 MB)
Memory:fc600000-fc620000
其中，这些标志量包含如下几组
1) 接口打开状态(UP or DOWN)
2) 接口运行状态(RUNNING ornot)
3) 接口是否环回接口(LOOPBACKor not)
4) 接口的广播与多播状态(BROADCASTor MULTICAST or not)
这两个标志量说明了网卡对广播包与多播包的过滤特性。接下来我所阐述的内容，就是围绕如何实现上述的BROADCAST和MULTICAST这两个标志量而展开的。由于2者有相互参考性，所以本人只重点阐述MULTICAST。内容涉及的范畴是由以下顺序进行，
网络层--->链路层之以太网层 ---> 链路层之网卡驱动与芯片寄存器--->链路层之物理层
【网络层】
IP多播是以IP层的D类地址，也就是多播组地址为基础的。多播组地址包括4个MSB(1110)和随后28bits的多播组号。用点分十进制表示为224.0.0.0到239.255.255.255。
【链路层之以太网层】
在以太网地址中，前3个most significant byes为01:00:5e是被保留作为多播地址的。网络层的IP多播地址与以太网多播地址的映射关系如下图(以下图片摘记TCP/IP详解之134页)
可以看出来此映射是多对一映射。
【链路层之网卡驱动与芯片寄存器】
在现代网卡中，一般都包含多播包过滤寄存器MAR(multicastaddress filter register, 8bytes)。这些寄存器提供了对接受帧中的多播帧的Mask。在接受设置寄存器RCR(RxConfigureRegister)assert相应的位后(一般为AcceptBroadcast, Accpet Multicast或Accept All)，网卡就必须采用上述的Mask对接受的数据帧进行过滤。
以下是rtl公司的系列网卡的MAR寄存器组的扼要说明
R/W, 64 bits, Multicast hash table. If the‘n’ bit value is set ‘1’, it implies the receiving frames which hash value with‘n’ will be indicated.
关于Mask的设置方法，也就是对MAR寄存器的位写入，在这里本人仅结合rtl的网卡驱动举个例子，其余可以类推。
例子
1) 将MAR0至MAR7分为2组，前一组位MAR0-3，记为组0；后一组为MAR4-7，记为组1；
2) 欲将本网卡加入01:00:5e:01:02:03这个多播组；
3) 计算01:00:5e:01:02:03的CRC-32值，计算得0x044eac67(关于这个计算方法，请参阅本文的扩展阅读部分)；
4) 将此值的前6个bits进行翻转0b0000 01 => 0b1111 10 ；
5) 翻转值的MSB为1。将MSB设0后，翻转值的十进制表示为30;
6) 根据5)中的结论，则设置组1的第30位为1。
至此，此地址的Hash过程结束。转换为C语言代码请参阅Linux源码的各个网卡驱动。在此我推荐/driver/net/r8169.c，因为本人就是参阅此代码理解上述过程的。
【链路层之物理层】
当网卡接收到一个数据帧时，会按照如下的流程图进行过滤分析(以下图片摘记Dana Castillo的文章)
注意此图的范围，只是检测I/G标志位符合包，略去了crc校验，AcceptX等标志开启的条件。如有更多疑问，可以参阅Dana的文章，写的很详细。
[扩展]
关于Linux中的CRC算法的实现
算法原理请参阅此篇论文