Linux内核与驱动面试经典“小”问题集锦（6）

接前一篇文章：Linux内核与驱动面试经典“小”问题集锦（5）

问题8

问：如何判断一个数是否是2的幂次（假设最多32位）？

备注：此问题是笔者年前参加小米面试时遇到的一个问题，是属于面试中的笔试。原题是一语句实现y是否为2的若干次幂的判断。

答：

其实上图中已经提供了一些思路，先要观察规律（为了简化，以8位为例）：

正例：

1：0x01即0b00000001，2的0次幂

2：0x02即0b00000010，2的1次幂

4：0x04即0b00000100，2的2次幂

……

128：0x80即0b10000000，2的7次幂

反例：

3：0x03即0b00000011

5：0x05即0b00000101

6：0x06即0b00000110

7：0x07即0b00000111

当时那为面试官还蛮有耐心，还提示到要从本数和其掩码的方面考虑。不过本人资质比较愚钝，一时也没有找到规律。他后来直接给出了答案，也就是上图中的那个：

#define is2pow(x) ((x & (x-1)) == 0)

验证：

• x=1时，x & (x-1)为0，返回真，说明是2的幂次。
• x=2时，x & (x-1)为0，返回真，说明是2的幂次。
• x=4时，x & (x-1)为0，返回真，说明是2的幂次。
• x=8时，x & (x-1)为0，返回真，说明是2的幂次。
• x=3时，x & (x-1)为2，返回假，说明不是2的幂次。
• x=5时，x & (x-1)为4，返回假，说明不是2的幂次。
• x=6时，x & (x-1)为4，返回假，说明不是2的幂次。
• x=7时，x & (x-1)为6，返回假，说明不是2的幂次。

总结：

这道题背后考察的不光是候选者的智商和数字敏感性，而更多地是考察内核的功力，因为Linux内核中有很多基于2的幂次的判断。对于此不熟悉，说明对于内核与驱动看得不够透彻、不够精通。

问题9

问：container_of内核中经常遇到吧，请写出其具体的代码实现？

备注：此问题是笔者年前参加小米面试时遇到的一个问题，是属于面试中的笔试。笔者几年之前参加位于北京玉泉慧谷的一家公司（公司名字已不记得了，只记得地点）面试的时候，也被问到过这个问题，不过当时只是和面试官说了思路，并没有直接写出完整代码。

答：

container_of(ptr, type, member)宏的作用是通过结构体成员的地址和结构体类型推导出结构体的地址，type是指结构体的类型，member是成员在结构体中的名字，ptr是该成员在type结构体中的地址。

实际上笔者多年来看内核的代码经常会遇到container_of，也花时间研究过代码，尤其是之前面试中被问到时，面试结束回来后曾经认真研究过一番。但是几次都是当时弄得很明白，时间一长就淡忘了。并不能做到信手拈来，这也应该是不经常玩内核的一种不足。

笔者在小米面试时被问到这个问题后，就努力在脑海中回忆container_of这个宏的具体实现。依稀记得是这样：

#define container_of(pointer, structure, member) (structure *)(pointer - (&((structure *)0)->member))

这是当时笔者第一时间想出来的。但是并不完全正确。

当时面试官说，要实现container_of宏，必须先实现offset_off宏，因此笔者就没有直接给出container_of的实现，而是按照面试官的思路即要求，先写出了offset_off宏，如下：

#define offset_off(structure, member) (&(((structure *)NULL)->member))

这样写完了之后，面试官指出了不足，应该将偏移强制转换为int类型，如下：

#define offset_off(structure, member) ((int)(&((structure *)NULL)->member))

完成了offset_off宏之后，进一步再实现container_of宏，我开始的实现是这样：

#define container_of(pointer, structure, member) ((int)(pointer) - offset_off(structure, member))

面试官又指出了一处不足，应该强制转换为void *类型，更正后实现如下：

#define container_of(pointer, structure, member) (void *)((int)(pointer) - offset_off(structure, member))

将offset_off宏完全展开后，最终得到：

#define container_of(pointer, structure, member) (void *)((int)(pointer) - ((int)(&((structure *)NULL)->member)))

和笔者最开始所构想的进行对比：

• 最初构想的：

#define container_of(pointer, structure, member) (structure *)(pointer - (&((structure *)0)->member))

•  最终实现的：

#define container_of(pointer, structure, member) (void *)((int)(pointer) - ((int)(&((structure *)0)->member)))

总结：

通过以上过程可以发现，虽然在大方向上能够答出，但在细节、精细度上和大公司那些人还是有一些差距，这是今后做技术需要弥补的。

在此顺带给出Linux内核中container_of宏的完整实现，在include/linux/container_of.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.** WARNING: any const qualifier of @ptr is lost.*/
#define container_of(ptr, type, member) ({				\void *__mptr = (void *)(ptr);					\static_assert(__same_type(*(ptr), ((type *)0)->member) ||	\__same_type(*(ptr), void),			\"pointer type mismatch in container_of()");	\((type *)(__mptr - offsetof(type, member))); })

这个正宗的container_of的定义比较复杂，换一个相对比较好理解的版本，在tools/include/linux/kernel.h中，代码如下：

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)/*** 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) ({			\const typeof(((type *)0)->member) * __mptr = (ptr);	\(type *)((char *)__mptr - offsetof(type, member)); })

对比：